El valor esperado de la máxima consecutivos distancia en un uniforme de permutación aleatoria

Question

¿Cómo calcular $\mathbb{E}[\max_{1\le i < n} |\sigma(i) - \sigma(i+1)|]$ donde la expectativa es que se toman sobre un uniformemente al azar permutación $\sigma \in \mathbb{P}_n$, el conjunto de todas las permutaciones en $[n]$?

Hay una recursividad para $c^n_t$ que cuenta el número de permutaciones $\sigma$ $[n]$ tal que $\max_{1\le i < n} |\sigma(i) - \sigma(i+1)| \le t$?

Answer 1

La respuesta a tu primera pregunta es $n - \sqrt{\pi n}/2 + o(\sqrt{n})$. La prueba es bastante complicado. Así que sólo haré un bosquejo de la idea principal. Déjeme saber si usted está interesado en obtener más detalles.

La respuesta a la segunda pregunta es: $(\alpha t)^n \leq c_t^n \leq (\beta t)^n$ para algunas constantes $\alpha, \beta > 0$.

Parte I. Un presupuesto para $\mathbb{E}[\max_{1\le i < n} |\sigma(i) - \sigma(i+1)|]$.

Será conveniente trabajar con la variable aleatoria $\Delta = n - \max_{1\le i < n} |\sigma(i) - \sigma(i+1)|$. Nuestro objetivo es demostrar que $\mathbb{E}[\Delta] = (\sqrt{\pi}/2 + o(1)) \sqrt{n}$. Vamos a considerar un algoritmo que genera $\sigma$ uniformemente al azar y muestran que para este algoritmo $\mathbb{E}[\Delta] = (\sqrt{\pi}/2 + o(1)) \sqrt{n}$ (por supuesto, la respuesta no depende de la forma en que generamos $\sigma$, mientras $\sigma$ se distribuye de manera uniforme).

Denotar $[n] = \{1,\dots,n\}$.

Deje $k = n ^{1/2+ \varepsilon}$ (para algunos pequeños $\varepsilon > 0$). Elija dos subconjuntos disjuntos $S,T \subset [n]$ uniformemente al azar.

Ahora

• asignar valores de $\{1,\dots, k\}$ $\sigma(i)$ $i\in S$(uso cada valor una vez);
• asignar valores de $\{n-k+1,\dots, n\}$ $\sigma(i)$ $i\in T$(uso cada valor una vez);
• asignar valores de $\{k+1,\dots, n-k\}$ $\sigma(i)$ $i\in [n]\setminus (S\cup T)$(uso cada valor una vez).

Tenemos una permutación $\sigma$ distribuido uniformemente al azar.

La Observación Informal. Observar que si $i\in S$ $i+1\in T$ $\sigma(i+1) - \sigma(i) \geq (n-k+1) - k = n - 2k +1$ y por lo tanto $\Delta \leq 2k - 1$. Del mismo modo, si $i\in T$$i+1\in S$, luego $\Delta \leq 2k - 1$. Por otro lado, si no es $i$ tal que cualquiera de las $i\in S$ $i+1\in T$ o $i\in T$ $i+1\in S$ a continuación, para cada $i$, $|\sigma(i) - \sigma(i+1)| \leq n - (k+1)$. Por lo $\Delta \geq k + 1$.

Tenga en cuenta que por la Paradoja de Cumpleaños un par de $(i,i+1)$ $i\in S$ y $i+1\in T$ debe existir al $k\approx \sqrt{n}$. Por lo tanto, esperamos que que $\Delta = \Theta(\sqrt n)$.

Deje $A$ el conjunto de pares $(i,i+1)$ tal que $i\in S$ $i+1\in T$ o $i\in T$$i+1\in S$. Estimar el tamaño de $A$. La probabilidad de que $i\in S$$i+1\in T$$\frac{|S| \cdot |T|}{n(n-1)} = \frac{k^2}{n(n-1)}$; la probabilidad de que $i\in T$$i+1\in S$$\frac{k^2}{n(n-1)}$. Por lo tanto, la previsión del número de pares es $2k^2/n$. Por otra parte, el número de pares se concentra cerca de $2k^2/n$.

Puede suceder que $(i,i+1)\in A$$(i+1,i+2)\in A$. Pero el número esperado de dichas $i$ es de aproximadamente $k^3 / n^2$. Así que por la desigualdad de Markov hay al menos uno de esos $i$ con probabilidad en la mayoría de los $k^3/n^2 = n^{3\varepsilon - 1/2}$. Podemos ignorar este evento.

Vamos \begin{align} S' &= \{i\in S: (i,i+1) \in A \text{ or } (i-1,i)\in A\},\\ T' &= \{i\in T: (i,i+1) \in A \text{ or } (i-1,i)\in A\}. \end{align} Recordemos que hemos asignado valores de$\{1,\dots,k\}$$\sigma(i)$$i\in S$. Deja un poco de modificar el procedimiento de asignación:

1. Para cada una de las $i\in S'$ asigne $\sigma(i)$ un valor de $\{1,\dots, k\}$ independientemente uniformemente al azar.
2. Si hemos utilizado cada valor de $\{1,\dots, k\}$ a lo sumo una vez, asignar valores no utilizados de $\{1,\dots, k\}$ al azar para asignar $\sigma(i)$, $i\in S\setminus S'$ el uso de cada valor de una sola vez.
3. Si utilizamos algún valor más de una vez, asignar valores de $\{1,\dots, k\}$ a todos $\sigma(i)$, $i\in S$ el uso de cada valor de una sola vez (reasignar algunos $\sigma(i)$).

Tenga en cuenta que el número esperado de pares $(i,j) \in S'\times S'$ de manera tal que se le asignó a $\sigma(i) = \sigma(j)$ en el primer paso es de aproximadamente $|S'|^2 / k = 4k^3/n^2 = 4n^{ - 1/2 + 3\varepsilon}$. La probabilidad de que haya al menos uno de estos pares es en la mayoría de las $4n^{ - 1/2 + 3\varepsilon}$. Podemos ignorar este evento. Así, podemos asumir que el algoritmo de asignación siempre realiza los pasos 1 y 2 (y nunca realiza el paso 3). Nosotros igualmente modificar el procedimiento para la asignación de valores a$\sigma(i)$$i\in T'$.

A continuación, para cada par de $(i,i+1) \in A$, $\sigma(i)$ se distribuye uniformemente al azar en $\{1,\dots, k\}$ $\sigma(i+1)$ es distribuido uniformemente al azar en $\{n-k+1,\dots, n\}$ o de la otra manera alrededor. Los valores de $\sigma(i), \sigma(i+1)$ para los diferentes pares de $(i,i+1) \in A$ son independientes.

Tenemos que por cada $(i,i+1) \in A$, la variable aleatoria $n+1 - |\sigma(i) - \sigma(i+1)|$ se distribuye como una suma de dos variables aleatorias uniformemente distribuidas en $\{1,\dots,k\}$. Ahora nuestro objetivo es estimar el mínimo de $2k^2/n$ independiente de las copias de dicha variable aleatoria.

Considere dos yo.yo.d. variables aleatorias $x \in_U (0,1)$$y \in_U (0,1)$. A continuación, $\lceil k x\rceil$ $\lceil k y\rceil$ están distribuidos de manera uniforme en $\{1,\dots,k\}$. Por lo $n+1 - |\sigma(i) - \sigma(i+1)|$ se distribuye de la $\lceil k x\rceil + \lceil k y\rceil \approx k(x+y)$ (hasta una constante aditiva 2).

Lema. Deje $x_1,\dots,x_N$ $y_1,\dots,y_N$ ser independiente de las variables aleatorias uniformemente distribuidas en $(0,1)$. Vamos $z_i = x_i + y_i$. Entonces $$\mathbb{E}[\min_i\{z_i\}] \approx \sqrt{\frac{\pi}{2N}}.$$

Prueba: La función de distribución de $F(t)$ c.d.f.) de $z_i$ está dado por $$F(t) = \begin{cases} 0, & \text{ if } t \leq 0;\\ t^2/2, & \text{ if } 0\leq t \leq 1;\\ 2t-1 - t^2/2, & \text{ if } 1\leq t \leq 2;\\ 1, &\text{ if } t > 1. \end{casos} $$

Tenga en cuenta que si $z_i < z_j$$F(z_i) < F(z_j)$. Por lo tanto $\arg\min_i F(z_i) = \arg\min_i z_i$. Cada una de las $F(z_i)$ es distribuido uniformemente en $[0,1]$. Por lo tanto $\min_i\{ F(z_i)\}$ tiene de densidad de probabilidad $N\cdot (1-s)^{N-1}$. Tenemos $$\mathbb{E}[\min_i\{z_i\}]=\int_0^1 N\cdot s^{N-1} F^{-1}(s) ds \approx \int_0^1 N\cdot s^{N-1}\sqrt{2s} ds = \sqrt{2}\cdot N \cdot B(N,3/2)\approx \sqrt{2}\cdot\Gamma(3/2) \cdot N \cdot N^{-3/2}=\sqrt{\pi/(2N)},$$ donde $B$ es la función beta y $\Gamma$ es la función gamma.

QED

Así, el mínimo de $2k^2/n$ copias independientes de $x+y$ es aproximadamente igual a $\sqrt{\pi n/(4k^2)}$ en la espera. El mínimo de $2k^2/n$ copias independientes de $k(x+y)$ es aproximadamente igual a $\sqrt{\pi n}/2$ en la espera.

Tenemos que la mínima sobre todos los pares de $(i,i+1)\in A$ $n+1 - |\sigma(i) - \sigma(i+1)|$ es de aproximadamente $\sqrt{\pi n}/2$. Si $(i,i+1)\notin A$$n+1 - |\sigma(i) - \sigma(i+1)| \geq k +1 \gg \sqrt{n}$. Se demostró que la $\Delta$ es aproximadamente igual a $\sqrt{\pi n}/2$ en la espera.

La parte II. De la simulación.

Nuestra estimación de acuerdo con los datos de una simulación computacional, que he hecho en MATLAB. Para$n$$100$$10000$, $$\sqrt{\pi n}/2 -0.75 < \Delta_{\text{simulation}}(n) < \sqrt{\pi n}/2 + 0.1,$$ donde $\Delta_{\text{simulation}}(n)$ es una estimación de $\Delta$ obtenido en la simulación.

La parte III. Una estimación de $c_t^n$.

Podemos demostrar primero que $c_t^n \leq n (2t)^{n-1}$. Hay $n$ formas de elegir los $\sigma(1)$. Dado $\sigma(1)$, hay en la mayoría de las $2t$ formas de elegir los $\sigma(2)$: $$\sigma(2)\in \{\sigma(1) -2t,\dots,\sigma(1)-1,\sigma(1)+1,\dots,\sigma(1)+t\}.$$ Del mismo modo, existen en la mayoría de las $2t$ formas de elegir cada una de las $\sigma(i)$$i\in\{2,\dots, n\}$. Por lo que el número total de permutaciones $\sigma$ (para un valor dado de a $t$) es en la mayoría de las $n (2t)^{n-1}<(\beta t)^n$ (para algunos $\beta>0$).

Ahora podemos demostrar que hay al menos $(t!)^{\lfloor n/(t+1)\rfloor} > (\alpha t)^n$ permutaciones (para algunos $\alpha > 0$). Considerar el conjunto de las permutaciones de los formulario $$[1, 2, \dots t], (t+1), [(t+1) + 1, (t+1) + 2 \dots (t + 1) + t], 2(t+1), [2(t+1) + 1 \dots 2(t+1) +t], 3(t+1) \dots$$ donde podemos arbitrariamente permutar los números dentro de cada soporte. Tenga en cuenta que $|\sigma(i) -\sigma(i+1)| \leq t$ para todas estas permutaciones.

Vamos a contar el número de permutaciones. Hay $t!$ formas de organizar los números en el interior de cada soporte. Hay ${\lfloor n/(t+1)\rfloor} $ entre corchetes. Por lo que el número total de permutaciones es (al menos) $(t!)^{\lfloor n/(t+1)\rfloor}$. Por la fórmula de Stirling, es, al menos, $(\alpha t)^n$ algunos $\alpha > 0$.

Answer 2

Un ingenuo aproximación para la segunda pregunta. La restricción de tener una permutación de longitud $n$ con el consecutivo distancias no mayores de $t$ prohíbe a un número total de pares dado por $ 2 \times (1 + 2 + \cdots n - t-1) = (n-t)(n-t-1)$

El número total de a priori pares es $n(n-1)$. La probabilidad de que un determinado par viola la restricción es entonces $$\frac{(n-t)(n-t-1)}{n (n-1)}$$

Si asumimos (muy aproximación!) que la probabilidad de que todos los pares de violar ajuste de la restricción son independientes, tenemos una probabilidad de "éxito" dada por

$$p_{n,t}=\left(1-\frac{(n-t-1)(n-t)}{n (n-1)}\right)^{n-1} = \left( \frac{t \, (2 n - t -1)}{n \, (n-1)} \right)^{n-1}$$

Si suponemos además que $n \gg 1$:

$$p_{n,t} \approx \left(\frac{2 t }{n}\right)^{n-1} e^{-(t-1)/2} $$

El número de permutaciones, a continuación, se puede aproximar como

$$c_{n,t} = n! \; p_{n,t} \approx \left(\frac{2 t }{e}\right)^{n-1} e^{-(t-1)/2} \sqrt{2 \pi \, n}$$

He hecho un par de simulaciones y la aproximación no parece tan malo.