Si tomo la primera carta de un mazo de cartas y la coloco al azar en el paquete, ¿cuántas veces tendré que repetir esto antes de mover todas las cartas?

Answer 1

Si tomo la primera carta de un mazo de cartas y la coloco al azar en el paquete, ¿cuántas veces tendré que repetir esto antes de mover todas las cartas?
Suponiendo que la colocación de nuevo en el mazo no estaba de nuevo en la parte superior, sino por lo demás totalmente al azar cuántas veces en promedio tendría que seguir tomando la carta superior, volviendo a colocarla y haciendo lo mismo con la siguiente carta en la parte superior antes de cada carta había estado en la cima y luego reemplazado al menos una vez?

Como la pregunta está redactada, creo que la respuesta es que todas las tarjetas nunca se moverán .

La pregunta dice que una tarjeta retirada de la parte superior se colocará aleatoriamente en el paquete . La palabra clave es ‘ dentro ‘, que significa entre la nueva carta superior y la carta inferior. De hecho, el comentario que lo acompaña refuerza esto al dar instrucciones para seguir tomando la primera carta y colocarla nuevamente .

Y así, la carta inferior nunca se moverá.

Answer 2

Gracias por el A2A. La respuesta de Mark es bastante correcta. Este problema es una versión del famoso problema del colector de cupones, aunque se invierte en el pedido.

La versión original dice que hay cupones de, por ejemplo, 52 tipos. Es igualmente probable que cada cupón que recolecte sea de cualquiera de los 52 tipos (independientemente). Deje que N sea el número total de cupones que necesita recolectar para tener al menos uno de cada tipo.

Se puede demostrar que la distribución de N es la misma que la distribución de la suma de 52 variables aleatorias geométricas independientes con parámetros [matemática] \ frac k {52} [/ matemática] para [matemática] k = 1,2,3 , \ ldots, 52 [/ math]. Su valor esperado es, por lo tanto, la suma de los recíprocos de estos parámetros como dice Mark. Wikipedia tiene información adicional interesante sobre este problema, incluido el comportamiento de distribución asintótico.

Su problema es equivalente porque la cantidad de cupones adicionales necesarios para obtener el tipo 52 es la misma variable aleatoria que la cantidad de cartas que necesita robar para mover la carta inferior del mazo a la posición 51. En general, la variable aleatoria para el tipo de cupón [math] (53-k) [/ math] es la misma que para la tarjeta del tipo [math] k [/ math].

Otra versión equivalente sería:

¿Cuántas tiradas de un dado de 52 lados se necesita para ver las 52 caras al menos una vez?

Answer 3

Lo único que importa en esta situación es la posición de la tarjeta que inicialmente estaba en la parte inferior. Esta carta que se está robando es necesaria y suficiente para que cada carta se haya robado una vez, ya que el orden de las cartas no retiradas en el mazo no puede cambiar.

Por lo tanto, podemos dividir este proceso en pasos, en cada punto considerando cuántas cartas debemos robar hasta que la carta inferior inicial suba una en el mazo.

Inicialmente, solo hay 1 de n ranuras que lograrán esto. Por lo tanto, podemos esperar que esto tome n empates en promedio. El siguiente paso tiene 2 de n ranuras, por lo que podemos esperar necesitar n / 2 sorteos.

Siguiendo este patrón, tenemos la expectativa de

[matemáticas] \ sum_ {i = 1} ^ n \ frac {n} {i} = n H_n [/ matemáticas]

que es asintóticamente [matemáticas] \ Theta (n log n) [/ matemáticas].

Answer 4

Steve Brown tiene razón con la forma en que está formulada la pregunta.

Si la pregunta quería decir que la tarjeta se coloca inmediatamente debajo de otra carta aleatoria, entonces la resuelves así: como han dicho otros, solo debes preocuparte por la tarjeta que está en la parte inferior al comienzo.

Cuando comienzas, tienes una probabilidad de 1/51 de poner la carta debajo de la carta inferior, porque no puedes poner la carta debajo de sí misma y no puede ir encima. El número de sorteos sería una variable aleatoria geométrica.

Después de la primera carta, la probabilidad se convertirá en 2/51, luego en 3/51, hasta 51/51 para la 51a carta que se encuentra debajo de la carta inferior. Luego movemos la carta inferior al final.

La carta inferior solo necesitará 1 movimiento, porque no importa dónde la muevas. La carta antes de la carta inferior también necesitará solo un movimiento, ya que solo podrá moverse debajo de la carta inferior, o debajo de una de las otras cartas que ya están debajo de la carta inferior.

Solo tenemos que sumar los valores esperados de los movimientos para cada una de las cartas colocadas debajo de la carta inferior. El valor esperado de una variable aleatoria geométrica es el recíproco de la probabilidad. La probabilidad es [matemática] \ frac {i} {51} [/ matemática]. Ya dije que el valor esperado para las tarjetas 51 y 52 es 1, por lo que solo tenemos que lidiar con los valores esperados de las otras.

Por lo tanto, obtenemos esto:

[matemáticas] \ displaystyle 2+ \ sum_ {i = 1} ^ {50} \ dfrac {51} {i} = 2 + 51 \ sum_ {i = 1} ^ {50} \ dfrac {1} {i} \ aproximadamente 231.45947225 [/ matemáticas]