Infinite dice roll problem

Question

The following is an interview question:

Two players A and B play a game rolling a fair die. If A rolls a 1, he immediately reroll, and if the reroll is less than 4 then A wins. Otherwise, B rolls. If B rolls a 6, he 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 (note that 1-{1,2,3} is the state where Person A rolls a 1 then either 1,2,3)

$ \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

Lulu's answer is quite simple and elegant.

Here's a slightly different approach, lengthier but perhaps a bit easier to understand.

Consider the first round.

Probability of A winning is

$$\frac{1}{6} \times \frac{1}{2} = \frac{1}{12}$$

Probability of neither of them winning the round is

$$\frac{11}{12} \times \frac{5}{6} = \frac{55}{72}$$

Also, these remain the same for every round viewed in isolation.

So, probability of A winning in the second round would be

$$\frac{55}{72} \times \frac{1}{12}$$

Similarly, probability of A winning in the third round would be

$$\left (\frac{55}{72} \right )^2\times \frac{1}{12}$$

Summing up the probability of A winning in round $1$, or $2$ ... infinity, we get the overall probability.$^{*}$

$$\begin{align*} P(A) &= \frac{1}{12} + \frac{1}{12} \times \frac{55}{72} + \frac{1}{12} \times \left (\frac{55}{72} \right )^2 + \, ...\\[0.3cm] &= \frac{\frac{1}{12}}{1 - \frac{55}{72}} \\[0.3cm] &= \frac{6}{17} \\[0.3cm] \end{align*}$$

---

$^{*}$ Sum of an infinite geometric sequence with $|r| < 1$ is $\frac{a}{1 - r}$.

Answer 2

As noted in the comments, the proposed solution is much too small..it's less than the probability that $A$ wins on the first toss and, clearly, the true answer must be considerably greater than that.

One approach:

$A's$ chance of winning in the first round is $$\frac 16\times \frac 12=\frac 1{12}$$.

$B's$ chance of winning in the first round is $$\frac {11}{12}\times \frac 16=\frac {11}{72}$$

It follows that $A's$ overall chance of winning is the ratio $$\frac 1{12}\Big / \left(\frac 1{12}+\frac {11}{72} \right)=\frac 6{17}$$

Answer 3

Your Markov chain doesn't seem to take into account whose turn it is. You say that $S$ has a $4/6$ chance of returning to $S$, but that means you're not tracking when it's A to roll and when it's B to roll. In the following, $A$ is the start state with A to roll, $B$ is the state with B to roll, $A_1$ is the state where A has just rolled a 1 and $A_w,B_w$ are the states where A or B (respectively) have won.

$ \begin{array}{c|ccccc} & A & A_1 & B & A_w & B_w \\ \hline A & 0 & 1/6 & 5/6 & 0 & 0 \\ A_1 & 0 & 0 & 1/2 & 1/2 & 0 \\ B & 5/6 & 0 & 0 & 0 & 1/6 \\ A_w & 0 & 0 & 0 & 1 & 0 \\ B_w & 0 & 0 & 0 & 0 & 1 \\ \end{array} $

The abundance of $0$s in our matrix indicate that a Markov chain may be overkill: we might just be able to write down the recurrence directly. We get that $a=\frac{1}{6}\times\frac{1}{2}+(1-\frac{1}{6}\times\frac{1}{2})(1-\frac{1}{6})a$. This is because A wins in one of the mutually exclusive possibilities: A wins on this turn; or the turn passes to B and then back to A and then A subsequently wins. (The use of $a$ on the RHS of the recurrence uses the memorylessness, like the Markov chain does.) We get $a=6/17$.

Answer 4

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 using a recursion based approach (although similiar to other methods, this logic can be applied to some places where the other methods fail and so it would be good to know all such methods when dealing with probability questions) and so I would like to show you the working of it :

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. : There are already good answers that would explain your question, but I did not see a recursion based approach and so I decided to post this answer with very detailed explanation because I am somewhat of a beginner in probability myself so it is important to thoroughly explain every detail of these recursion methods for everybody like me to understand it clearly.