# Who's favored in this dice game?

Alyson and Bethany decide to play a game involving a (standard six-sided) die. Alyson goes first, and rolls the die: if she rolls a 6, then she wins. Otherwise, Bethany takes the die and rolls until she beats Alyson's initial roll. Then, if she's rolled a 6, she wins; otherwise, the die is passed back to Alyson. The game keeps going back and forth between A and B this way, with each one rolling until they beat the other player's high roll, and whoever first hits an unbeatable roll (i.e., the 6 on a six-sided die) winning. Which of them has the better winning chances?

Bonus questions: (a) what happens if the win condition is kept the same, but the die is handed back whenever a player's roll is greater than or equal to the previous high roll? (b) How many rolls does a game take, on average? How many turns (i.e., passes of the die)?

• Bonus A looks boring to solve: just a cascade of algebra. Is there a clever method you know of that makes it more elegant? – Yakk May 5 '15 at 13:56
• @Yakk Sadly, I do not; the problem is solvable for arbitrary $n$ by just setting up the recurrence relation, but I don't know a cleaner approach offhand (though at least it can be tackled as a recurrence relation); that's why it wound up as a bonus question. The genesis of the original problem was in doing some probability work for (simplified versions of) a friend's dice game and discovering the result; I did the calculations first, then discovered a version of the symmetry argument along the way when I realized how uniform it was, and thought it was a neat enough toy problem to share here. – Steven Stadnicki May 5 '15 at 15:59

The probability is exactly $\frac{1}2$ in the original game. The crucial fact is that rolling a $5$ is a loss and that rolling a $6$ is a win - so we can consider the game over once one of those appears. However, at any given roll, the probability of rolling a $5$ equals the probability of rolling a $6$. We can quickly extend this local property to learn that the game is fair:

Suppose player $X$ won, rolling a $6$. An equally likely outcome would be that the game progressed the same until the last roll, at which point $X$ rolled a $5$. Similarly, if $X$ lost rolling a $5$, it was equally likely that they'd have rolled a $6$ instead.

That is, we can pair up all the possible games by switching the last roll between $5$ and $6$, which changes who won, but not the probability of such events occurring.

Extension to Bonus (b)

Notably, if we stop the game whenever we reach a value of $k$ or more, then it is clear that the probability that we stop the game at a value of exactly $k$ is $\frac{1}n$, where $n=7-k$ is the number of integers in $[k,6]$ - that is, the number of rolls greater than or equal to $k$. This holds because switching the last value in such a game has similar effect to before, and hence the last value is uniformly distributed. In particular, this means that the probability of $k$ appearing in a normal game (since the game after a value of $k$ or more is irrelevant as $k$ will not appear again) is $\frac{1}n$.

We can rephrase the above as: We expect to see $\frac{1}n$ turns where $k$ is passed to the other player. Then, the expected length of a game is the sum of the expected number of turns wherein each given value is passed due to the linearity of expectation - thus, the expected length of the game is $$1+\frac{1}2+\frac{1}3+\frac{1}4+\frac{1}5+\frac{1}6=\frac{49}{20}$$

The number of rolls is obviously distributed the same as if we just rolled a die until we got a $6$. We can see that the expected number of rolls $r$ satisfies the relation $$r=\frac{1}6\cdot 1 + \frac{5}6(r+1)$$ since we take $1$ roll $\frac{1}6$ of the time, and otherwise expect $r+1$ rolls. This solves to $$r=6.$$ More generally, we expect as many rolls as there are faces on the die.

Suppose that, in the previous turn, a player passed the number $6-n$. Let the expected number of turns remaining be $t_n$. Then, we have $t_0=0$ and $t_6$ is the expected number of turns in a game with a six sided die. It can be seen that $t$ satisfies the relation: $$t_n=1+\frac{1}n\sum_{i=0}^{n-1}t_i$$ That is to say, each $t_i$ is one more than the average of those below it. This looks unwieldily, but it actually turns out to equal the well-known harmonic series. In particular, define $$T_n=\frac{1}{n+1}\sum_{i=0}^{n}t_i$$ as the average of the sequence thus far. We can express this algebraically, but consider the following:

The average of the sequence $t_0,t_1,\ldots,t_{n-1}$ is $T_{n-1}$. Thus, so is the average of $t_0,t_1,\ldots,t_{n-1},T_{n-1}$, as putting the mean into the sequence doesn't affect the mean. Increasing one element of the $\frac{1}{n+1}$ elements by $1$ increases the mean by $\frac{1}{n+1}$. Therefore $T_n=\frac{1}{n+1}+T_{n-1}$.

From this, and the fact that $t_n=T_{n-1}+1$, we can use the relation that $T_{n-1}=\frac{1}n+T_{n-2}$ as derived above to yield: $$t_n=\frac{1}n+T_{n-2}+1$$ $$t_n=\frac{1}n+\frac{1}{n-1}+T_{n-3}+1$$ and expanding until $T_0=0$ yields $$t_n=\frac{1}n+\frac{1}{n-1}+\ldots+1$$ meaning that $t_n$ is the $n^{th}$ harmonic number - the sum of the reciprocals of the first $n$ natural numbers. So, this game's expected length, which is $t_6$ is $$\frac{1}1+\frac{1}2+\frac{1}3+\frac{1}4+\frac{1}5+\frac{1}6=\frac{49}{20}$$ Though there's no particularly helpful closed form for exact computation of Harmonic numbers as ratios of two integers, this means that, when played with an $n$ sided die, the game will take about $\log(n)+\gamma$ turns where $\gamma$ is the Euler-Macaroni constant.

• If anyone is interested in working it out, the recurrence for a player winning with an $n$-sided die in the bonus question (a) is $$p_0=0$$ $$p_n=1-\frac{1}{n+1}\sum_{i=0}^np_i$$ and one can draw that $p_n$ out of the latter sum and solve algebraically for a more closed form. I haven't calculated any values, but it's probably tractable to describe a simpler form. – Milo Brandt May 5 '15 at 3:43
• Hooray for symmetry arguments! – user2357112 supports Monica May 5 '15 at 6:11
• Great answer all-around, and a well-earned check mark! – Steven Stadnicki May 6 '15 at 15:47

From my initial calculations, if I'm interpreting the question correctly, Alyson's chance of winning on her initial roll is...

50%

Here's my reasoning:

When Alyson throws the die the first time, these are the possible results:

6 - If a 6 is thrown, she immediately wins, as per the question.

5 - If a 5 is thrown, she waits until Bethany can beat her roll. Since the only roll that will beat 5 is a 6, Bethany simply rolls until she gets a 6 and wins. Thus, if Alyson rolls a 5, she immediately loses.

4 - If a 4 is thrown, she again waits for Bethany to beat her roll. This time, Bethany can roll a 5 or a 6 to beat her. Using the previous logic, if Bethany rolls a 5, Bethany loses and Alyson wins. If Bethany rolls a 6, their fortunes are reversed. Therefore, if Alyson rolls a 4, she has a 50% chance of winning on Bethany's turn.

3 - If a 3 is thrown, Bethany's options to beat her are now 4, 5 or 6, each with equal likelihood. If Bethany rolls a 6, Alyson has lost. If she rolls a 5, Alyson has won. If Bethany rolls a 4, she (and thus Alyson as well) has a 50% chance of winning. The total chance for Alyson to win will be $1/3(0\%)$ (on a 6) $+ 1/3(100\%)$ (on a 5) $+ 1/3(50\%)$ (on a 4), which totals 50% again.

2 - The logic above is extended for a roll of 2. This time, the chance of winning breaks down as $1/4(0\%) + 1/4(100\%) + 1/4(50\%) + 1/4(50\%) = 50\%$

1 - The odds are, again, 50%: $1/5(0\%) + 1/5(100\%) + 1/5(50\%) + 1/5(50\%) + 1/5(50\%) = 50\%$

Bonus B

The average number of game turns is 2.45. The following chart shows every possible outcome (shown in turn order), each with a corresponding probability. The sum of the number of turns for each outcome, multiplied by the probability of each, will give us the average turn length of a game.

• So how would you answer the same questions if they were rolling a d20? :-) – Steven Stadnicki May 4 '15 at 23:55
• @StevenStadnicki With great difficulty. :-) I'm sure there's an equation to be derived in there, and the pattern is apparent, but I don't quite have the time to find it right now. – Cubicon May 4 '15 at 23:58
• @StevenStadnicki - this proof is basically "proof by induction" by descending numbers. You show that (N) is a win and (N - 1) is a loss (where N is the number of sides). You then prove that every number less than that is 50% win/loss, because it's the average of the 0%, 100% and any number of 50%s. – cloudfeet May 5 '15 at 15:49

She'll win:

half the time

1/6 of the time, Alyson wins with a roll of 6.
1/6 of the time, Alyson loses with a roll of 5.
1/6 of the time, Alyson rolls a 4 which then has a win/lose rate of 1/2. (total, 5/12).
1/6 of the time, Alyson rolls a 3. 1/3 of those, she wins (B=5); 1/3 she loses (B=6); 1/3 she splits (B=4).
1/6 of the time, Alyson rolls a 2. 1/4 of those, she wins (B=5); 1/4 she loses (B=6); 1/4 she splits (B=4); 1/4 she splits (B=3).
1/6 of the time, Alyson rolls a 1. 1/5 of those, she wins (B=5); 1/5 she loses (B=6); 1/5 she splits (B=4); 1/5 she splits (B=3); 1/5 she splits (B=2).

Bonus A:
1/6 of the time, Alyson wins with a roll of 6.
1/6 of the time, Alyson rolls a 5. 1/4 of the time B=5, A=6. The sum of the sequence is 1/3.
...
(in progress)

No complicated math needed:

6 is an instant win while 5 is an instant loss. Any other outcome will either do nothing or switch turns. The chance remains the same: 50%

For a D20 die, the chance is

still 50%, following the same logic. Anything but the two highest numbers have absolutely no influence on the outcome of the game.

Adding the results of a short simulation program confirms that:

For situation A (dice swap when a better roll achieved): Alyson wins 50% of the time, with an average of 6 rolls and 2.45 turns.

For situation B (dice swap when a better or equal roll achieved): Alyson wins 52.4% of the time, with an average of 6 rolls and 3.28 turns.

And if a D20 dice was used then:

For situation A (dice swap when a better roll achieved): Alyson wins 50% of the time, with an average of 20 rolls and 3.60 turns.

For situation B (dice swap when a better or equal roll achieved): Alyson wins 50.2% of the time, with an average of 20 rolls and 4.55 turns.