Inicialmente la cubierta está ordenada al azar. El objetivo es ordenar la baraja en orden. Ahora en cada turno, las cartas se barajan al azar. Si cualquiera de la inicial o de la última de las tarjetas están en orden, a continuación, se mantienen a un lado, y el proceso es seguido con el resto de las cartas. La pregunta ahora es ¿cuál es el número esperado de la baraja para toda la cubierta para obtener ordenados de esta manera.
por ejemplo, supongamos inicialmente que la cubierta es (3,5,6,2,7,1,4). Después de la primera shuffle se convierte (1,2,6,4,5,3,7), entonces el siguiente shuffle se hace con (6,4,5,3) como (1,2) y (7) ya están en el orden correcto. Compruebe que incluso si 5 también en el lugar adecuado, pero no en el continuo de la orden de ahí considerado para el shuffle.
Lo que sé es que el número esperado de la baraja para ordenar la baraja en un intento de es $n!$. (Algo que se conoce como bogo-sort). Pero no puede pensar en más. Cualquier ayuda será apreciada.
Respuestas
¿Demasiados anuncios?
Deje $r$ denotar el número de tarjetas que, después de barajar $n$ tarjetas, permanecen sin clasificar (en la porción media de la cubierta, que es ser suffled de nuevo).
Deje $t_n$ ser el número necesario o baraja a partir de $n$ tarjetas hasta que todas las cartas están ordenados. Queremos $E(t_n)$
Ahora, vamos a considerar que la expectativa condicionada a que el valor de $r_n$, es decir, supongamos que sabemos exactamente cuántas cartas permanecen sin clasificar tras el primer intento:
Entonces podemos escribir: $E[t_n | r_n=r] = 1 + E[t_r]$
(tenga en cuenta que esto incluye los casos extremos,$r_n=0$$r_n = n$)
La aplicación de la propiedad $E[E[x|y]] = E[x]$ tenemos:
$\displaystyle E[t_n] = \sum_{r=0}^n (1 + E[t_r]) \; p(n,r) $
donde $p(n,r) = Prob(r_n = r)$ (vamos a calcular más tarde)
Debemos sacar el plazo $r=n$ para la suma, y por trivial manipulación obtenemos el deseado de recursividad:
$\displaystyle E[t_n] = \frac{1}{1-p(n,n)} \left( p(n,n) + \sum_{i=0}^{n-1} (1 + E[t_r]) \; p(n,r) \right) $
Como los valores iniciales tenemos $E[t_0] = E[t_1] = 0$
Para calcular los $p(n,r)$ (la probabilidad de que después de un revolver de $n$ tarjetas de queda -con las reglas de nuestro juego - exactamente $r$ cartas para barajar de nuevo) es más simple (pero es más tedioso), sólo combinatoria contar - te voy a explicar si lo piden.
Mi resultado es
$\displaystyle p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
si $r>1$. En otros lugares, $p(n,0) = 1/n!$$p(n,1)=0$.
Aquí están algunos de los valores (en javascript) http://hjg.com.ar/varios/mat/cards.html
Por CIERTO: Este problema puede ser visto como entre los dos problemas, uno sencillo y uno de los más complejos/general: En comparación con el Cupón de Colector problema, esto es más complicado, porque no se puede dividir el camino en "estados" que se puede visitar de forma secuencial y, por tanto, podemos expresar la expectativa deseada como una suma de las expectativas de las piezas. Puede ser consisdered como un Modelo de Markov con un estado de absorción; pero el markovian formulación, a pesar de apt, es demasiado general, y el resultado deseado (número de iteraciones para alcanzar el estado de absorción) es menos straigforward que la solución que aquí se propone. Eso es porque nuestro problema tiene algunas restricciones especiales (en términos de una cadena de Markov, se diría que su transición de la matriz es triangular)
AGREGADO: Para calcular los $p(n,r)$$r \ge 2$ : Después de barajar $n$ tarjetas, obtenemos $r$ sin clasificar tarjetas, decir $(n1;r;n2)$ Permite contar cuántas maneras (con $n1$ $n2$ fijo) hay. Corresponden a elegir una permutación de las $r$ medio de tarjetas, con la condición de que ambos extremos están "equivocados". Esta está dada por:
$r! - 2(r - 1)! + (r-2)! = (r^2 - 3 r + 3) (r-2)!$
(Esta es la exclusión-inclusión a contar: el primer término cuenta todas las posibilidades, el segundo recuento de los casos en los que la primera O la última de la derecha, el tercer recuento de los casos en los que el primero Y el último son de la derecha).
Pero, para un determinado $r$ existen varias opciones de $(n1;n2)$, sólo están obligados a resumir $n-r$. En realidad, hay $n - r +1$ alternativas. A continuación, obtenemos el número total de permutaciones que dan a $r$ sin clasificar tarjetas, y se divide sobre todas las permutaciones:
$\displaystyle p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
ACTUALIZADO: Un asintótica puede ser adivinado que (teóricamente y empíricamente):
$\displaystyle E(t_n) \approx \frac{n(n-1)}{4} \approx \frac{n^2}{4}$
Uno tiene la recurrencia de la siguiente manera. Deje $N(n)$ denotar el número medio de baraja necesarios para ordenar una baraja de $n$ tarjetas y $p_n(k)$ la probabilidad de fijar exactamente $k$ tarjetas por barajar una vez que una baraja de $n$ tarjetas. A continuación, $N(1)=0$ (la cubierta ya está ordenada) y, para cada $n\ge2$, $$ N(n)=1+\sum_{k=0}^{n-2}p_n(k)N(n-k). $$ Deje $T_n$ $B_n$ denotar los números aleatorios de tarjetas fijas en la parte superior y en la parte inferior de la cubierta por una shuffle, así $$ p_n(k)=P(T_n+B_n=k). $$ El evento $[T_n\ge i,B_n\ge j]$ corresponde al hecho de que $i+j$ tarjetas tienen su posición impuesta y el resto de $n-i-j$ cartas se barajan libremente. Por lo tanto $$ P(T_n\ge i,B_n\ge j)=(n-k)!/n!=r_n(n-k) $$ para cada $(i,j)$ tal que $i+j=k$. Ahora $[T_n=i,B_n=j]$ es $$ [T_n\ge i,B_n\ge j]-[T_n\ge i+1,B_n\ge j]-[T_n\ge i,B_n\ge j+1]+[T_n\ge i+1,B_n\ge j+1], $$ por lo tanto $$ P(T_n=i,B_n=j)=r_n(n-k)-2r_n(n-k-1)+r_n(n-k-2). $$ Desde $p_n(k)$ $(k+1)$ veces esta, uno se $$ N(n)=1+\sum_{k=0}^{n-2}(k+1)(r_n(n-k)-2r_n(n-k-1)+r_n(n-k-2))N(n-k), $$ es decir, $$ n!N(n)=n!+\sum_{k=2}^{n}(n-k+1)\left(k!-2(k-1)!+(k-2)!\right)N(k). $$ El resto debe ser una historia de la generación de funciones técnicas, como se explica aquí.
Algunos pensamientos: habrá una recurrencia. La idea es encontrar el tiempo de espera para reducir el número de cartas en la baraja, a continuación, para encontrar la probabilidad de que si se reduzca, ¿cuál es la probabilidad de que reducir por 1, 2, ... Primero la probabilidad de que al menos uno de los extremos está en la posición correcta es 2/n, como puedo reclamar el hecho de que la parte superior de la tarjeta no está bien no cambia la probabilidad de que la parte inferior de la tarjeta es cierto-no es de 1/n de la posibilidad de que la parte superior de la tarjeta debe estar en la parte inferior, luego del 1-1/n=(n-1)/n de probabilidades de que no hay es 1/(n-1) probabilidad de que el derecho es en la parte inferior. Así que el tiempo de espera para la reducción de la es n/2. A continuación, ordenar,$P_k(n)$, la probabilidad de que si hay una reducción es exactamente k. Por el argumento anterior, $P_1(n)=\frac{n-3}{n-1}$, Entonces, como en el cupón de colector problema tiene N(n) (el número de baraja de n de tarjetas)=n/2(probabilidad de que una reducción de 1 dado que hay una reducción)*N(n-1)+probabilidad de reducción de 2 dado que hay una reducción)*N(n-2)+...)
Añadido: 2 es especial, ya que si una tarjeta es mejor, también lo es el otro. Esta probabilidad es 1/2. Por lo que el número esperado de la baraja es de 2. De 3, tiene 1/3 de probabilidades de nada correcto, 1/6 de probabilidad de todas correctas, y 1/2 de probabilidad de 1 correcto. Entonces N(3)=(1/3)(N(3)+1)+(1/2)(N(2)+1)+(1/6)(N(0)+1) Como usted sabe, N(2)=2 y N(0)=0 se puede resolver para N(3)
