¿Con qué frecuencia tienes que tirar un dado de 6 lados para obtener cada número al menos una vez?

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

Finalmente gané, y los otros 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 lanzamientos hasta que llegue 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 tirar un dado de seis lados hasta que obtengas todos los números al menos una vez?
2. Entre cuatro pruebas independientes (es decir, con cuatro jugadores), ¿cuál es la expectativa del número máximo de tiradas necesarias? [nota: es máximo, no mínimo, porque a su edad, se trata más de terminar que de llegar primero para mis hijos]

Puedo simular el resultado, pero me pregunto cómo haría para calcularlo 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)

Debido a que se ha solicitado un "enfoque completamente analítico", aquí hay una solución exacta. También proporciona un enfoque alternativo para resolver la pregunta en Probabilidad de dibujar una bola negra en un conjunto de bolas blancas y negras con condiciones de reemplazo mixtas .

---

El número de movimientos en el juego, , se puede modelar como la suma de seis realizaciones independientes de variables geométricas con probabilidades , cada uno de ellos desplazado por (porque una variable geométrica cuenta solo las tiradas que preceden a un éxito y también debemos contar las tiradas en las que se observaron éxitos). Al calcular con la distribución geométrica, obtendremos respuestas que son menos que las deseadas y, por lo tanto, debemos asegurarnos de agregar al final.$X$$(p)$$p=1, 5/6, 4/6, 3/6, 2/6, 1/6$$1$6 6$6$$6$

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

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

Por lo tanto, el 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 se puede calcular en esta forma cerrada separándolo en cinco términos mediante fracciones parciales).

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

$$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 del Principio de inclusión-exclusión).

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

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

El CDF del máximo de versiones independientes de es (y de esto podemos, en principio, responder cualquier pregunta de probabilidad sobre el máximo que nos gusta, como cuál es su varianza, cuál es su percentil 99 , y así). Con obtenemos una expectativa de$m$$X$$F(z)^m$$m=4$

$$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 estándar es Aquí hay una gráfica de la función de masa de probabilidad del máximo para cuatro jugadores (ya ha sido desplazada por ):$6.77108\ldots.$$6$

Como cabría esperar, está positivamente sesgado. El modo es a rollos. Es raro que la última persona que termine tome más de rollos (es aproximadamente ).$18$$50$$0.3\%$

ThePawn tiene la idea correcta de atacar el problema con una relación recurrente. Considere una cadena de Markov con estados correspondientes a la cuenta del número de tiradas de dados distintas que han sucedido. El estado 0 es el estado inicial y el estado 6 es el estado final. Entonces, la probabilidad de transición del estado a sí mismo es . La probabilidad de transición del estado al estado es . Por lo tanto, el tiempo de llegada del estado final es $\{0, \dotsc, 6\}$$i$$\frac{i}{6}$$i$$i+1$$\frac{6-i}{6}$

$$\begin{align} \sum_{i=0}^5 \frac{6}{6-i} = 14.7 \end{align}$$

Para el máximo de cuatro ensayos, considere los estados que son cuádruples. Desea encontrar el tiempo de golpe esperado para el estado objetivo . El tiempo de golpe esperado de cualquier estado es el promedio ponderado para cada estado fuente del tiempo de golpe esperado más el tiempo para ir de a , ponderado por , la probabilidad de llegar al estado y moverse a$(6,6,6,6)$$j$$i$$T_i$$i$$j$$p_ip_{ij}$$i$$j$. Puede descubrir los tiempos de golpe y las probabilidades mediante programación dinámica. No es tan difícil ya que hay un orden transversal para completar los tiempos de golpe y las probabilidades. Por ejemplo, para dos dados: primero calcule 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])

Estimación rápida y sucia de Monte Carlo en R de la duración de un juego 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: , , por lo que un intervalo de confianza del 95% para la media es .$\hat{\mu}=14.684$$\hat{\sigma} = 6.24$$[14.645,14.722]$

Para determinar la duración de un juego de cuatro jugadores, podemos agrupar las muestras en cuatro y tomar la longitud mínima promedio sobre cada grupo (usted preguntó sobre el máximo, pero supongo que se refería al mínimo ya que, según lo leí, el el juego termina cuando alguien logra obtener todos los números):

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

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

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

T m = 1 + 6 -

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

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

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

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

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

Primero necesitas rodar cualquier número. Esto es fácil, siempre tomará exactamente 1 rollo.

Luego debe rodar cualquier número que no sea el primero. La probabilidad de que esto suceda es , por lo que tomará (1.2) rollos en promedio.$\frac{5}{6}$$\frac{6}{5}$

A continuación, debe rodar cualquier número que no sean los dos primeros. La posibilidad de que esto suceda es , por lo que tomará (1.5) rollos en promedio.$\frac{4}{6}$$\frac{6}{4}$

A continuación, debe rodar cualquier número que no sean los primeros tres. La probabilidad de que esto suceda es , por lo que tomará (2) tiradas en promedio.$\frac{3}{6}$$\frac{6}{3}$

Y así sucesivamente hasta completar con éxito nuestro sexto rollo:

$\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 respuesta de Neil G, solo, sin la cadena de Markov.

La función de densidad de probabilidad (o equivalente discreto) para obtener el siguiente número nuevo es:

f = suma (p * (1 - p) ^ (i - 1), i = 1 .. inf)

donde p es la probabilidad por tirada, 1 cuando no se han lanzado números, 5/6 después de 1, 4/6 .. hasta 1/6 para el último número

el valor esperado, mu = suma (i * p * (1 - p) ^ (i - 1), i = 1 .. inf) dejando n = i - 1, y llevando p fuera de la suma,

mu = p * suma ((n + 1) * (1 - p) ^ n, n = 0 .. inf)

mu = p * sum (n (1-p) ^ n, n = 0 .. inf) + p * sum ((1-p) ^ n, n = 0 .. inf) mu = p * (1-p ) / (1-p-1) ^ 2 + p * 1 / (1- (1-p))

mu = p * (1 - p) / p ^ 2 + p / p

mu = (1 - p) / p + p / p

mu = (1 - p + p) / p

mu = 1 / p

La suma de los valores esperados (mus) para ps de 1, 5/6, 4/6, 3/6, 2/6 y 1/6 es 14.7 como se informó anteriormente, pero 1 / p por número requerido es general independientemente del tamaño del dado

Del mismo modo, podemos calcular la desviación estándar analíticamente

sigma ^ 2 = suma ((i - mu) ^ 2 * p * (1 - p) ^ (i - 1), i = 1 .. inf)

Te ahorraré el álgebra aquí, pero sigma ^ 2 = (1-p) / p ^ 2

En el caso de 6, la suma de sigma ^ 2 para cada paso es 38.99 para una desviación estándar de aproximadamente 6.24, nuevamente, como se simula

La pregunta 1 fue:

¿Cuántas veces tienes que tirar un dado de seis lados hasta que obtengas todos los números al menos una vez?

Obviamente, la respuesta correcta debe ser 'infinita'.