6

I know how to calculate the probability of throwing the same number in every throw of a die, and I know how to calculate the probability of throwing a different number in each throw of a die. But how do I calculate the probability of throwing n different numbers in m throws of a die?

Just to be clear, it doesn't matter what the numbers are or how many times each number is thrown – so two ones and three twos in five throws will be equivalent to four threes and one four in the same number of throws, for example.

Alexis
  • 29,850
Remster
  • 350

1 Answers1

4

Let:

  • $T_{n, m}$ be the event "exactly $n$ different numbers in $m$ throws of a dice".
  • $A$ be the event "in the $m^{th}$ throw, a number that has been seen before appears".
  • $D$ be the number of sides on your dice.

We assume that the dice is fair. The objective is to find $P (T_{n, m })$.

Then by the law of total probability, we have:

\begin{align} P (T_{n, m}) =& P (T_{n, m}|A)P(A) + P (T_{n, m}|\overline{A})P(\overline{A})\\ =& P (T_{n, m -1}|A)P(A) + P (T_{n-1, m-1}|\overline{A})P(\overline{A}) \\ =& P (A| T_{n, m -1})P (T_{n, m -1}) +P(\overline{A}|T_{n-1, m -1})P (T_{n-1, m -1}) \\ =& \frac{n}{D}P (T_{n, m -1}) + \frac{D - (n - 1)}{D}P (T_{n-1, m -1}) \end{align}

Base case: $P (T_{n, n })=\frac{n!}{n^n} $ and $ n>m\Rightarrow P (T_{n, m }) =0 $.

Franck Dernoncourt
  • 46,817
  • 33
  • 176
  • 288
  • 1
    I can't quite see this. The probability of throwing six different numbers in six throws of a six-sided dice comes out as 0.665, but I thought it was 0.015 (6/65/64/63/62/6*1/6). Perhaps I'm misunderstanding the notation. – Remster Feb 19 '17 at 23:43
  • @Remster Thanks, good point, the answer was incorrect. Another counter example can be found taking m=1. I have edited the answer. Maybe you can get a neat closed form by induction, I haven't tried. – Franck Dernoncourt Feb 20 '17 at 04:22
  • @Remster I am not a dice expert so you may want to double check :-) My only recent dice experience are job interviews (don't do a PhD in machine learning, just play dice if you want to get hired in some places…) – Franck Dernoncourt Feb 20 '17 at 15:15