Quantas vezes você precisa rolar um dado de 6 lados para obter todos os números pelo menos uma vez?

Acabei de jogar um jogo com meus filhos que basicamente se resume a: quem joga todos os números pelo menos uma vez em um dado de 6 lados ganha.

Ganhei, eventualmente, e os outros terminaram 1-2 turnos depois. Agora estou me perguntando: qual é a expectativa da duração do jogo?

Eu sei que a expectativa do número de jogadas até você atingir um número específico é .$\sum_{n=1}^\infty n\frac{1}{6}(\frac{5}{6})^{n-1}=6$

No entanto, tenho duas perguntas:

1. Quantas vezes você precisa rolar um dado de seis lados até obter todos os números pelo menos uma vez?
2. Entre quatro tentativas independentes (ou seja, com quatro jogadores), qual é a expectativa do número máximo de jogadas necessário? [nota: é o máximo, não o mínimo, porque na idade deles, trata-se mais de terminar do que de chegar primeiro para os meus filhos]

Posso simular o resultado, mas me pergunto como procederia para calculá-lo analiticamente.

---

Aqui está uma simulação de Monte Carlo no 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)

Como uma "abordagem completamente analítica" foi solicitada, aqui está uma solução exata. Ele também fornece uma abordagem alternativa para resolver a questão no Probability de desenhar uma bola preta em um conjunto de bolas preto e branco com condições de substituição mistas .

---

O número de jogadas no jogo, , pode ser modelado como a soma de seis realizações independentes de variáveis geométricas com probabilidades , cada uma delas deslocada por (porque uma variável geométrica conta apenas as jogadas anteriores a um sucesso e também devemos contar as jogadas nas quais os sucessos foram observados). Ao computar com a distribuição geométrica, obteremos respostas inferiores às desejadas e, portanto, não se esqueça de adicionar no final.$X$$(p)$$p=1, 5/6, 4/6, 3/6, 2/6, 1/6$$1$6 6$6$$6$

A função geradora de probabilidade (pgf) de uma variável geométrica com o parâmetro é$p$

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

Portanto, o pgf para a soma dessas seis variáveis ​​é

$$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).$$

(O produto pode ser calculado neste formulário fechado, separando-o em cinco termos por meio de frações parciais.)

A função de distribuição cumulativa (CDF) é obtida a partir das somas parciais de (como uma série de potências em ), que equivale à soma de séries geométricas, e é 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).$$

(Eu escrevi essa expressão de uma forma que sugere uma derivação alternativa por meio do Princípio da inclusão-exclusão.)

A partir disso, obtemos o número esperado de jogadas no jogo (respondendo à primeira pergunta) como

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

O CDF do máximo de versões independentes de é (e, a partir disso, podemos, em princípio, responder a quaisquer perguntas de probabilidade sobre o máximo que gostamos, como qual é sua variação, qual é o seu percentil 99 , e assim por diante). Com , obtemos uma expectativa de$m$$X$$F(z)^m$$m=4$

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

(O valor é uma fração racional que, na forma reduzida, possui um denominador de 71 dígitos.) O desvio padrão é Aqui está um gráfico da função de massa probabilística do máximo para quatro jogadores (ela já foi alterada por ):$6.77108\ldots.$$6$

Como seria de esperar, é positivamente distorcido. O modo está em rolos. É raro que a última pessoa a terminar leve mais de rolos (é cerca de ).$18$$50$$0.3\%$

O ThePawn tem a ideia certa de atacar o problema com um relacionamento de recorrência. Considere uma cadeia de Markov com os estados correspondentes à contagem do número de jogadas de dados distintas que ocorreram. O estado 0 é o estado inicial e o estado 6 é o estado final. Então, a probabilidade de transição do estado para si é . A probabilidade de transição do estado para o estado é . Portanto, o tempo de acerto do estado final é $\{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 o máximo de quatro tentativas, considere estados quádruplos. Você deseja encontrar o tempo de acerto esperado para o estado de destino . O tempo de acerto esperado de qualquer estado é a média ponderada de cada estado de origem do tempo de acerto esperado mais o tempo de ir de para , ponderado por , a probabilidade de chegar ao estado mudar para$(6,6,6,6)$$j$$i$$T_i$$i$$j$$p_ip_{ij}$$i$$j$. Você pode descobrir os tempos e as probabilidades de acerto através da programação dinâmica. Não é tão difícil, pois existe uma ordem transversal para preencher os tempos e as probabilidades de acerto. Por exemplo, para dois dados: primeiro calcule T ep para (0,0), depois para (1,0), depois (1, 1), (2, 0), depois (2, 1), etc.

Em 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])

Estimativa rápida e suja de Monte Carlo em R da duração de um jogo para 1 jogador:

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: , , portanto, um intervalo de confiança de 95% para a média é .$\hat{\mu}=14.684$$\hat{\sigma} = 6.24$$[14.645,14.722]$

Para determinar a duração de um jogo para quatro jogadores, podemos agrupar as amostras em quatro e ter a duração mínima média de cada grupo (você perguntou sobre o máximo, mas suponho que você quis dizer o mínimo, pois, pelo que li, o o jogo termina quando alguém consegue obter todos os números):

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

Resultados: , ; portanto, um intervalo de confiança de 95% para a média é .$\hat{\mu}=9.44$$\hat{\sigma} = 2.26$$[9.411,9.468]$

Que tal uma relação recursiva em relação ao número remanescente de lados que você precisa obter para vencer.$m$

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

Basicamente, a última relação está dizendo que o número de tempo para rolar os números diferentes restantes é igual a mais:$m$$1$

• 6 - m 6 - $T_{m}$ se você rolar um dos números de já rolados (probabilidade )$6 - m$$\frac{6 - m}{6}$
• m $T_{m-1}$ se você rolar um dos números restantes (probabilidade )$m$$\frac{m}{6}$

A aplicação numérica dessa relação fornece .$14.7$

Uma explicação simples e intuitiva para a primeira pergunta:

Você primeiro precisa rolar qualquer número. Isso é fácil, sempre leva exatamente 1 rolo.

Você precisa rolar qualquer número diferente do primeiro. A chance de isso acontecer é ; portanto, serão necessários (1,2) testes em média.$\frac{5}{6}$$\frac{6}{5}$

Você precisará rolar qualquer número que não seja os dois primeiros. A chance de isso acontecer é ; portanto, serão necessários (1,5) testes em média.$\frac{4}{6}$$\frac{6}{4}$

Você precisa rolar qualquer número que não seja os três primeiros. A chance de isso acontecer é , portanto, levará (2) testes em média.$\frac{3}{6}$$\frac{6}{3}$

E assim sucessivamente, até concluirmos com êxito nosso sexto rolo:

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

Essa resposta é semelhante à resposta de Neil G, apenas, sem a cadeia markov.

a função densidade de probabilidade (ou equivalente discreto) para obter o próximo número novo é:

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

onde p é a probabilidade por rolagem, 1 quando nenhum número foi rolado, 5/6 após 1, 4/6. até 1/6 no último número

o valor esperado, mu = soma (i * p * (1 - p) ^ (i - 1), i = 1 .. inf) deixando n = i - 1 e colocando p fora da soma,

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

mu = p * soma (n (1-p) ^ n, n = 0 .. inf) + p * soma ((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

A soma dos valores esperados (mus) para ps de 1, 5/6, 4/6, 3/6, 2/6 e 1/6 é 14,7 conforme relatado anteriormente, mas 1 / p por número necessário é geral, independentemente do tamanho da matriz

Da mesma forma, podemos calcular o desvio padrão analiticamente

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

Vou poupar a álgebra aqui, mas sigma ^ 2 = (1-p) / p ^ 2

No caso de 6, a soma de sigma ^ 2 para cada etapa é 38,99 para um desvio padrão de cerca de 6,24, novamente, como simulado

A pergunta 1 foi:

Quantas vezes você tem que jogar um dado de seis lados até obter todos os números pelo menos uma vez?

Obviamente, a resposta correta deve ser "infinita".