5
$\begingroup$

Question

Ann and Bob take turns to roll a fair six-sided die. The winner is the first person to roll a six immediately after the other person has rolled a one. Ann will go first. Find the probability that Ann will win.

Answer

$\mathbb{P} (\mathrm {Ann\ wins}) = \frac {36} {73}$


I have thought long and hard about this question but I am unable to even start. I have tried considering cases, but got stuck along the way. For example, it is trivial to calculate the probability that Ann wins if there are only three rolls (which is the minimum number of rolls needed for Ann to win). However, the problem easily becomes very complicated when we consider five rolls and more.

The suggested solution by my professor uses first-step decomposition, but it is a new concept to me and I am struggling to understand it.

If anyone can provide a detailed and intuitive explanation as to how this problem should be solved, that will be greatly appreciated!

$\endgroup$
4
  • $\begingroup$ Am I reading 36/73 right, or should it be 36/72? $\endgroup$
    – 900edges
    Mar 20, 2021 at 15:32
  • $\begingroup$ Weird to have a 73 $\endgroup$
    – 900edges
    Mar 20, 2021 at 15:32
  • $\begingroup$ That' weird, I keep getting $\frac{18}{73}$ $\endgroup$
    – Alex
    Mar 20, 2021 at 15:40
  • $\begingroup$ @Alex Maybe you can post your working as an answer, so we can both look at it? Perhaps more pairs of eyes will do the trick! $\endgroup$
    – Ethan Mark
    Mar 20, 2021 at 15:42

5 Answers 5

8
$\begingroup$

This works well with states.

There are only $4$ active states:

Let $(A,0)$ denote the state in which it is $A's$ turn and the prior toss was not a $1$ (this includes the START state).

Let $(A,1)$ denote the state in which it is $A's$ turn and the prior toss was a $1$

Let $(B,0)$ denote the state in which it is $B's$ turn and the prior toss was not a $1$

Let $(B,1)$ denote the state in which it is $B's$ turn and the prior toss was a $1$

For any state $S$ let $P(S)$ denote the probability that $A$ will eventually win, given that we are now in state $S$. We see that $$P(A,0)=\frac 16P(B,1)+\frac 56P(B,0)$$ $$P(A,1)=\frac 16\times 1+\frac 16P(B,1)+\frac 46P(B,0)$$ $$P(B,0)=\frac 16P(A,1)+\frac 56P(A,0)$$ $$P(B,1)=\frac 16\times 0 + \frac 16P(A,1)+\frac 46P(A,0)$$

This system is easily solved and confirms the official result, here

$\endgroup$
7
  • $\begingroup$ Hello, thank you for answer! I am having trouble understanding how you came up with your four equations. I understand the states. Do you mind explaining just the first equation, so that perhaps I can extend the logic myself to the other three? $\endgroup$
    – Ethan Mark
    Mar 20, 2021 at 15:56
  • $\begingroup$ Sure. Let's say we are in $(A,0)$, so either the game is just starting or $B$ just threw something other than a $1$. $A$ has two paths to eventual victory. Either $A$ throws a $1$ and then wins (eventually) from state $(B,1)$ or $A$ throws something elose and then (eventually) wins from state $(B,0)$. That's all the first equation says! $\endgroup$
    – lulu
    Mar 20, 2021 at 15:58
  • 3
    $\begingroup$ The concept here ought to be clear: this game is likely to take a lot of turns and there's no real hope of writing down all the possible paths, but we don't need to. All that matters is the prior turn, and there are only so many cases to consider. This was Markov's great idea...complicated systems simplify if you don't need to keep track of all the possible paths. $\endgroup$
    – lulu
    Mar 20, 2021 at 16:00
  • 1
    $\begingroup$ Hi. It’s me again! I’m trying to read up on Markov chains by myself and would like to use this question as an example. Do you mind adding to your answer how you would solve this by actually modelling a Markov chain i.e. what would the transition matrix and initial vector be and what multiplications would we need to do to arrive at the answer? $\endgroup$
    – Ethan Mark
    Mar 20, 2021 at 18:29
  • $\begingroup$ You can do that yourself, based on what I have written. You'll want to add two more stares corresponding to the two END stares ($A$ wins or $B$ wins). The transition probabilities can be read off: $(A,0)\to (B,0)$ with probability $\frac 56$, for example, and $(A,0)\to (B,1)$ with prob. $\frac 16$. I suggest: take a shot at it yourself, and post it here. I'll check it. $\endgroup$
    – lulu
    Mar 20, 2021 at 18:33
2
$\begingroup$

I am only guessing on the "First Step Decomposition" technique you referred to in your question, because although I know a method suitable for this question, I do not know the name for the method.

Suppose the answer is $p$. Notice that the first roll has three types of outcomes:

  • Ann rolls 2, 3, 4, 5 or 6. The probability of Ann winning after that is $(1-p)$, since the game proceed with exactly the same rules, except Ann and Bob exchanges position.
  • Ann rolls a 1. In this case, let's suppose Bob's winning probability becomes $q$. Either Bob rolls a 6 (probability $1/6$) and wins the game, or
    • Bob rolls 2, 3, 4, or 5. The probability of Ann winning after this is $p$ again.
    • Bob rolls 1 too. The probability of Ann winning is also $q$.

And let's summarize. The total winning probabilities add up to $p$: $$p = \frac56 (1-p) + \frac16 (1-q).$$ Also there is a relation between $p$ and $q$: $$q = \frac16 + \frac46 (1-p) + \frac16 (1-q).$$

Can you see why these relations hold?

Now solve the equations. You get $p = \frac{36}{73}$.

$\endgroup$
5
  • $\begingroup$ Yes! This is exactly the method my professor used. It is very succinct but it is also very confusing to me. If I think hard enough, I can understand your first equation, but I am unable to understand how you came up with the second. If I am understanding it right, shouldn't the $\frac 1 6$ in your second equation be $\frac 1 6 * \frac 1 6$ since the probability that Bob wins is when Ann rolls a 1 ($\frac 1 6$) and he rolls a 6 himself ($\frac 1 6$)? $\endgroup$
    – Ethan Mark
    Mar 20, 2021 at 16:08
  • $\begingroup$ @EthanMark No. $q$ stands for the probability that Bob wins under the condition that Alice rolls a 1. This is more convenient for me to write equations, but you can do it however you like. Also, this method seems to be strictly weaker than Markov chains, but I never bothered to figure out whether those complex problems can be tackled with this method. $\endgroup$
    – Trebor
    Mar 20, 2021 at 16:21
  • $\begingroup$ Oh, I see. Okay, I actually finally get what is happening here, but this is really really REALLY confusing. Thank you nonetheless :) $\endgroup$
    – Ethan Mark
    Mar 20, 2021 at 16:23
  • $\begingroup$ @trueblueanil either you or I mistyped something, because I got 36/73 on my draft paper. $\endgroup$
    – Trebor
    Mar 21, 2021 at 5:33
  • $\begingroup$ Have resurrected my answer in a new formulation. $\endgroup$ Apr 11, 2021 at 10:12
1
$\begingroup$

This is my attempt at using Markov chains to solve the problem.

Following one of the answers posted, we have $4$ active states and $2$ absorbing states.

Let the $4$ active states be $(A, 0)$, $(A, 1)$, $(B, 0)$ and $(B, 1)$, where

$(A,0)$ is the state in which it is $A$'s turn and the prior flip was not a $1$,

$(A,1)$ is the state in which it is $A$'s turn and the prior flip was a $1$,

$(B,0)$ is the state in which it is $B$'s turn and the prior flip was not a $1$ and

$(B,1)$ is the state in which it is $B$'s turn and the prior flip was a $1$.

Let the $2$ absorbing states be $(A)$ and $(B)$, where

$(A)$ is the state in which $A$ wins and

$(B)$ is the state in which $B$ wins.

Note also that $(A, 0)$ shall be the state in which the game starts.

In order of $(A, 0)$, $(A, 1)$, $(B, 0)$, $(B, 1)$, $(A)$ and $(B)$, the corresponding transition matrix shall be

$$T = \begin{pmatrix} 0 & 0 & \frac 5 6 & \frac 1 6 & 0 & 0 \\ 0 & 0 & \frac 4 6 & \frac 1 6 & \frac 1 6 & 0\\ \frac 5 6 & \frac 1 6 & 0 & 0 & 0 & 0 \\ \frac 4 6 & \frac 1 6 & 0 & 0 & 0 & \frac 1 6 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}.$$

Then, we are simply interested in $T^n_{1, 5}$ as $n \rightarrow \infty$, which can be easily computed to give approximately $0.493$, as required.

P.S. This is my very first time working with Markov chains and all of my learning regarding this concept is independent, so do feel free to provide any comments on how I can improve my working! I do believe I will be covering Markov chains soon, so this could be a nice head start!

$\endgroup$
13
  • $\begingroup$ My matrix is somewhat different...you want the matrix $T$ to be such that $T\vec v$ give3s you the probabilities that we are now in the appropriate states. here is my version (very similar to yours, of course). (cont.) $\endgroup$
    – lulu
    Mar 21, 2021 at 12:18
  • $\begingroup$ (cont.) and here is that matrix raised to the $400^{th}$ power. Note that, afer multiplying by the initial column vector, we see a $.493146$ chance that we have ended with $A$ winning. And $\frac {36}{73}=0.493150685$ $\endgroup$
    – lulu
    Mar 21, 2021 at 12:20
  • $\begingroup$ Should have said, my states go, in order, $(A,0), (A,1), (B,0), (B,1), E_A, E_B$. $\endgroup$
    – lulu
    Mar 21, 2021 at 12:21
  • $\begingroup$ Note that Wolfram Alpha shows you how the matrix arithmetic works out. That is, it gives you the explicit diagonalization of $T$. Once you have that, there is no difficulty inn compouting high powers of the matrix. $\endgroup$
    – lulu
    Mar 21, 2021 at 12:23
  • $\begingroup$ @lulu Isn’t your matrix just the transpose of mine? And so basically, what we want to do is to find $T^n$ and let $n$ tend to infinity, then multiply that by the initial vector? $\endgroup$
    – Ethan Mark
    Mar 21, 2021 at 12:30
1
$\begingroup$

Let the probability of A winning from start be $s$, and from the brink of winning be $t$, then by symmetry, the corresponding state probabilities for $B$ will be $(1-s)\;$ and$\; (1-t)$, and a first step analysis gives

$\displaylines{s = \frac56(1-s) +\frac16(1-t)\\(1-s)=\frac56s +\frac16t\\(1-t) = \frac16\cdot0 +\frac46s +\frac16t}$

[Note: The zero multiplier in the last equation is because we want to find $\Bbb P$($A$ wins), so $B$ can't be allowed to win]

Wolfram gives the answer as $s= \frac{36}{73}, t = \frac{42}{73}$

$\endgroup$
0
0
$\begingroup$

You should solve it using Markov Chains by constructing the set of states varying from the absorbing state $s_{-2}$ (Bob wins) and the absorbing state $s_3$ (Alice wins). I denote the starting state $s_{\emptyset}$. Unless I made a silly mistake somewhere, you should get this set of recurrent equations: $$ p_{\emptyset, 3} = \frac{5}{6}p_{1,3} + \frac{1}{6}p_{-1,3}\\ p_{1,3} = \frac{1}{6}p_{2,3} + \frac{5}{6}p_{\emptyset,3} \\ p_{2,3} = \frac{1}{6}p_{3,3} + \frac{4}{6}p_{\emptyset,3} + \frac{1}{6}p_{-1,3}\\ p_{-1,3} = \frac{1}{6}p_{-2,3} + \frac{1}{6}p_{2,3} + \frac{4}{6}p_{\emptyset,3} $$
The boundary values are $p_{3,3}=1, p_{-2,3} = 0$. I'm pretty sure of this setup, but perhaps I made a typo somewhere during calculations, as I keep getting $p_{\emptyset,3}=\frac{18}{73}$.

$\endgroup$
3
  • $\begingroup$ Oh boy. I was half expecting you to use Markov chains to solve this, but at the same timing hoping you did not, because I have not learnt Markov chains yet (I think I am due to learn it soon), so I really doubt I can understand what is going on in your solution. I will try my best, but if you happen to be able to come up with a more intuitive answer, do post it too! $\endgroup$
    – Ethan Mark
    Mar 20, 2021 at 15:50
  • $\begingroup$ I'm not sure of any other way other than recurrent equations $\endgroup$
    – Alex
    Mar 20, 2021 at 15:51
  • $\begingroup$ On happening on this answer by chance, I see that you have made things difficult due to asymmetry of notation. B's route is $0, -1, -2,$ while $A's$ route is $1,2,3.$ The equations (using your notation except ignoring the $3's$ after the commas) would be $\displaylines{6p_1= p_{-1}+5p_0\\ 6p_0=p_2+ 5p_1\\ 6p_2= 1+p_{-1} +4p_0\\ 6p_{-1} = 0 + p_2 +4p_1}\quad$yielding $\;p_1 = 36/73$ $\endgroup$ Sep 30, 2021 at 18:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .