Infinite dice roll probability

Question

The following is an interview question:

Two players A and B play a game rolling a fair die. If A rolls a 1, they immediately reroll, and if the reroll is less than 4 then A wins. Otherwise, B rolls. If B rolls a 6, they win, otherwise A rolls again, and so on. What is the probability A wins?

My approach: I have 4 states S (initial starting state), 1, 1-{1,2,3}, 6, and this is my markov chain matrix

$ \begin{array}{c|cccc} & \text{S} & \text{1} & \text{1-{1,2,3}} & \text{6} \\ \hline \text{S} & 4/6 & 1/6 & 0 & 1/6 \\ \text{1} & 33/36 & 0 & 3/36 & 0 \\ \text{1-{1,2,3}} & 0 & 0 & 1 & 0 \\ \text{6} & 0 & 0 & 0 & 1 \\ \end{array} $

Using this I calculate probability of absorption to state 1-{1,2,3} and get 0.0769. Is this matrix the right set up? And is there a simpler way of doing this?

Thank you!

Answer 1

The matrix doesn't seem right, but it is difficult to see as the labels are not very clear. What is the transition from 1 to 1-{1,2,3} and why is it 3/36?

Possibly it is easier to use:

$$\begin{array}{}M = & \begin{array}{c|cccc} & \text{A's turn} & \text{B's turn} & \text{A wins} & \text{B wins} \\ \hline \text{A's turn} & 0 & \frac{11}{12} & \frac{1}{12} & 0 \\ \text{B's turn } & \frac{5}{6} & 0 & 0 & \frac{1}{6} \\ \text{A wins} & 0 & 0 & 1& 0 \\ \text{B wins} & 0 & 0 & 0 & 1 \\ \end{array} \end{array}$$

You might want to consider the product of the matrix $M \cdot M$ which makes the state A's turn either return to the state A's turn or to one of the absorbing states.

From this point there are different ways to solve it. (and also there are different ways to reach this point, the matrix formulation is not really neccesary)

• One may use a recursive formula formula like

  $$P(\text{A wins, given A starts in turn 1}) = \frac{55}{72} P(\text{A wins, given A starts in turn 3}) + \frac{1}{12}$$

  and solve it after substituting $P(\text{A wins, given A starts in turn 1}) = P(\text{A wins, given A starts in turn 3})$

  This reasoning also occurs in question like

  • Amoeba Interview Question
  • The Frog Problem (puzzle in YouTube video)
  • The Dead Drunk Man

• Or plainly reason based on the odds for A and B $$P(\text{A wins}) = \frac{6/72}{6/72+11/72}$$

• Or compute the above reasoning more explicitly by expressing the total integral of 'fraction x time' that is spend in state $\text{A's turn}$

  $$P(\text{A wins}) = \frac{1}{12} \underbrace{ \sum_{k=0}^\infty \left(\frac{55}{72} \right)^k }_{= \frac{1}{1-\frac{55}{72}}}$$

That last case resembles the more genral matrix approach by Whuber, which I hope would score extra points. But it is difficult to say what the interviewers are looking for. If they had wanted a matrix approach, then they should have asked a question that asks for such approach (with less zero's in the matrix).

Answer 2

Evidently $A$ has a $3/6 \times 1/6 = 1/12 = a$ chance of winning on their turn and $B$ has a $1/6 = b$ chance of winning.

From $A$'s perspective, their chance $p_A$ of winning this game is the sum of

1. The chance of winning immediately, equal to $a,$ and

2. The chance of not winning immediately ($1-a$) times the chance $B$ does not win on their turn ($1-b$) times the chance $p_A$ of winning, because at that point the game restarts.

Thus

$$p_A = a + (1-a)(1-b)p_A\tag{*}$$

whose unique solution is easily found (which I leave to you to work out).

I you like to test things with simulations, here is one using R:

play <- function(a, b) ifelse (runif(1) < a, 1, 1 - play(b, a))
mean(replicate(1e3, play(1/12, 1/6)))

[1] 0.3458

This result differs from the correct value only by chance variation.

---

This answer disagrees with the value (0.0769) stated in the question, so let's look at the Markov chain. There are four states:

• It is A's turn.
• It is B's turn.
• A has won.
• B has won.

The initial state is $(1,0,0,0),$ the final state is $(0,0,1,0),$ and the transition matrix (which reflects the definitions of $a$ and $b$ -- there's no computation needed) is

$$\mathbb P = \pmatrix{0&1-a&a&0\\ 1-b&0&0&b \\ 0&0&1&0 \\ 0&0&0&1}$$

You could compute eigenvalues and eigenvectors and turn the Markov Chain crank, but the block matrix structure of $\mathbb P$ suggests a simpler way. Notice that

$$\mathbb P = \pmatrix{\mathbb A&\mathbb B\\ 0 & \mathbb I}$$

with $\mathbb A = \pmatrix{0&1-a\\1-b&0}$ and $\mathbb B = \pmatrix{a&0\\0&b}$ for the top $2\times 2$ blocks. When squaring any matrix in this form you find

$$\mathbb P^2 = \pmatrix{\mathbb A^2 & (\mathbb A + \mathbb I)\mathbb B\\ 0 & \mathbb I}.$$

Iterating reveals a pattern in the upper right block: within $\mathbb P^{2^n}$ it takes the form

$$(\mathbb A^{2^n-1} + \mathbb A^{2^n-2} + \cdots + \mathbb A + \mathbb I)\mathbb B$$

(easily established by induction). This is a geometric series of matrices with limiting form

$$\lim_{n\to\infty} \mathbb P^{2^n} = (\mathbb I - \mathbb A)^{-1}\mathbb B.$$

You can read the chance of $A$ winning from the $(1,3)$ entry of $\mathbb P,$ equal to the $(1,1)$ entry of this limit,

$$(\mathbb I - \mathbb A)^{-1}\mathbb B = \pmatrix{1 & a-1\\b-1&1}^{-1}\pmatrix{a&0\\0&b} = \frac{1}{1 - (1-a)(1-b)}\pmatrix{a & *\\* & *},$$

which you can verify solves $(*)$ above.

Answer 3

@Glen_b and @whuber have gave good answers, and I think the gist is the Bayesian formula.

---

Here is another method:

For a single round , the probabilities are:

P_A = 1/6 * 3/6 = 1/12
P_B = (1 - P_n_A ) * 1/6 = 11/12 * 1/6 = 11/72
P_Draw = 1 - P_n_A - P_n_B = 55/72

For round n, the probabilities are:

P_n_A = P_Draw ^ (n-1) * P_A
P_n_B = P_Draw ^ (n-1) * P_B
P_n_Draw = P_Draw ^ (n)

These are all geometric sequence, and the common ratio is: r= P_Draw

The sum of the first n terms in a geometric sequence: Sn = a1 * (1-r^n) / (1-r)

So, the probability for A or B wins before round n is:

S_n_A = P_1_A + P_2_A + ... P_n_A = 1/12 * (1-r^n) / (1-r)
S_n_B = P_1_B + P_2_B + ... P_n_B = 11/72 * (1-r^n) / (1-r)

By the way, the probability for draw before round n is: r ^ (n)

Because r < 1, so:

lim(n->∞)(S_n_A) = 1/12 * (1-0) / (1-r) = 1/12 / (1- 55/72) = 6/17
lim(n->∞)(S_n_B) = 11/72 * (1-0) / (1-r) =  11/72 / (1- 55/72) = 11/17
lim(n->∞)(draw_n) = lim(n->∞)(r ^ (n)) =  0

---

And we can get common formulas for this kind of games:

P_Draw_single = 1- P_A_single - P_B_single
P_Awin = P_A_single / (1 - P_Draw_single) 
P_Bwin = P_B_single / (1 - P_Draw_single) 

Thus,

P_Awin = P_A_single / (P_A_single + P_B_single)
P_Bwin = P_B_single / (P_A_single + P_B_single)

---

For example, a more simplified game: Two players A and B roll by turn, who rolls a 1 wins, and A rolls first. So,

P_A_single = 1/6
P_B_single = 5/6 * 1/6 = 5/36

And,

P_Awin = P_A_single / (P_A_single + P_B_single) = 6/11
P_Bwin = P_B_single / (P_A_single + P_B_single) = 5/11

---

Further more, I think these common formulas can support more than 2 players.

P_Awin = P_A_single / (P_A_single + P_B_single + ......)
P_Bwin = P_B_single / (P_A_single + P_B_single + ......)
P_Cwin = P_C_single / (P_no_draw)
......

Answer 4

We don't need matrices — this can be modeled with series. Let $P_W$ denote the probability $A$ wins on their roll, and $P_L$ denote the probability $A$ loses but gets another chance to roll (i.e., $B$ doesn't win on their roll). Then the probability $A$ wins overall, $P_O$, is the sum:

$$ P_O = P_W + (P_L)P_W + (P_L)^2P_W + \dots $$

This is a geometric series and using the well-known formula one can simplify this down to:

$$ P_O = \frac{P_W}{1 - P_L} $$

We can solve for $P_W$ and $P_L$ directly:

$$ \begin{aligned} P_W &= \frac{1}{6}\left(\frac{1}{2}\right) = \frac{1}{12} \\ P_L &= \left[\frac{5}{6} + \frac{1}{6}\left(\frac{1}{2}\right)\right]\left(\frac{5}{6}\right) = \frac{55}{72} \end{aligned} $$

Thus, the overall chance $A$ wins is:

$$ P_O = \frac{\frac{1}{12}}{1 - \frac{55}{72}} = \frac{6}{17} $$

Answer 5

Another graphical way to go about this is to use a familiar tree,

We see that the probability of $A$ winnning per game is $6/72$ and the probability of the game repeating is $50/72 + 5/72 = 55/72$. So the apriori probability for $A$ winning is

\begin{align} \Pr({\rm A\; wins}) &= \frac 6{72} + \frac{55}{72} \cdot \frac 6{72} + \left(\frac{55}{72}\right)^2\cdot \frac 6{72}+\dots \\ &=\frac 6{72} \cdot \left( 1+ \frac{55}{72} + \left(\frac{55}{72}\right)^2+\dots \right)\\ &= \frac 6{72}\cdot \frac {1}{1- 55/72} = \frac 6 {17}. \end{align}

Answer 6

I am sorry because I do not know Markow chains and such theorems because I am kind of new to high level math, but this probability question is something that I would like to answer and maybe, the methods above are just my method condensed but I do not understand the logic behind them and so I would like to show you the working of my method just in case it is different :

Let us break this up into the 3 cases possible for A to win :

$\text{Case 1 : A} \xrightarrow{\text{rolls a 1}}\text{A rolls again}\xrightarrow{\text{rolls < 4}} \text{A wins}$

$\text{Case 2 : A}\xrightarrow{\text{rolls a 1}}\text{A rolls again}\xrightarrow{\text{rolls > 3}}\text{B rolls}\xrightarrow{\text{does not roll a 6}}\text{A rolls again as if nothing ever happened (}``\text{a fresh start")}$

$\text{Case 3 : A}\xrightarrow{\text{does not roll a 1}}\text{B wolls}\xrightarrow{\text{does not roll a 6}}\text{A rolls again as if nothing ever happened (}``\text{a fresh start")}$

Let the probability of A winning the game eventually when nobody else has ever rolled the dice before is $P_a$

For case 1, we have a simple probability of $\frac{1}{6} \text{(to roll a 1)} \cdot \frac{3}{6} \text{(to roll < 4)} = \frac{1}{12}$

For case 2, A will first need to roll a 1 and then > 3 and then B will have to not roll a 6 and then probability of A winning eventually is just $P_a$ because A rolls again as if nothing ever happened and probability of A winning eventually before anybody ever rolled the dice is $P_a$ only.

So the probability comes out to be $\frac{1}{6} \text{(to roll a 1)} \cdot \frac{3}{6} \text{(to roll > 3)} \cdot \frac{5}{6} \text{(for B to not roll a 6)} \cdot P_a = \frac{5P_a}{72}$.

For case 3, A will have to not roll a 1 and then B will not have to roll a 6 and then again probability of A winning eventually is just $P_a$ because A rolls again as if nothing ever happened and probability of A winning eventually before anybody ever rolled the dice is $P_a$ only.

So the probability comes out to be $\frac{5}{6} \text{(to not roll a 1)} \cdot \frac{5}{6} \text{(for B to not roll a 6)} \cdot P_a = \frac{25P_a}{36}$.

As all of these are "cases" we have to add them all to find total probability of A winning eventually when nobody has ever rolled the dice before, but that is again just $P_a$

So $P_a = \frac{1}{12} + \frac{5P_a}{72} + \frac{25P_a}{36} = \frac{1}{12} + \frac{55P_a}{72}$

$\therefore P_a - \frac{55P_a}{72} = \frac{17P_a}{72} = \frac{1}{12} \implies P_a = \frac{6}{17}$

P.S. : The topmost answer is almost the same method (and exactly the same logic) but since I, being somewhat of a beginner in probability, found it confusing how they had reduced some steps in their answer, I decided to post this answer with much more explanation and understanding for people like me to better understand the solution.