¿Cuál es la longitud esperada de la subsecuencia consecutiva más larga de una permutación aleatoria de los enteros 1 a N? Para ser más precisos, estamos buscando la cadena más larga de enteros consecutivos en la permutación (sin tener en cuenta dónde se produce esta cadena). Creo que la respuesta debería ser ~ c ln(n), pero no he podido demostrarlo.
Actualización: Buscamos la subsecuencia creciente más larga. Es decir, 9,1,5,2,7,3 tiene una subsecuencia creciente 1,2,3.
El objetivo de esta respuesta es utilizar el método del segundo momento para hacer riguroso el argumento heurístico de Michael Lugo. (He aquí por qué su argumento es sólo heurístico: Si $N$ es una variable aleatoria entera no negativa, como el número de longitudes $r$ secuencias consecutivas crecientes en una permutación aleatoria de $\{1,2,\ldots,n\}$ sabiendo que $E[N] \gg 1$ no implica que $N$ es positivo con alta probabilidad, porque la gran expectativa podría ser causada por un evento raro en el que $N$ es muy grande).
Teorema: La longitud esperada del bloque creciente más largo en una permutación aleatoria de $\{1,2,\ldots,n\}$ es $r_0(n) + O(1)$ como $n \to \infty$ , donde $r_0(n)$ es el menor número entero positivo tal que $r_0(n)!>n$ . ("Bloque" significa subsecuencia consecutiva $a_{i+1},a_{i+2},\ldots,a_{i+r}$ para algunos $i$ y $r$ sin condiciones sobre los tamaños relativos de los $a_i$ .)
Nota: Como señaló Michael, $r_0(n)$ es de orden $(\log n)/(\log \log n)$ .
Prueba del teorema: Dejemos que $P_r$ es la probabilidad de que exista un bloque creciente de al menos $r$ . La longitud esperada del bloque creciente más largo es entonces $\sum_{r \ge 0} r(P_r-P_{r+1}) = \sum_{r \ge 1} P_r$ . Acotaremos esta última suma por arriba y por abajo.
Límite superior: La probabilidad $P_r$ es como máximo la esperada número de bloques crecientes de longitud $r$ que es exactamente $(n-r+1)/r!$ ya que para cada uno de los $n-r+1$ valores de $i$ en $\{0,\ldots,n-r\}$ la probabilidad de que $a_{i+1},\ldots,a_{i+r}$ están en orden creciente es $1/r!$ . Así, $P_r \le n/r!$ . Por comparación con una serie geométrica con relación $2$ tenemos $\sum_{r > r_0(n)} P_r \le P_{r_0(n)} \le 1$ . Por otro lado $\sum_{1 \le r \le r_0(n)} P_r \le \sum_{1 \le r \le r_0(n)} 1 \le r_0(n)$ Así que $\sum_{r \ge 1} P_r \le r_0(n) + 1$ .
Límite inferior: Aquí necesitamos el método del segundo momento. Para $i \in \{1,\ldots,n-r\}$ , dejemos que $Z_i$ sea $1$ si $a_{i+1}<a_{i+2}<\ldots<a_{i+r}$ y $a_i>a_{i+1}$ y $0$ en caso contrario. (La condición añadida $a_i>a_{i+1}$ es un truco para reducir la correlación positiva entre los $Z_i$ .) La probabilidad de que $a_{i+1}<a_{i+2}<\ldots<a_{i+r}$ es $1/r!$ y la probabilidad de que se mantenga mientras $a_i>a_{i+1}$ falla es $1/(r+1)!$ Así que $E[Z_i]=1/r! - 1/(r+1)!$ . Dejemos que $Z=\sum_{i=1}^{n-r} Z_i$ Así que $$E[Z]=(n-r)(1/r! - 1/(r+1)!).$$ A continuación calculamos el segundo momento $E[Z^2]$ al ampliar $Z^2$ . Si $i=j$ entonces $E[Z_i Z_j] = E[Z_i] = 1/r! - 1/(r+1)!$ sumando todo esto $i$ da menos o igual que $n/r!$ . Si $0<|i-j|<r$ entonces $E[Z_i Z_j]=0$ ya que las desigualdades son incompatibles. Si $|i-j|=r$ entonces $E[Z_i Z_j] \le 1/r!^2$ (esta última es la probabilidad si eliminamos la condición añadida en la definición de $Z_i$ y $Z_j$ ). Si $|i-j|>r$ entonces $Z_i$ y $Z_j$ son independientes, por lo que $E[Z_i Z_j] = (1/r! - 1/(r+1)!)^2$ . La suma de todos los $i$ y $j$ muestra que $$E[Z^2] \le \frac{n}{r!} + E[Z]^2 \le \left(1 + O(r!/n) \right) E[Z]^2.$$ El método del segundo momento da la segunda desigualdad en $$P_r \ge \operatorname{Prob}(Z \ge 1) \ge \frac{E[Z]^2}{E[Z^2]} \ge 1 - O(r!/n).$$ Si $r \le r_0(n)-2$ entonces $r! \le (r_0(n)-1)!/(r_0(n)-1)$ Así que $r!/n \le 1/(r_0(n)-1)$ Así que $P_r \ge 1 - O(1/r_0(n))$ . Así, $$\sum_{r \ge 1} P_r \ge \sum_{r=1}^{r_0(n)-2} \left( 1 - O(1/r_0(n)) \right) = r_0(n) - O(1).$$
Si entiendo bien la pregunta, creo que la respuesta es un poco más grande que $2$ .
Estoy interpretando que la pregunta busca la subcadena más larga de la forma $i(i+1)(i+2) \cdots (i+r)$ en cualquier parte de la permutación. La probabilidad de que cualquier cadena de $3$ los caracteres serán de esta forma es $(n-2)/\binom{n}{3} = O(1/n^2)$ . Por linealidad de la expectativa, el número esperado de tales cadenas de longitud $3$ es $O(1/n)$ . En particular, la probabilidad de que tengamos una cadena de longitud $3$ o superior es $O(1/n)$ .
¿Está buscando el valor esperado $E(n)$ de los mayores $k$ para lo cual $1,2,\dots,k$ es una subsecuencia creciente? La probabilidad de que $1,2,\dots,k$ es una subsecuencia creciente es $1/k!$ por lo que la probabilidad de que $k$ es el mayor valor de este tipo es $\frac{1}{k!}-\frac{1}{(k+1)!}$ . Así, $$ \lim_{n\to\infty}E(n) = \sum_{k\geq 1}k\left(\frac{1}{k!}-\frac{1}{(k+1)!}\right) = e-1. $$
Asumiendo la interpretación que di en un comentario anterior, basta con encontrar la longitud de la subsecuencia consecutiva más larga en una secuencia de $n$ variables aleatorias $(X_1, \ldots, X_n)$ cada uno de los cuales es uniforme en $[0,1]$ . Tal $n$ -determina una permutación siempre y cuando nunca tengamos $X_i = X_j$ Esto ocurre con probabilidad cero.
La probabilidad de que $X_{i+1} < \cdots < X_{i+r}$ es sólo $1/r!$ . Por tanto, el número esperado de subsecuencias consecutivas crecientes de longitud $r$ en una secuencia de longitud $n$ es $n/r!$ .
Por lo tanto, la longitud de la subsecuencia creciente más larga debe estar cerca de $r_0(n)$ , donde $r_0 := r_0(n)$ satisface $r_0! = n$ . Esto no es una constante de los tiempos $\log n$ . Sin embargo, si resolvemos $(r/e)^r = n$ para $r$ (esto es aproximadamente La aproximación de Stirling), obtenemos $r = \log(n)/W(\log(n)/e)$ donde W es el Función Lambert W . Como $z \to \infty$ , $W(z)$ crece más lentamente que $\log z$ , por lo que parece que $r_0(n)$ crece un poco más rápido que $\log n/\log \log n$ . No sería difícil confundir esto con un tiempo constante $\log n$ si se trabaja con datos numéricos.
Otra interpretación de este problema es, dada una permutación $a_1 a_2 \ldots a_n$ para encontrar la secuencia más larga $i_1, i_2, \ldots, i_r$ tal que $a_{i_1}, a_{i_2}, \ldots, a_{i_r}$ son números enteros consecutivos. (Por ejemplo, en 691528347, los números 1, 2, 3, 4 aparecen en ese orden.) La subsecuencia más larga de $\sigma$ en este tiene la misma longitud que la subsecuencia más larga de $\sigma^{-1}$ en el sentido anterior en esta respuesta; por ejemplo, la inversa de 691528347 es 357841962, que tiene la secuencia creciente consecutiva 3578. Así que las longitudes de las secuencias crecientes más largas en estas dos interpretaciones tienen la misma distribución.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
