“Alea iacta est” - said Julius Caesar as he crossed the Rubicon, starting an avalanche of events that would change the course of history forever. The die is cast, and the future is now.
Fast-forward two millennia, and humanity’s obsession with dice, fate and randomness is still going strong. So much so as today we have to invoke the evergreen participant of math problems, Alice for a gentler introduction to a particularly interesting aspect of probabilities and statistics. This is a problem that I have encountered a long time ago on Daily Coding Problem, but I was for a very long time bugged by how counter-intuitive it seemed to me at first.
The problem in its original form goes like this:
1
2
3
4
5
6
7
8
9
10
Alice wants to join her school's Probability Student Club.
Membership dues are computed via one of two simple probabilistic games.
The first game: roll a die repeatedly. Stop rolling once you get a five
followed by a six. Your number of rolls is the amount you pay, in dollars.
The second game: same, except that the stopping condition is a five followed by a five.
Which of the two games should Alice elect to play? Does it even matter? Write a
program to simulate the two games and calculate their expected value.
But are they not equal?
We have to roll some pattern twice. My intuition says that it shouldn’t depend on the pattern. Rolling two fives in a row should be exactly as likely as rolling a five and a six consecutively. Are the probabilities not equal?
No, they are not. This problem is a perfect example of how our intuition can lead us astray. Of course, it’s a bit easier to reason about it if we first write the simulation and see the actual outcome. I am providing here however two theoretical solutions as well, an elegant but formal mathematical one, and a more intuitive, informal one.
The intuitive solution
The first natural intuition would be that the events of rolling a die twice are independent, and therefore it shouldn’t matter which two numbers we are looking for. That’s where we are wrong.
Imagine you’re Alice, and you’re playing the first game. You just rolled a five: a decisive moment, you’re waiting for a six. If you roll anything but a six, you’re back to square one. Except, you can roll another five and be back to only expecting that winning six. This is the key difference between the games. In the first game, where Alice is expecting the five-five streak after rolling the initial five, rolling anything else would push her back to rolling that initial five again. In other words, the first game is a bit more forgiving in the buildup of the expected streak.
It’s a slight difference, but the first game is just a tidbit more permissive, and she’s likely to get it done in fewer rolls.
The formal solution
Formally, writing the numbers of rolls for the first and second games as random variables A and B respectively, Alice should choose the one with the lower expected value.
The expected value of the first game then becomes:
\[{\rm I\!E}(A)= 1 + \frac{1}{6}{\rm I\!E}(A|prev = 5) + \frac{5}{6} {\rm I\!E}(A)\] \[{\rm I\!E}(A| prev = 5) = 1 + \frac{1}{6} 0 + \frac{1}{6}{\rm I\!E}(A | prev = 5 ) +\frac{4}{6} {\rm I\!E}(A)\] \[{\rm I\!E}(A) = x \ \ and \ \ {\rm I\!E}(A|prev = 5) = y\]And we get the system of equations:
\[\left\{ \begin{array}{ll} x = 1 + \frac{1}{6} y + \frac{5}{6} x \\ y = 1 + \frac{1}{6} y + \frac{4}{6} x \end{array} \right.\]Whose solutions are $y=42$ and $x=36$. The expected value of the first game is then $36$ rolls.
For the second game, we proceed similarly:
\[{\rm I\!E}(B)= 1 + \frac{1}{6}{\rm I\!E}(E|prev = 5) + \frac{5}{6} {\rm I\!E}(B)\] \[{\rm I\!E}(B| prev = 5) = 1 + \frac{5}{6}{\rm I\!E}(B) +\frac{1}{6} 0\] \[{\rm I\!E}(B) = x \ \ and \ \ {\rm I\!E}(B|prev = 5) = y\]We get the system of equations:
\[\left\{ \begin{array}{ll} x = 1 + \frac{1}{6} y + \frac{5}{6} x \\ y = 1 + \frac{5}{6} x \end{array} \right.\]So
\[x = 1 + \frac{1}{5} + \frac{5}{36}x + \frac{30}{36}x\]Meaning that $x=42$. That is, we need in average 42 rolls to win the second game.
The simulation
As simple and straightforward as it gets:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import random
import numpy as np
def first_game(previous, current):
return previous == 5 and current == 6
def second_game(previous, current):
return previous == 5 and current == 5
def simulate(nr_trials=100_000, game_condition=first_game):
trials = np.zeros(nr_trials)
for i in range(nr_trials):
prev = random.randint(1, 6)
trial = 1
while True:
current = random.randint(1, 6)
trial += 1
if game_condition(prev, current):
break
prev = current
trials[i] = trial
print(f'Expected number of trials: {trials.mean()}')
print(f'Standard deviation: {trials.std()}')
if __name__ == '__main__':
print(f'First game:')
simulate()
print(f'Second game:')
simulate(game_condition=second_game)
Bonus question: Why does the standard deviation look the way it does?