1
$\begingroup$

If n dice are rolled (n>6), what is probability that each of the six numbers will appear at least once?

  • Dice of 3 numbers:

I've tried some hard solution making a manual exercise to get the formula with a dice of 3 numbers (i.e. A B C).

If I throw the dice n times the possible values are $(1/3)^n$ (3 times = 27, 4 times = 81, 4 times = 243) meanwhile the different values are:

  • 3 dice: ABC ACB BAC BCA CAB CBA = 6
  • 4 dice: AABC AACB ABAC ABCA ACAB ACBA BABC BACB... = 36
  • 5 dice: AAABC AAACB AABAC AABCA... = 150

I'm sure that previous values are true because I've calculated them manually. From there I've tried to get the formula to solve the problem and it works fine the following (for a 3 number dice):

3 dice are rolled: $3*(R_0+(2^{(3-1)})-2)/3^3 = 6/27 = R_1$

4 dice are rolled: $3*(R_1+(2^{(4-1)})-2)/3^4 = 36/81 = R_2$

5 dice are rolled: $3*(R_2+(2^{(5-1)})-2)/3^5 = 150/243 = R_3 \ldots$

The formula just works refering to the previous result because as you can see it is always repeated 3 times, so I've named it as $R_1, R_2, R_3 \ldots (R_0 = 0)$.

  • It seems to be correct so I tried to figure out the formula for a F faces dice thrown n times:

$F*(R_0+((F-1)^{(n-1)})-(F-1))/F^n$

I've tested it but it does not work and I cannot find the issue.

Can you please help me to solve this problem?

$\endgroup$
1
$\begingroup$

Let's say that we have $n$ dice, each with $d$ faces.

Using the Generalized Inclusion-Exclusion Principle, Let $S(i)$ be the outcomes in which face $i$ is not rolled. Then $N(j)$ is the number of outcomes in which $j$ of the faces are not rolled, and $d^n$ is the number of possible outcomes. The probability that $j$ of the faces are not rolled is $$ \frac{N(j)}{d^n}=\overbrace{\ \ \ \binom{d}{j}\ \ \ }^{\substack{\text{number of}\\\text{face choices}}}\overbrace{\left(1-\frac jd\right)^n\vphantom{\binom{d}{j}}}^{\substack{\text{for each choice}\\\text{of faces, the}\\\text{probability of}\\\text{not rolling them}}} $$ Thus, the probability of being in $0$ of these states is $$ \sum_{j=0}^\infty(-1)^j\binom{j}{0}N(j)=\sum_{j=0}^d(-1)^j\binom{d}{j}\left(1-\frac jd\right)^n $$ For $d=3$, this gives $$ 1-3\left(\frac23\right)^n+3\left(\frac13\right)^n-\left(\frac03\right)^n $$ The $\left(\frac03\right)^n$ term becomes important when $n=0$ (we define $0^0=1$, this is not a limit; see also this answer).

$\endgroup$
0
$\begingroup$

For a dice with 3 faces, the probability that all 3 values will be thrown at least once in $n$ rolls is:

$P(3,n) = \frac{Q(3,n)}{R(3,n)} = \frac{3^n - 3(2^n) + 3}{3^n}$

This expression can be derived using the inclusion-exclusion principle. The denominator $Q(3,n)$ does indeed satisfy the recurrence relation that you have discovered:

$Q(3,n) = 3(Q(3,n-1) +2^{n-1}-2)$

However, this formula will not work for more than 3 faces, because the inclusion-exclusion principle introduces an extra term in the denominator $Q(m,n)$ for each new face. For example, for 4 faces the probability that all 4 values will be seen in $n$ rolls is

$P(4,n) = \frac{Q(4,n)}{R(4,n)} = \frac{4^n - 4(3^n) + 6(2^n) -4}{4^n}$

$\endgroup$
  • $\begingroup$ Thank you all for your help! It was really useful! :-) $\endgroup$ – Javier Jul 19 '18 at 9:15
0
$\begingroup$

You can calculate the probability of throwing $k\leq m$ different numbers rolling $n$ dices with $m$ sides using the following formula:

$$P_m(n,k)=\begin{cases}0&, k>n \\ 1&, n\geq k=1\\ \frac{k}{m}P_m(n-1,k-1)+\left(1-\frac{k}{m}\right)P_m(n-1,k)&, n\geq k >1\end{cases}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.