¿Cuántas veces tienes que tirar un dado de 6 caras para obtener cada número al menos una vez?

Question

Acabo de jugar con mis hijos a un juego que básicamente se reduce a: quien saque cada número al menos una vez en un dado de 6 caras, gana.

Gané, finalmente, y los demás terminaron 1-2 turnos después. Ahora me pregunto: ¿cuál es la expectativa de la duración del juego?

Sé que la expectativa del número de tiradas hasta llegar a un número específico es $\sum_{n=1}^\infty n\frac{1}{6}(\frac{5}{6})^{n-1}=6$ .

Sin embargo, tengo dos preguntas:

1. ¿Cuántas veces tienes que lanzar un dado de seis caras hasta que consigas todos los números al menos una vez?
2. Entre cuatro ensayos independientes (es decir, con cuatro jugadores), ¿cuál es la expectativa del máximo ¿número de rollos necesarios? [nota: es el máximo, no el mínimo, porque a su edad, para mis hijos se trata más de terminar que de llegar primero]

Puedo simular el resultado, pero me pregunto cómo lo calcularía analíticamente.

---

Aquí hay una simulación de Monte Carlo en Matlab

mx=zeros(1000000,1);
for i=1:1000000,
   %# assume it's never going to take us >100 rolls
   r=randi(6,100,1);
   %# since R2013a, unique returns the first occurrence
   %# for earlier versions, take the minimum of x
   %# and subtract it from the total array length
   [~,x]=unique(r); 
   mx(i,1)=max(x);
end

%# make sure we haven't violated an assumption
assert(numel(x)==6)

%# find the expected value for the coupon collector problem
expectationForOneRun = mean(mx)

%# find the expected number of rolls as a maximum of four independent players
maxExpectationForFourRuns = mean( max( reshape( mx, 4, []), [], 1) )

expectationForOneRun =
   14.7014 (SEM 0.006)

maxExpectationForFourRuns =
   21.4815 (SEM 0.01)

Answer 1

Porque se ha solicitado un "enfoque completamente analítico", aquí hay una solución exacta. También ofrece un enfoque alternativo para resolver la cuestión en Probabilidad de sacar una bola negra en un conjunto de bolas negras y blancas con condiciones de sustitución mixtas .

---

El número de movimientos en el juego, $X$ se puede modelar como la suma de seis realizaciones independientes de la Geometría $(p)$ variables con probabilidades $p=1, 5/6, 4/6, 3/6, 2/6, 1/6$ cada uno de ellos desplazado por $1$ (porque una variable geométrica sólo cuenta las tiradas anterior un éxito y debemos contar también las tiradas en las que se observaron éxitos). Por lo tanto, al calcular con la distribución geométrica, obtendremos respuestas que son $6$ menos que los deseados y, por lo tanto, debe asegurarse de añadir $6$ al final.

El función generadora de probabilidad (pgf) de tal variable geométrica con el parámetro $p$ es

$$f(z, p) = \frac{p}{1-(1-p)z}.$$

Por lo tanto, la pgf para la suma de estas seis variables es

$$g(z) = \prod_{i=1}^6 f(z, i/6) = 6^{-z-4} \left(-5\ 2^{z+5}+10\ 3^{z+4}-5\ 4^{z+4}+5^{z+4}+5\right).$$

(El producto puede calcularse en esta forma cerrada separándolo en cinco términos a través de fracciones parciales).

La función de distribución acumulativa (FDA) se obtiene a partir de las sumas parciales de $g$ (como una serie de potencias en $z$ ), que equivale a sumar series geométricas, y viene dada por

$$F(z) = 6^{-z-4} \left(-(1)\ 1^{z+4} + (5)\ 2^{z+4}-(10)\ 3^{z+4}+(10)\ 4^{z+4}-(5)\ 5^{z+4}+(1)\ 6^{z+4}\right).$$

(He escrito esta expresión en una forma que sugiere una derivación alternativa a través de el Principio de Inclusión-Exclusión).

A partir de esto obtenemos el número esperado de movimientos en el juego (respondiendo a la primera pregunta) como

$$\mathbb{E}(6+X) = 6+\sum_{i=1}^\infty \left(1-F(i)\right) = \frac{147}{10}.$$

La FCD del máximo de $m$ versiones independientes de $X$ es $F(z)^m$ (y a partir de esto podemos, en principio, responder a cualquier pregunta de probabilidad sobre el máximo que queramos, como cuál es su varianza, cuál es su percentil 99, etc.). Con $m=4$ obtenemos una expectativa de

$$ 6+\sum_{i=1}^\infty \left(1-F(i)^4\right) \approx 21.4820363\ldots.$$

(El valor es una fracción racional que, en forma reducida, tiene un denominador de 71 dígitos). La desviación típica es $6.77108\ldots.$ Aquí se muestra un gráfico de la función de masa de probabilidad del máximo para cuatro jugadores (se ha desplazado por $6$ ya):

Como era de esperar, está sesgado positivamente. La moda está en $18$ rollos. Es raro que la última persona en terminar se lleve más de $50$ rollos (se trata de $0.3\%$ ).

Answer 2

ThePawn tiene la idea correcta de atacar el problema con una relación de recurrencia. Consideremos una cadena de Markov con estados $\{0, \dotsc, 6\}$ correspondiente al recuento del número de tiradas de dados distintas que se han producido. El estado 0 es el estado inicial y el estado 6 es el estado final. Entonces, la probabilidad de transición del estado $i$ a sí mismo es $\frac{i}{6}$ . La probabilidad de transición del estado $i$ al estado $i+1$ es $\frac{6-i}{6}$ . Por lo tanto, el tiempo de golpeo del estado final es \begin{align} \sum_{i=0}^5 \frac{6}{6-i} = 14.7 \end{align}

Para el máximo de cuatro ensayos, considera los estados que son cuádruples. Se quiere encontrar el tiempo de acierto esperado para el estado objetivo $(6,6,6,6)$ . El tiempo esperado de llegada de cualquier estado $j$ es la media ponderada de cada estado fuente $i$ del tiempo de golpeo esperado $T_i$ más el tiempo para ir de $i$ a $j$ ponderado por $p_ip_{ij}$ la probabilidad de llegar al estado $i$ y se trasladan a $j$ . Puedes descubrir los tiempos y probabilidades de acierto mediante programación dinámica. No es tan difícil ya que hay un orden de recorrido para rellenar los tiempos de acierto y las probabilidades. Por ejemplo, para dos dados: primero calcula T y p para (0,0), luego para (1,0), luego (1, 1), (2, 0), luego (2, 1), etc.

En Python:

import numpy as np
import itertools as it
from tools.decorator import memoized  # A standard memoization decorator

SIDES = 6

@memoized
def get_t_and_p(state):
    if all(s == 0 for s in state):
        return 0, 1.0
    n = len(state)
    choices = [[s - 1, s] if s > 0 else [s]
               for s in state]
    ts = []
    ps = []
    for last_state in it.product(*choices):
        if last_state == state:
            continue
        last_t, last_p = get_t_and_p(tuple(sorted(last_state)))
        if last_p == 0.0:
            continue
        transition_p = 1.0
        stay_p = 1.0
        for ls, s in zip(last_state, state):
            if ls < s:
                transition_p *= (SIDES - ls) / SIDES
            else:
                transition_p *= ls / SIDES
            stay_p *= ls / SIDES
        if transition_p == 0.0:
            continue
        transition_time = 1 / (1 - stay_p)
        ts.append(last_t + transition_time)
        ps.append(last_p * transition_p / (1 - stay_p))
    if len(ts) == 0:
        return 0, 0.0
    t = np.average(ts, weights=ps)
    p = sum(ps)
    return t, p

print(get_t_and_p((SIDES,) * 4)[0])

Answer 3

Estimación rápida y sucia de Monte Carlo en R de la duración de una partida para 1 jugador:

N = 1e5
sample_length = function(n) { # random game length
    x = numeric(0)
    while(length(unique(x)) < n) x[length(x)+1] = sample(1:n,1)
    return(length(x))
}
game_lengths = replicate(N, sample_length(6))

Resultados: $\hat{\mu}=14.684$ , $\hat{\sigma} = 6.24$ por lo que un intervalo de confianza del 95% para la media es $[14.645,14.722]$ .

Para determinar la duración de una partida de cuatro jugadores, podemos agrupar las muestras en cuatros y tomar la media de la duración mínima de cada grupo (has preguntado por la máxima, pero supongo que te referías a la mínima, ya que, tal y como lo he leído, la partida termina cuando alguien consigue obtener todos los números):

grouped_lengths = matrix(game_lengths, ncol=4)
min_lengths = apply(grouped_lengths, 1, min)

Resultados: $\hat{\mu}=9.44$ , $\hat{\sigma} = 2.26$ por lo que un intervalo de confianza del 95% para la media es $[9.411,9.468]$ .

Answer 4

¿Qué tal una relación recursiva con respecto al número restante $m$ de lados que tienes que obtener para ganar.

$$T_{1} = 6$$ $$T_{m} = 1 + \frac{6 - m}{6}T_{m} + \frac{m}{6}T_{m-1}$$

Básicamente, la última relación está diciendo que el número de tiempo para rodar el $m$ los restantes números diferentes es igual a $1$ más:

• $T_{m}$ si tira el de la $6 - m$ números ya lanzados (probabilidad $\frac{6 - m}{6}$ )
• $T_{m-1}$ si tira uno de los $m$ números restantes (probabilidad $\frac{m}{6}$ )

La aplicación numérica de esta relación da como resultado $14.7$ .

Answer 5

Una explicación sencilla e intuitiva a la primera pregunta:

Primero tienes que sacar un número cualquiera. Esto es fácil, siempre tomará exactamente 1 rollo.

A continuación, tienes que sacar cualquier número que no sea el primero. La probabilidad de que esto ocurra es $\frac{5}{6}$ , por lo que se necesitará $\frac{6}{5}$ (1,2) rollos de media.

A continuación, tienes que tirar cualquier número que no sean los dos primeros. La probabilidad de que esto ocurra es $\frac{4}{6}$ , por lo que se necesitará $\frac{6}{4}$ (1,5) rollos de media.

A continuación, tienes que tirar cualquier número que no sean los tres primeros. La probabilidad de que esto ocurra es $\frac{3}{6}$ , por lo que se necesitará $\frac{6}{3}$ (2) rollos de media.

Y así sucesivamente hasta completar con éxito la sexta tirada:

$\frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} = 14.7\ rolls$

Esta respuesta es similar a la de Neil G, sólo que sin la cadena de Markov.