Si una serie de n términos está desordenada, ¿cuál es la probabilidad de que ningún término se sitúe al lado de un término al que estaba originalmente?

Question

Me he topado con este interesantísimo problema cuya solución se me ha escapado hasta ahora y creo que sería muy fascinante ver cómo se puede abordar con precisión.

Funciona de la siguiente manera,

Si alguna serie de $n$ términos se desvirtúa, ¿cómo podemos calcular primero la probabilidad de que ningún término se sitúe al lado de un término al que estaba originalmente, y además, si $n$ resulta ser infinita, ¿cómo podemos demostrar que la probabilidad es $e^{-2}$ ?

Answer 1

La relación límite no es difícil de derivar mediante el método de los momentos.

En una permutación aleatoria $\sigma$ de $\{1,2,\dots,n\}$ (no necesariamente un desvarío), que $X_n$ sea

• el número total de enteros $i$ , $1 \le i \le n$ , de tal manera que $\sigma(i) = i$ , además
• el número total de enteros $i$ , $1 \le i \le n-1$ , de tal manera que $\sigma(i+1) = \sigma(i)+1$ , además
• el número total de enteros $i$ , $1 \le i \le n-1$ , de tal manera que $\sigma(i) = \sigma(i+1)+1$ .

Demostraremos que para cualquier $k$ tenemos $\lim_{n \to \infty} \mathbb E[\binom{X_n}{k}] = \frac{3^k}{k!}.$ Si una variable aleatoria $X$ es Poisson con media $3$ también tenemos $\mathbb E[\binom{X}{k}] = \frac{3^k}{k!}$ . La distribución de Poisson está determinada por sus momentos, por lo que se deduce que $X_n$ converge en su distribución a $X$ y en particular $\lim_{n \to \infty} \Pr[X_n = 0] = e^{-3}$ .

Para ver esto, observe que $X_n$ es la suma de $3n-2$ variables indicadoras correspondientes a cada uno de los eventos (enumerados anteriormente) que $X_n$ cuenta, así que $\binom{X_n}{k}$ cuenta el número de tamaño- $k$ conjuntos de eventos que se producen. El cálculo es difícil de hacer con exactitud, pero es más o menos sencillo asintóticamente. Fuera del $\binom{3n-2}{k}$ opciones de $k$ eventos, $(1-o(1))\binom{3n-2}{k}$ nunca implican el mismo valor $\sigma(i)$ más de una vez, por lo que la probabilidad de que ocurran es $(1+o(1))n^{-k}$ . Estos contribuyen $(1+o(1))\frac{3^k}{k!}$ al valor esperado $\mathbb E[\binom{X}{k}]$ que es todo lo que queríamos.

Así pues, queda por asegurar que la contribución de todas las demás opciones de $k$ eventos es insignificante en el límite. Empañando el panorama, algunos grupos de $j \le k$ eventos que se solapan tienen una probabilidad significativamente mayor que un grupo de $j$ eventos que no se solapan. Por ejemplo, los eventos que $\sigma(3)=3$ que $\sigma(4)=4$ y que $\sigma(4)=\sigma(3)+1$ tienen esta propiedad.

Sin embargo, nunca podremos ganar de esta manera, porque hay $O(n)$ maneras de elegir que un grupo de $j$ eventos superpuestos (con un factor constante que depende de $k$ ) pero un $O(n^{-2})$ probabilidad de que se produzcan todos los eventos (ya que al menos dos valores de $\sigma$ están involucrados). Por lo tanto, para cualquier posible estructura superpuesta, la contribución a $\mathbb E[\binom{X}{k}]$ es $O(n^{-1})$ y hay un número constante (que sólo depende de $k$ ) de estructuras superpuestas.

Como resultado, podemos ignorar todos los solapamientos y concluir que $\lim_{n\to\infty}\mathbb E[\binom{X}{k}] = \frac{3^k}{k!}$ y deducimos que $\lim_{n\to\infty} \Pr[X_n = 0] = e^{-3}$ . Por lo tanto, $$\lim_{n\to\infty} \Pr[X_n = 0 \mid \text{$ |sigma $ is a derangement}] = \lim_{n\to\infty} \frac{\Pr[X_n=0]}{\Pr[\text{$ |sigma $ is a derangement}]} = \frac{e^{-3}}{e^{-1}} = e^{-2}.$$