Average number of dice rolls before having 3 of kind

Question

Suppose you have 3 dice, and you want to have 3 of a kind. Initially, you roll them all, then you can re-roll some of them until you get 3 of a kind. Rolling multiple dice at once counts as 1 roll.

Example:

2, 4, 5 -> re-roll all dice
3, 3, 1 -> re-roll the 1
3, 3, 5 -> re-roll the 5
3, 3, 3 -> 3 of a kind obtained in 4 roll.

What is the average number of rolls needed to get 3 of a kind ?

My progress so far:

• I wrote a program to do it 100000 times and get the average, it outputs ~7.9 rolls.

• I classified the hand (a,b,c) in 3 different categories:

  • B1, a != b != c
  • B2, a = b != c (2 of a kind)
  • B3, a = b = c (3 of a kind)

The probability of changing to another class when rolling in B1:

• Staying in B1: 5/9
• Changing to B2: 5/12
• Changing to B3: 1/36

Same for B2:

• Changing to B1: 0
• Staying in B2: 5/6
• Changing to B3: 1/6

But i couldn't find an exact formula for the average rolls.

Answer 1

Let $X$ be the random variable that represents the number of rolls until having a three of a kind. To compute its expectation, we condition on the first roll and denote by $Y$ the number of different results we got.

If we got three of a kind ($Y=1$ w.p. $\tfrac{1}{6^2}$), $X=1$ and the expected number of additional rolls is $0$.

If we got two of a kind ($Y=2$ w.p. ${3 \choose 2} \tfrac{5}{6^2}$), we continue to re-roll the third kind. The number of required rolls is $Geom(\tfrac{1}{6})$ (expectation of additional rolls is $6$).

If we got three different results ($Y=3$ w.p. $\tfrac{20}{36}$) then you reroll all or just two (no matter which ones), so the process repeated from this point onward.

By the law of complete expectation (the one represent the first role, the other term is the expected additional number of rolls till three of a kind):

$$E(X)=E(E(X\vert Y))=1+\tfrac{15\cdot 6 + 20 \cdot E(X)}{36}$$

Solving this leads to $E(X)=\tfrac{63}{8}=7.875$

Answer 2

Let $E_1$ be the expected number of throws you need for a 3 of a kind when the current situation is B1, and similarly, $E_2$ for situation B2. Clearly $E_3$ would be $0$ since you have already reached your goal when you are in situation B3.

The transition probabilities you have give you the following equations: $$E_1 = 1 + \frac59 E_1 + \frac5{12} E_2 + \frac1{36} \cdot 0$$ $$E_2 = 1 + 0 E_1 + \frac56 E_2 + \frac16 \cdot 0$$

These equations say you need one roll, plus whatever expected number of rolls you need for each possible result of that roll weighted by their probability.

These are easily solved to give $E_1=\frac{63}8$. This is also the expected number of rolls you are looking for because the situation before the first roll is just like B1 in that you are going to roll all three dice anyway.

Answer 3

Here's another approach. Let $X$ denote the number of trails until exactly two out of the three dice show up the same number, and let $Y$ denote the number of trials until all three dice show up the same number. For $y\in \mathbb{N}$ we have from the total law of probability that

$$P(Y=y)=\sum_{x=0}^{y-1}P(X=x,Y=y)$$

First notice $$P(X=0,Y=y)=\Bigg(\frac{6\cdot5\cdot4}{6^3}\Bigg)^{y-1}\cdot\frac{1}{36}$$ and for $x\in \{1,...,y-1\}$ $$P(X=x,Y=y)=\Bigg(\frac{6\cdot5\cdot4}{6^3}\Bigg)^{x-1}\cdot\frac{3!\cdot 6 \cdot 5}{2!\cdot 6^3} \cdot \Bigg(\frac{5}{6}\Bigg)^{y-x-1} \cdot \frac{1}{6}$$ Plugging these into our forumula for $P(Y=y)$ and simplifying gives us $$P(Y=y)=\frac{3}{10}\Bigg(\frac{5}{6}\Bigg)^y-\frac{2}{9}\Bigg(\frac{5}{9}\Bigg)^{y-1}$$ Finally using geometric series $$E(Y)=\sum_{y=1}^{\infty}yP(Y=y)=\frac{63}{8}$$