Tengo algunos problemas para resolver lo siguiente.
Robas cartas de una baraja estándar de 52 cartas sin reemplazo hasta que obtengas un as. Sacas de lo que queda hasta que obtienes un 2. Continúas con 3. ¿Cuál es el número esperado en el que estarás después de que se acabe todo el mazo?
Era natural dejar
Entonces, el problema esencialmente equivale a calcular la probabilidad de que esté en cuando se acabe el mazo, a saber:
Puedo ver eso
pero no pudo llegar más lejos ...
2AAA2
T 1 > T 2 T 1 < T 2Respuestas:
Siguiendo la idea de @ Gung, ¿creo que el valor esperado sería 5.84? y según mi interpretación de los comentarios, supongo que "A" es un valor casi imposible (a menos que las últimas cuatro cartas del mazo sean todos ases). Aquí están los resultados de una simulación de Monte Carlo de 100,000 iteraciones
y aquí está el código R en caso de que quieras jugar con él ...
fuente
A
imposible? Considere la secuencia de 48 cartas seguidas por,AAAA
por ejemplo.1/prod( 48:1 / 52:5 )
results
Para una simulación es crucial ser correcto y rápido. Ambos objetivos sugieren escribir código que apunte a las capacidades centrales del entorno de programación, así como un código que sea lo más breve y simple posible, porque la simplicidad brinda claridad y la claridad promueve la corrección. Aquí está mi intento de lograr ambos en
R
:Se puede aplicar esto de forma reproducible con la
replicate
función después de establecer la semilla de número aleatorio, como enEso es lento, pero lo suficientemente rápido como para realizar simulaciones bastante largas (y por lo tanto precisas) repetidamente sin esperar. Hay varias formas en que podemos exhibir el resultado. Comencemos con su significado:
El último es el error estándar: esperamos que la media simulada esté dentro de dos o tres SE del valor verdadero. Eso coloca la verdadera expectativa en algún lugar entre y5.8535.817 5.853 .
También podríamos querer ver una tabulación de las frecuencias (y sus errores estándar). El siguiente código embellece un poco la tabulación:
Aquí está la salida:
¿Cómo podemos saber que la simulación es correcta? Una forma es probarlo exhaustivamente para detectar problemas más pequeños. Por esa razón, este código fue escrito para atacar una pequeña generalización del problema, reemplazando cartas distintas con y palos con . Sin embargo, para la prueba es importante poder alimentar el código de una plataforma en un orden predeterminado. Escribamos una interfaz ligeramente diferente para el mismo algoritmo:413 4 4
n
k
(Es posible usarlo
draw
en lugar de ensim
todas partes, pero el trabajo adicional realizado al principiodraw
hace que sea el doble de lento quesim
).Podemos usar esto aplicándolo a cada barajado distinto de un mazo dado. Dado que el propósito aquí es solo unas pocas pruebas puntuales, la eficiencia en la generación de esas mezclas no es importante. Aquí hay una forma rápida de fuerza bruta:
Ahora
d
es un marco de datos cuyas filas contienen todas las barajas. Aplicardraw
a cada fila y contar los resultados:La salida (que usaremos en una prueba formal momentáneamente) es
(El valor de es fácil de entender, por cierto: todavía estaríamos trabajando en la tarjeta si y solo si todos los dos precedieron a todos los ases. La posibilidad de que esto suceda (con dos palos) es . De los shuffles distintos, tienen esta propiedad).2 1 / ( 2 + 2420 2 25202520/6=4201/(2+22)=1/6 2520 2520/6=420
Podemos probar la salida con una prueba de chi-cuadrado. Con este fin, aplico veces a este caso de cartas distintas en palos:10,000 n=4 k=2
sim
n = 4 k = 2Debido a que es tan alto, no encontramos diferencias significativas entre lo que dice y los valores calculados por enumeración exhaustiva. La repetición de este ejercicio para otros valores (pequeños) de y produce resultados comparables, lo que nos da una amplia razón para confiar cuando se aplica a y .n k n = 13p n k n=13 k=4
sim
sim
Finalmente, una prueba de chi-cuadrado de dos muestras comparará la salida de
sim
con la salida informada en otra respuesta:La enorme estadística de chi cuadrado produce un valor p que es esencialmente cero: sin duda,
sim
no está de acuerdo con la otra respuesta. Hay dos posibles resoluciones del desacuerdo: una (¡o ambas!) De estas respuestas es incorrecta o implementan diferentes interpretaciones de la pregunta. Por ejemplo, he interpretado que "después de que se acaba el mazo" significa que después de observar la última carta y, si es posible, actualizar el "número en el que estará" antes de finalizar el procedimiento. Es concebible que el último paso no esté destinado a ser dado. Quizás alguna diferencia de interpretación tan sutil explicará el desacuerdo, en cuyo punto podemos modificar la pregunta para aclarar lo que se está preguntando.fuente
Hay una respuesta exacta (en forma de un producto matricial, presentado en el punto 4 a continuación). Existe un algoritmo razonablemente eficiente para calcularlo, derivado de estas observaciones:
Se puede generar una combinación aleatoria de cartas barajando aleatoriamente tarjetas y luego intercalando aleatoriamente las cartas restantes dentro de ellas.N kN+k N k
Al mezclar solo los ases, y luego (aplicando la primera observación) intercalando los dos, luego los tres, etc., este problema puede verse como una cadena de trece pasos.
Necesitamos hacer un seguimiento de más del valor de la tarjeta que estamos buscando. Sin embargo, al hacer esto, no necesitamos tener en cuenta la posición de la marca en relación con todas las cartas, sino solo su posición en relación con las cartas de igual o menor valor.
Imagina colocar una marca en el primer as, y luego marcar los dos primeros encontrados después, y así sucesivamente. (Si en algún momento el mazo se agota sin mostrar la carta que estamos buscando actualmente, dejaremos todas las cartas sin marcar). Deje que el "lugar" de cada marca (cuando exista) sea el número de cartas de igual o menor valor que se repartieron cuando se realizó la marca (incluida la propia tarjeta marcada). Los lugares contienen toda la información esencial.
El lugar después de la marca es un número aleatorio. Para un mazo dado, la secuencia de estos lugares forma un proceso estocástico. De hecho, es un proceso de Markov (con matriz de transición variable). Por lo tanto, se puede calcular una respuesta exacta a partir de doce multiplicaciones matriciales.ith
Usando estas ideas, esta máquina obtiene un valor de (computación en coma flotante de doble precisión) en segundo. Esta aproximación del valor exacto es precisa para todos los dígitos mostrados.1 / 9 19826005792658947850269453319689390235225425695.8325885529019965 1/9
El resto de esta publicación proporciona detalles, presenta una implementación funcional (en
R
) y concluye con algunos comentarios sobre la pregunta y la eficiencia de la solución.Generación aleatoria de barajas
En realidad, es más claro conceptualmente y matemáticamente no más complicado considerar un "mazo" (también conocido como multiset ) de cartas de las cuales hay de la denominación más baja, de la siguiente más baja, y así sucesivamente . (La pregunta formulada se refiere al mazo determinado por el vector .N=k1+k2+⋯+km k1 k2 13 (4,4,…,4)
¡Una "combinación aleatoria" de cartas es una permutación tomada uniforme y aleatoriamente de la permutaciones de las cartas. Estas mezclas se agrupan en grupos de configuraciones equivalentes porque permutar los "ases" entre ellos no cambia nada, permutar los "dos" entre ellos tampoco cambia nada, y así sucesivamente. Por lo tanto, cada grupo de permutaciones que se ven idénticas cuando se ignoran los palos de las cartas contienepermutaciones Estos grupos, cuyo número viene dado por el coeficiente multinomialN N!=N×(N−1)×⋯×2×1 N k1 k2 k1!×k2!×⋯×km!
se llaman "combinaciones" de la baraja.
Hay otra forma de contar las combinaciones. ¡Las primeras cartas solo pueden formar combinación. Dejan "espacios" entre y alrededor de ellos en los que se pueden colocar las siguientes cartas. Podríamos indicar esto con un diagrama donde " " designa una de las tarjetas y " " designa una ranura que puede contener entre y tarjetas adicionales:k1 k1!/k1!=1 k1+1 k2 ∗ k1 _ 0 k2
Cuando se tarjetas adicionales, el patrón de estrellas y nuevas tarjetas divide las tarjetas en dos subconjuntos. El número de subconjuntos distintos es .k2 k1+k2 (k1+k2k1,k2)=(k1+k2)!k1!k2!
Repitiendo este procedimiento con "tres", encontramos que hay formas de intercalarlos entre las primeras cartas. Por lo tanto, el número total de formas distintas de organizar las primeras tarjetas de esta manera es igualk3 ((k1+k2)+k3k1+k2,k3)=(k1+k2+k3)!(k1+k2)!k3! k1+k2 k1+k2+k3
Después de terminar las últimas cartas y continuar multiplicando estas fracciones telescópicas, encontramos que el número de combinaciones distintas obtenidas es igual al número total de combinaciones contadas previamente, . Por lo tanto, no hemos pasado por alto ninguna combinación. Eso significa que este proceso secuencial de barajar las cartas captura correctamente las probabilidades de cada combinación, suponiendo que en cada etapa cada forma distinta posible de intercalar las nuevas cartas entre las viejas se tome con una probabilidad uniformemente igual.kn (Nk1,k2,…,km)
El proceso del lugar
Inicialmente, hay ases y obviamente el primero está marcado. En etapas posteriores hay tarjetas, el lugar (si existe una tarjeta marcada) es igual a (algún valor de a ), y estamos a punto de intercalar cartas a su alrededor. Podemos visualizar esto con un diagrama comok1 n=k1+k2+⋯+kj−1 p 1 n k=kj
donde " " designa el símbolo marcado actualmente. Condicional a este valor del lugar , deseamos encontrar la probabilidad de que el próximo lugar sea igual a (algún valor de a ; según las reglas del juego, el siguiente lugar debe venir después de , de donde ). Si podemos encontrar cuántas formas hay de intercalar las nuevas tarjetas en los espacios en blanco para que el siguiente lugar sea igual a , entonces podemos dividir por el número total de formas de intercalar estas cartas (igual a , como hemos visto) para obtener el⊙ p q 1 n+k p q≥p+1 k q (n+kk) probabilidad de transición de que el lugar cambie de a . (También habrá una probabilidad de transición para que el lugar desaparezca por completo cuando ninguna de las nuevas cartas siga a la carta marcada, pero no hay necesidad de calcular esto explícitamente).p q
Actualicemos el diagrama para reflejar esta situación:
La barra vertical " " muestra dónde aparece la primera carta nueva después de la carta marcada: por lo tanto, no pueden aparecer cartas nuevas entre el y el (y, por lo tanto, no se muestran espacios en ese intervalo). No sabemos cuántas estrellas hay en este intervalo, así que lo acabo de llamar (que puede ser cero). Lo desconocido desaparecerá una vez que encontremos la relación entre él y .| ⊙ | s s q
Supongamos, entonces, que intercalamos nuevas cartas alrededor de las estrellas antes del y luego, independientemente de eso, intercalamos las nuevas cartas restantes alrededor de las estrellas después del . Existenj ⊙ k−j−1 |
maneras de hacer esto. Tenga en cuenta, sin embargo, esta es la parte más complicada del análisis, que el lugar de es igual a porque| p+s+j+1
Por lo tanto, nos da información sobre la transición del lugar al lugar . Cuando rastreamos esta información cuidadosamente para todos los valores posibles de , y sumamos todas estas posibilidades (disjuntas), obtenemos la probabilidad condicional del lugar después del lugar ,τn,k(s,p) p q=p+s+j+1 s q p
donde la suma comienza en y termina en . (La longitud variable de esta suma sugiere que hay es poco probable que sea una fórmula cerrada en función de y , excepto en casos especiales).j=max(0,q−(n+1)) j=min(k−1,q−(p+1) n,k,q, p
El algoritmo
Inicialmente, existe la probabilidad que el lugar sea y la probabilidad que tenga cualquier otro valor posible en . Esto puede ser representado por un vector .1 1 0 2,3,…,k1 p1=(1,0,…,0)
Después de intercalar las siguientes tarjetas , el vector se actualiza a multiplicándolo (a la izquierda) por la matriz de transición . Esto se repite hasta que se hayan colocado tarjetas . En cada etapa , la suma de las entradas en el vector de probabilidad es la posibilidad de que se haya marcado alguna tarjeta. Lo que quede para hacer que el valor sea igual a por lo tanto, existe la posibilidad de que no quede ninguna tarjeta marcada después del pasok2 p1 p2 (Prk1,k2(q|p),1≤p≤k1,1≤q≤k2) k1+k2+⋯+km j pj 1 j . Por lo tanto, las diferencias sucesivas en estos valores nos dan la probabilidad de que no podamos encontrar una carta de tipo para marcar: esa es la distribución de probabilidad del valor de la carta que estábamos buscando cuando el mazo se agota al final del juego .j
Implementación
El siguiente(n+kk)
R
código implementa el algoritmo. Es paralela a la discusión anterior. Primero, el cálculo de las probabilidades de transición se realiza mediantet.matrix
(sin normalización con la división por , lo que facilita el seguimiento de los cálculos al probar el código):Esto lo utilizapj−1 pj p1
transition
para actualizar a . Calcula la matriz de transición y realiza la multiplicación. También se encarga de calcular el vector inicial si el argumento es un vector vacío:p
Ahora podemos calcular fácilmente las probabilidades sin marca en cada etapa para cualquier mazo:
Aquí están para el mazo estándar:
La salida es
Según las reglas, si se marcara un rey, no buscaríamos más cartas: esto significa que el valor de debe aumentarse a . Al hacerlo, las diferencias dan la distribución del "número en el que se encontrará cuando se acabe el mazo":0.9994461 1
(Compare esto con el resultado que informo en una respuesta separada que describe una simulación de Monte-Carlo: parecen ser los mismos, hasta las cantidades esperadas de variación aleatoria).
El valor esperado es inmediato:
En total, esto requirió solo una docena de líneas de código ejecutable. Lo he comparado con cálculos manuales para valores pequeños de (hasta ). Por lo tanto, si se observa alguna discrepancia entre el código y el análisis anterior del problema, confíe en el código (porque el análisis puede tener errores tipográficos).k 3
Observaciones
Relaciones con otras secuencias.
Cuando hay una de cada tarjeta, la distribución es una secuencia de recíprocos de números enteros:
El valor en el lugar es(comenzando en el lugar ). Esta es la secuencia A001048 en la Enciclopedia en línea de secuencias enteras . En consecuencia, podríamos esperar una fórmula cerrada para los mazos con constante (los mazos "adecuados") que generalizaría esta secuencia, que tiene algunos significados profundos. (Por ejemplo, cuenta los tamaños de las clases de conjugación más grandes en los grupos de permutación y también está relacionado con los coeficientes trinomiales ). (Desafortunadamente, los recíprocos en la generalización para no suelen ser enteros).i i!+(i−1)! i=1 ki k>1
El juego como proceso estocástico
Nuestro análisis deja en claro que los coeficientes iniciales de los vectores , , son constantes. Por ejemplo, rastreemos la salida de mientras procesa cada grupo de tarjetas:i pj j≥i
game
...
Por ejemplo, el segundo valor del vector final (que describe los resultados con un mazo completo de 52 cartas) ya apareció después de que se procesó el segundo grupo (y es igual a ). Por lo tanto, si desea información solo sobre las marcas a través del valor de la tarjeta , solo tiene que realizar el cálculo para un mazo de cartas .1/(84)=1/70 jth k1+k2+⋯+kj
Debido a que la posibilidad de no marcar una carta de valor se acerca rápidamente a medida que aumenta, después de tipos de cartas en cuatro palos casi hemos alcanzado un valor límite para la expectativa. De hecho, el valor límite es de aproximadamente (calculado para un mazo de cartas, en cuyo punto el error de redondeo de doble precisión evita ir más allá).j 1 j 13 5.833355 4×32
Sincronización
Al observar el algoritmo aplicado al vector , vemos que su sincronización debe ser proporcional a y, usando un límite superior bruto, no es peor que proporcional a . Por temporización todos los cálculos para a través de y a través de , y el análisis de solamente aquellos que toman tiempos relativamente largos ( segundo o más), calculo el tiempo de cálculo es de aproximadamente , apoyando esta evaluación de límite superior.( k , k , ... , k ) k 2 m 3 k = 1 7 n = 10 30 1 / 2 O ( k 2 n 2.9 )m (k,k,…,k) k2 m3 k=1 7 n=10 30 1/2 O(k2n2.9)
Un uso de estas asintóticas es proyectar tiempos de cálculo para problemas mayores. Por ejemplo, viendo que el caso toma aproximadamente segundos, estimaríamos que el caso (muy interesante) tomaría aproximadamente segundos. (En realidad, toma segundos).1,31 k = 1 , n = 100 1,31 ( 1 / 4 ) 2 ( 100 / 30 ) 2,9 ≈ 2,7 2,87k=4,n=30 1.31 k=1,n=100 1.31(1/4)2(100/30)2.9≈2.7 2.87
fuente
Hackeó un simple Monte Carlo en Perl y encontró aproximadamente .5.8329
fuente