Qual é o número esperado de vezes que você deve rolar um dado até que cada lado apareça 3 vezes?
Esta pergunta foi feita na escola primária da Nova Zelândia e foi resolvida usando simulações. Qual é a solução analítica para esse problema?
probability
multinomial
negative-binomial
coupon-collector-problem
Edgar Santos
fonte
fonte
Respostas:
Suponha que todos os ladosd=6 tenham chances iguais. Vamos generalizar e encontrar o número esperado de rolagens necessárias até que o lado 1 apareça n1 vezes, o lado 2 apareça n2 vezes, ... e o lado d apareça nd vezes. Como as identidades dos lados não importam (todas têm chances iguais), a descrição desse objetivo pode ser condensada: suponhamos que i0 lados não precisam aparecer, i1 dos lados precisa aparecer apenas uma vez, ... e in dos lados deve aparecer n = max ( n1 1, n2, … , Nd) vezes. Seja
Uma recorrência fácil está disponível. Na próxima rodada, o lado que aparece corresponde a um dos : isto é, ou não precisa vê-lo, ou que precisávamos para vê-lo uma vez, ..., ou que precisávamos para vê-lo n mais vezes. j é o número de vezes que precisávamos vê-lo.Euj n j
Quando , não precisamos vê-lo e nada muda. Isso acontece com probabilidade i 0 / d .j = 0 Eu0 0/ d
Quando , precisávamos ver esse lado. Agora, há um lado a menos que precisa ser visto j vezes e outro lado que precisa ser visto j - 1 vezes. Assim, i j se torna i j - 1 e i j - 1 se torna i j + 1 . Deixe esta operação nos componentes de i ser designada i ⋅ j , para quej > 0 j j−1 ij ij−1 ij−1 ij+1 i i⋅j
Isso acontece com a probabilidade .ij/d
Nós apenas temos que contar esse teste e usar a recursão para nos dizer quantos mais testes são esperados. Pelas leis da expectativa e probabilidade total,
(Let's understand that wheneverij=0 , the corresponding term in the sum is zero.)
Ifi0=d , we are done and e(i)=0 . Otherwise we may solve for e(i) , giving the desired recursive formula
Notice that
I compute that
That seemed awfully small to me, so I ran a simulation (using32.669 . The standard error of that estimate is 0.027 : the difference between this average and the theoretical value is insignificant, confirming the accuracy of the theoretical value.
R
). After over three million rolls of the dice, this game had been played to its completion over 100,000 times, with an average length ofThe distribution of lengths may be of interest. (Obviously it must begin at18 , the minimum number of rolls needed to collect all six sides three times each.)
Implementation
Although the recursive calculation ofe is simple, it presents some challenges in some computing environments. Chief among these is storing the values of e(i) as they are computed. This is essential, for otherwise each value will be (redundantly) computed a very large number of times. However, the storage potentially needed for an array indexed by i could be enormous. Ideally, only values of i that are actually encountered during the computation should be stored. This calls for a kind of associative array.
To illustrate, here is workingi are converted to strings and those are used to index into a list i⋅j operation is implemented as
R
code. The comments describe the creation of a simple "AA" (associative array) class for storing intermediate results. VectorsE
that will hold all the values. The%.%
.These preliminaries enable the recursive functione to be defined rather simply in a way that parallels the mathematical notation. In particular, the line
R
O tempo mostra que é preciso0.01 seconds to compute
e(c(0,0,0,6))
; its value isAccumulated floating point roundoff error has destroyed the last two digits (which should be
68
rather than06
).Finalmente, aqui está a implementação original do Mathematica que produziu a resposta exata. A memorização é realizada através da
e[i_] := e[i] = ...
expressão idiomática , eliminando quase todas asR
preliminares. Internamente, porém, os dois programas estão fazendo as mesmas coisas da mesma maneira.fonte
A versão original desta pergunta começou a vida perguntando:
Obviamente, essa é uma pergunta que não tem resposta como o @JuhoKokkala comentou acima: a resposta é uma variável aleatória com uma distribuição que precisa ser encontrada. A pergunta foi modificada para perguntar: "Qual é o número esperado de rolagens". A resposta abaixo procura responder à pergunta original: como encontrar a distribuição do número de rolos , sem usar simulação, e apenas usando técnicas conceitualmente simples que qualquer estudante da Nova Zelândia com um computador poderia implementar→ Why not? The problem reduces to a 1-liner.
Distribution of the number of rolls required ... such that each side appears 3 times
We roll a dien times. Let Xi denote the number of times side i of the die appears, where i∈{1,…,6} . Then, the joint pmf of (X1,X2,…,X6) is Multinomial(n,16) i.e.:
Let:N=min{n:Xi≥3∀i}. Then the cdf of N is: P(N≤n)=P(X∀i≥3∣∣n)
i.e. To find the cdfP(N≤n) , simply calculate for each value of n={18,19,20,…} :
Here, for example, is Mathematica code that does this, asn increases from 18 to say 60. It is basically a one-liner:
... which yields the exact cdf asn increases:
Here is a plot of the cdfP(N≤n) , as a function of n :
To derive the pmfP(N=n) , simply first difference the cdf:
Of course, the distribution has no upper bound, but we can readily solve here for as many values as practically required. The approach is general and should work just as well for any desired combination of sides required.
fonte