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

41

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 é .n=1n16(56)n1=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)
Jonas
fonte
11
O problema do colecionador de cupons também pode ser visto - o Google go fornece muitos mais hits e mais informações. Tente também pesquisar sobre isso aqui em stats.SE .
Glen_b
1
@Glen_b: Obrigado, eu não sabia esse nome!
Jonas
1
@ whuber: Não sei se essa pergunta deveria ter sido encerrada. Ele quer o tempo mínimo esperado de quatro tentativas. Eu estava prestes a corrigir minha resposta para a solução de programação dinâmica.
Neil G
2
@whuber: Vou editar meu post para esclarecer
Jonas

Respostas:

22

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/616 666

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

f(z,p)=p1(1p)z.

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

g(z)=i=16f(z,i/6)=6z4(5 2z+5+10 3z+45 4z+4+5z+4+5).

(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 porgz

F(z)=6z4((1) 1z+4+(5) 2z+4(10) 3z+4+(10) 4z+4(5) 5z+4+(1) 6z+4).

(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

E(6+X)=6+i=1(1F(i))=14710.

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 demXF(z)mm=4

6+i=1(1F(i)4)21.4820363.

(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.6

Figura

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

whuber
fonte
Este método de solução foi inspirado pela observação de que somas de variáveis ​​geométricas são misturas (possivelmente com pesos negativos) de variáveis ​​geométricas com os mesmos parâmetros. Uma relação semelhante ocorre entre as variáveis ​​gama (com diferentes parâmetros de taxa). Peço desculpas por fazer o trabalho no Mathematica, mas tenho certeza de que o Matlab também pode executar esses cálculos :-).
whuber
2
Esta é a resposta que eu estava esperando. Muito obrigado! Eu acho que eu deveria ser capaz de calcular os resultados numéricos em Matlab :)
Jonas
Como relaciona com a distribuição de massa de probabilidade da distribuição geométrica? De onde vem o produto ? Eu entendo o significado de , mas qual é o significado de ? f(z,p)=p1(1p)zi=16f(z,i/6)F(z)g(z)
Sextus Empiricus 14/03
1
Vejo agora que é a função geradora de probabilidade . f(z,p)
Sextus Empiricus 14/03
@MartijnWeterings Obrigado - acredito que esse é o termo mais preciso e convencional. (Você pode dizer que eu tendem a pensar no pmf e no pgf como quase a mesma coisa, devido ao longo hábito de usar funções de geração.) Vou mudar a terminologia neste post.
whuber
13

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,,6}ii6ii+16i6

i=0566i=14.7

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)jiTiijpipijij. 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])
Neil G
fonte
1
Você perdeu o número máximo esperado de jogadas em quatro repetições independentes do jogo.
probabilityislogic
Ah, eu acabei de perceber isso. Eu acho que você quer dizer mínimo, mas sim.
Neil G
@ NeilG: Na verdade, quero dizer máximo (veja minha pergunta atualizada), embora eu assuma que a estratégia seja a mesma para min e max. Você pode elaborar a estratégia de programação dinâmica?
Jonas
@ Jonas: atualizado para o máximo. Tenho muito trabalho, mas talvez eu possa codificar isso para você mais tarde.
Neil G
2
@ NeilG: Obrigado. Eu esperava obter uma abordagem completamente analítica, mas o código DP também é bastante instrutivo.
Jonas
6

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 é .μ^=14.684σ^=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 é .μ^=9.44σ^=2.26[9.411,9.468]

bnaul
fonte
1
Cheguei a um resultado muito semelhante com uma simulação do Matlab, mas estava curioso sobre como resolver isso analiticamente. Além disso, desde que eu brinco com meus filhos, todos eles querem terminar o jogo, independentemente de quem ganha, então eu quero perguntar sobre o máximo.
Jonas
5

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

T1=6
Tm=1+6m6Tm+m6Tm1

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

  • 6 - m 6 - mTm se você rolar um dos números de já rolados (probabilidade )6m6m6
  • m mTm1 se você rolar um dos números restantes (probabilidade )mm6

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

ThePawn
fonte
Algo parece errado com esta resposta. Não deveria ser um resumo no final? . Ti=Ti1+66i+1
Neil G
1
Sim, desculpe, cometi um erro, estou corrigindo
#
Espero que você não se importe de ter adicionado uma resposta. 14,7 é correto, mas a relação de recorrência ainda é falho ...
Neil G
Não tem problema, deveria ter sido cuidadoso na primeira vez :). Sua resposta é ótima.
precisa saber é
5

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. 65665

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. 64664

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. 63663

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

66+65+64+63+62+61=14.7 rolls

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


fonte
1

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

MikeP
fonte
-4

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".

Stef van Buuren
fonte
6
Isso responderia à pergunta "garantir com absoluta certeza que todos os números fossem obtidos pelo menos uma vez". Para a pergunta que foi feita, a resposta é uma variável aleatória, cuja distribuição pode ser bem aproximada.
Glen_b