1
$\begingroup$

Suppose there is a fair six faced dice, and you roll it once at each round. The rule is as follows:
1). If you roll 1 or 2 at an odd-number round, you win the game and the game ends immediately.
2). If you roll 1 or 2 at an even-number round, you lose the game and it ends immediately.
3). If you roll 3 at any round, then it is a draw and the game ends immediately. If two consecutive $3$'s appear then the game ends immediately in a draw.
4). Otherwise the game goes on.

Now, what is the probability that you will win the game?

I attempted to compute the probability of winning at the 1,3,5,...-th round separately and sum them up. However, due to rule 3) it is ever more complicated to compute this for large round numbers.

Another attempt was to calculate the probability of stopping at each round and to get a closed form expression for this sequence, but this is also hard, because it depends backwards on the previous rounds in an endless manner.

Simply put, if we only consider 1) and 2), or only consider 3), the problem isn't hard, but a combination of the three really messes things up.

Can anyone help? Thanks in advance.

EDIT: I'm very sorry for the mistake when I transcribed rule 3), I have corrected it.

$\endgroup$
13
  • 1
    $\begingroup$ And... if you roll a 4,5, or 6 you roll again? You can describe this rather easily using markov chains. If you care only about winning and consider losses and draws the same, you can describe this with a 4-state markov chain with states Won,Lost,Oddturn,Eventurn and corresponding transition matrix $\left[\begin{smallmatrix}1&0&\frac{1}{3}&0\\0&1&\frac{1}{6}&\frac{1}{2}\\0&0&0&\frac{1}{2}\\0&0&\frac{1}{2}&0\end{smallmatrix}\right]$. Then use standard tools for absorbing stochastic matrices to find the probabilities and if desired expected time until reaching an absorbing state. $\endgroup$
    – JMoravitz
    Mar 20, 2017 at 6:04
  • $\begingroup$ @JMoravitz yeah you are right, if none of the three applies then the game goes on. About Markov, could you briefly explain the four-state chain, and what the W,L,O,E means exactly? I know the basics of Markov chains but don't know how they can apply here. $\endgroup$
    – Vim
    Mar 20, 2017 at 6:06
  • 2
    $\begingroup$ It is still a markov process, just with more states. The method described would still work, just add the additional states OddPrevWas3 EvenPrevWas3 and change states Oddturn to OddPrevWasnt3 and similarly change Eventurn... that increases number of states to 6, but still plenty managable. $\endgroup$
    – JMoravitz
    Mar 20, 2017 at 6:16
  • 1
    $\begingroup$ Intuitively, you have a little better than a 50% chance of winning. The conditions are the same in each round, 1 or 3 is a win or a loss, everything else continues the game. The long run average tells me that overall there is a 50% of winning the game because each round is identical and the chances of winning or losing is the same every other game. The trick though is that every game has to start somewhere. The fact that you start on an odd-numbered game gives you a slight advantage. $\endgroup$ Mar 20, 2017 at 23:33
  • 1
    $\begingroup$ Ergo, an "intuitive" argument. Intuition is rarely reliable, especially in probability theory. That slight advantage of going first has a huge impact, doesnt it? $\endgroup$ Mar 20, 2017 at 23:39

3 Answers 3

1
$\begingroup$

Expanding on JMoravitz’ comment and incorporating the “rule of 3s” that was added in an edit, this game can be modeled by an absorbing Markov process. There are three absorbing states (Win, Lose, Draw). We need to know whether we’re starting an odd-numbered or even-numbered turn since that changes the meaning of rolling a 1 or 2 (Odd, Even), but we also need to track whether or not a 3 was rolled on the previous turn, which adds two more states (Odd Saw A 3, Even Saw A 3). Using the convention that the $i$th row of the transition matrix gives the probabilities of moving to state $j$ from state $i$ (used in the Wikipedia article on absorbing Markov chains), this gives us the following table of transition probabilities for the process: $$\begin{array}{c|cccc|ccc} & O&E&O_3&E_3 & W&L&D\\ \hline O & 0&\frac36&0&\frac16 & \frac26&0&0 \\ E & \frac36&0&\frac16&0 & 0&\frac26&0 \\ O_3 & 0&\frac36&0&0 & \frac26&0&\frac16 \\ E_3 & \frac36&0&0&0 & 0&\frac26&\frac16 \\ \hline W & 0&0&0&0 & 1&0&0 \\ L & 0&0&0&0 & 0&1&0 \\ D & 0&0&0&0 & 0&0&1 \end{array}$$ Taking the first row, these are the transition probabilities at the start of the game, and for any odd-numbered turn: we win on a 1 or 2 ($W$), we continue to an even-numbered turn on a 4-6 ($E$), and on a 3, we go to an even-numbered turn but remember that we had a 3 ($E_3$). The $O_3$ row, which represents a odd-numbered turn for which the immediately preceding roll was a three is the same except that on a 3 we draw ($D$) instead of continuing the game on an even turn. $W$, $L$ and $D$ are absorbing states: even though the game ends when we enter them, for the purposes of this model we consider the process to loop in that state forever once entered.

Per the Wikipedia article, the states are labeled so that the transition matrix has the block structure $$P=\left(\begin{array}{c|c}Q&R\\\hline0&I\end{array}\right)$$ and the probabilities of entering each absorbing state given that we start in one of the other (transient) states are given by the matrix $B=(I-Q)^{-1}R$. You can check your result for plausibility by checking that all of the row sums are equal to $1$. Since we start the game in state $O$, the overall win/lose/draw probabilities are in the first row of $B$.

P.S. The chance of the game’s ending in a draw is easy to compute directly. It’s the probability of rolling two 3s in a row before rolling a 1 or 2, which is given by the equation $P=\frac36P+\frac16(\frac36P+\frac16)$, from which $P(Draw)=\frac1{15}$.

$\endgroup$
17
  • $\begingroup$ One problem with this approach is that the probability from OddPrevWasnt3 to LostOrDraw is hard to determine (I don't know how you get E3 to W =0?). As I said in a comment earlier, I think it's necessary to further break down the states Odd and Even. I actually solved this problem using a nine-state absorbing Markov - absorbing state : W, L, D; transient: O(N,3) (odd, previous wasn't 3 but current is 3), O(3,N) and O(N,N) and E(N,3) etc. $\endgroup$
    – Vim
    Mar 20, 2017 at 22:19
  • $\begingroup$ @Vim Which game are you playing? Per your edit, there’s no possibility of a draw. If you’re on an odd turn and the previous roll wasn’t a 3, the situation is exactly as it was at the beginning of the game: you win on a 1 or 2, otherwise you keep playing and remember if the roll was 3. You’ve either misstated the rules of the game (again) or are making the analysis needlessly complicated. $\endgroup$
    – amd
    Mar 20, 2017 at 22:26
  • $\begingroup$ Another problem is I think there can be another initial state i.e. what if we roll 1 or 2 and win the first round (P=1/3)? I think we must also consider this probability, adding 1/3 to the absorbing probabilities from O(N,N) and O(N,3) to W. $\endgroup$
    – Vim
    Mar 20, 2017 at 22:29
  • $\begingroup$ two consecutive 3s lead to a draw. I'm sorry I didn't know that would be ambiguous. $\endgroup$
    – Vim
    Mar 20, 2017 at 22:29
  • $\begingroup$ No we don't need to distinguish the outcomes of L or D actually, my confusion is stated in a 14 hours ago comment in response to JM's. (If OddPrevWasnt3, then the result at the current odd turn can be either 3 or not 3, and they have different transition probabilities to L/D). $\endgroup$
    – Vim
    Mar 20, 2017 at 22:33
1
$\begingroup$

EDIT Due to a change in rule (3) my answer is no longer correct. However, it is still a useful approach when games are perfectly periodic. Now the probabilities for turns 3 and 4 are not just a scaling of those from turns 1 and 2, so more powerful reasoning will be required! (discrete time dynamical evolution system type things)

Every two turns the game "repeats", so you only need to consider cases up to the end of the second turn.

Suppose $P_1$ goes first. Then they have a $1/3$ chance of winning, $1/6$ chance of drawing, and $1/2$ chance of the dice-roll going to $P_2$. Now, still on turn 1, $P_2$ has a $1/2\times1/3$ chance of winning, $1/2\times1/6$ chance of drawing, and $1/2\times1/2$ chance of the next turn starting.

Turn 2: We've worked out there's a $1/4$ chance of turn 2 starting. $P_1$ has a $1/4\times1/3$ chance of losing, $1/4\times1/6$ chance of drawing, $1/4\times1/2$ chance of the dice going to $p_2$. Now, still on turn 2, $P_2$ has a $1/8\times1/3$ chance of losing, $1/8\times1/6$ chance of drawing, and $1/8\times1/2$ chance of the next turn starting.

You can realise now that turn 3 and 4 are just "scalings" of turn 1 and 2. The probability of each event occurring for every pair of turns is scaled in a geometric series so that eventually the total chance of a win, draw, and loss for either player sums to 1.

Hence after 2 turns the chances for $P_1$ winning, drawing, and losing are: $1/3+1/24 = 3/8$, $1/6+1/12+1/24+1/48 = 15/48$, and $1/6+1/12 = 1/4$ respectively. (This is can be verified by noting that $1 - 3/8+15/48+1/4 = 1/16$, and $1/16$ is the chance of the game not ending by the end of turn 2.

Now it suffices to scale each probability of winning, drawing, and losing, so that their sum is 1. i.e. multiplying each probability by 16/15.

For $P_1$, the chance of winning is $2/5$, the chance of drawing is $1/3$, and the chance of losing is $4/15$.

$\endgroup$
1
  • $\begingroup$ Dear shanye, I'm very sorry I made a mistake when I transcribed rule3 in my post. Please see the edit. Sorry again for wasting your time.. $\endgroup$
    – Vim
    Mar 20, 2017 at 6:20
1
$\begingroup$

Markov chain methods, described in other comments and answers, are a good general approach to analyzing this sort of looping game, but in this specific case the graph of the game is simple and small enough that a direct calculation of the probabilities is feasible. The approach is basically that described in Shayne2020’s answer.

I’ll go through the simplest probability calculation in detail, that of a draw. That’s just the probability of rolling two 3s in a row before rolling a 1 or 2. We don’t care about keeping track of even/odd turns for this, so the game graph simplifies a bit to

enter image description here

Let the random variables $X_i$ represent the die rolls. We then compute the probability of a draw via a breadth-first walk of the graph and the law of total probability: $$\begin{align}\Pr(\text{Draw})&=\Pr(X_1\lt3)\Pr(\text{Draw} \mid X_1\lt3)\\&+\Pr(X_1=3)\Pr(\text{Draw} \mid X_1=3)\\&+\Pr(X_1\gt3)\Pr(\text{Draw} \mid X_1\gt3).\end{align}$$ The game effectively restarts on a roll of 4-6, so $\Pr(\text{Draw} \mid X_1\gt3)=\Pr(\text{Draw})$ and the game ends in a win/loss on a 1 or 2, so the only term left to expand is $$\begin{align}\Pr(\text{Draw}\mid X_1=3) &= \Pr(X_2\lt3)\Pr(\text{Draw}\mid X_1=3\land X_2\lt3) \\&+ \Pr(X_2=3)\Pr(\text{Draw}\mid X_1=3\land X_2=3) \\&+ \Pr(X_2\gt3)\Pr(\text{Draw}\mid X_1=3\land X_2\gt3).\end{align}$$ As before, the game loops back to the start on a 4-6, while the other two branches are terminals. Filling in all of the known probabilities, we get the equation $$\begin{align}\Pr(\text{Draw})&=\frac26\cdot0+\frac16\left(\frac26\cdot0+\frac16\cdot1+\frac36\Pr(\text{Draw})\right)+\frac36\Pr(\text{Draw}) \\ &= \frac1{36}+\frac7{12}\Pr(\text{Draw})\end{align}$$ so $\Pr(\text{Draw})=\frac1{15}$.

To compute the win/loss probabilities, we will need the full graph: enter image description here

The game starts in state $O$, which represents a “clean” odd-numbered turn, i.e., one for which a draw is not possible because the preceding roll was not a 3. If we perform the same sort of breadth-first walk as we did for draw probability, we’ll find that there are two interesting loop points: states $O$ and $E$. The former we already understand; the latter represents a “clean” even turn. If we let $p$ be the probability of winning if we are in state $O$ (which is also equal to the overall probability of winning) and $q$ the probability of winning if we are in state $E$, breadth-first walks give us the following system of equations: $$\begin{align}p &= \frac26\cdot1 + \frac16\left(\frac26\cdot0+\frac16\cdot0+\frac36p\right) + \frac36q \\ q &= \frac26\cdot0+\frac16\left(\frac26\cdot1+\frac16\cdot0+\frac36q\right)+\frac36p\end{align}$$ which simplifies to $$\begin{align} \frac{11}{12}p-\frac12q &= \frac13 \\ -\frac12p+\frac{11}{12}q &= \frac1{18}\end{align}$$ with solution $\Pr(\text{Win})=p=\frac{48}{85}\approx0.5647$ and $q=\frac{94}{255}\approx0.3686$. Observe that the players’ roles are reversed with each turn, so $q$ is also the probability that the first player loses.

$\endgroup$

You must log in to answer this question.

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