¿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

La función de densidad de probabilidad (o su 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 han salido 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 sacando p fuera de la suma,

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

mu = p * suma( n(1-p)^n, n = 0 .. inf ) + p * suma( (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 los ps de 1, 5/6, 4/6, 3/6, 2/6 y 1/6 es de 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 de forma analítica

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 de 38,99 para una desviación estándar de aproximadamente 6,24, de nuevo, como se ha simulado

Answer 2

La pregunta 1 era:

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

Obviamente, la respuesta correcta debe ser "infinito".