14
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ Bonus A looks boring to solve: just a cascade of algebra. Is there a clever method you know of that makes it more elegant? $\endgroup$ – Yakk May 5 '15 at 13:56
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki May 5 '15 at 15:59
16
$\begingroup$

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.


Alternate Bonus (b) Answer

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Milo Brandt May 5 '15 at 3:43
  • 1
    $\begingroup$ Hooray for symmetry arguments! $\endgroup$ – user2357112 May 5 '15 at 6:11
  • $\begingroup$ Great answer all-around, and a well-earned check mark! $\endgroup$ – Steven Stadnicki May 6 '15 at 15:47
6
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ So how would you answer the same questions if they were rolling a d20? :-) $\endgroup$ – Steven Stadnicki May 4 '15 at 23:55
  • 1
    $\begingroup$ @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. $\endgroup$ – Cubicon May 4 '15 at 23:58
  • $\begingroup$ @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. $\endgroup$ – cloudfeet May 5 '15 at 15:49
4
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.