Para una permutación aleatoria, ¿cuál es la probabilidad de que cada mitad de los elementos mantenga el orden relativo?

Question

Si tomamos una permutación aleatoria de una secuencia de $2k$ elementos, $X_1, X_2, \ldots X_k, X_{k+1}, \ldots, X_{2k}$ . ¿Cuál es la probabilidad de que $X_1, X_2, .. X_k$ y $X_{k+1}, \ldots, X_{2k}$ ¿ambas mantienen su orden relativo en la nueva secuencia?

Mi opinión es que estos dos eventos son independientes porque el hecho de que uno ocurra no cambia la probabilidad del otro. Así que tenemos

$$ \Pr \{ [\text {both sub-sequence keep relative order}]\} = (\frac 1 {n!})^2 $$

¿Qué te parece? ¿Es posible obtener el resultado contando cuántas permutaciones cumplen la condición?

Answer 1

Su razonamiento me parece correcto. Otra forma de conseguirlo:

Para contar los posibles arreglos, imaginemos el primero $k$ elementos son blancos y el resto negros. Es fácil ver que si se nos dan los colores de una determinada disposición, se pueden identificar los elementos; por lo tanto, contar todas las permutaciones "legales" equivale a contar todas las formas posibles de colocar $k$ negro y $k$ elementos blancos en $2k$ posiciones. Esto es ${2n \choose n}$ . Y el número total de permutaciones es $(2n)!$ Por lo tanto, la probabilidad es

$$\frac{{2n \choose n}}{(2n)!} = \frac{1}{(n!)^2}$$

Answer 2

El argumento de la independencia me parece sólido, aunque los supuestos podrían necesitar una justificación dependiendo de a quién se le pregunte. Simplemente se toman los índices del primer $k$ objetos después de la permutación y clasificarlos; esto produce una permutación de la $k$ objetos y por simetría no hay preferencia por una permutación sobre otra. Sólo una permutación conserva el ordenamiento relativo (la identidad) por lo que la probabilidad de que mantengan su ordenamiento es $1/k!$ . El cumplimiento de esta condición es independiente entre el primer $k$ y el segundo $k$ argumentos por lo que multiplicamos las probabilidades para obtener $1/k!^2$ .

Pero sí, es posible contar las permutaciones que cumplen las condiciones: cada forma de permutar $2k$ elementos tales que el primero y el segundo $k$ elementos de forma independiente mantener su orden relativo es esencialmente una forma de elegir $k$ posiciones fuera del $2k$ posible para la primera $k$ elementos para ir - esto determina automáticamente la permutación completa (¿puede ver cómo?). Y el número total de permutaciones es $(2k)!$ por lo que la probabilidad es $\frac{1}{(2k)!}{2k\choose k}=\frac{1}{k!^2}$ . De manera más general, si se toma $n$ elementos y dividirlos en partes de tamaño $a_1,a_2,\dots,a_m$ (ni siquiera tienen que ser partes contiguas), la probabilidad de que una permutación preserve el ordenamiento relativo de cada parte es $$\frac{1}{n!}{n\choose a_1,\dots,a_{m-1}}=\frac{1}{a_1!a_2!\cdots a_m!}.$$ Como puedes adivinar por la forma anterior, el argumento de la independencia también funciona para esto.