Massachusetts Institute of Technology Handout 42 6.042J/18.062J: Mathematics for Computer Science April 25, 2000 Professors David Karger and Nancy Lynch

Probabilities in a Dice Game

Two players take turns rolling a six-sided die, and whoever first rolls a 1 is the winner. It’s pretty clear that the first player has an advantage since he has the first chance to win. How much of an advantage?

The game is simple and so is its analysis. The only part of the story that turns out to require some attention is the formulation of the sample space.

1 The Probability that the First Player Wins

We assume the die is fair, so the first player has a 1/6 probability of winning immediately by rolling a 1 on his first turn. That is, letting E be the event that the first player rolls 1 on the first roll, we have

Pr \{E\} = \frac{1}{6}.

Now let W be the event that the first player wins the game. We want to find Pr {W }.

With probability 5/6 the first player does not win on the first roll, in which case the probability the first player wins is, by definition, Pr \{W | \overline{E}\}. This means

Pr \{W \} = \frac{1}{6} + Pr \{W | \overline{E}\} · \frac{5}{6}.  (1)

So now let’s find Pr \{W | \overline{E}\}.

Consider the case when the second player wins. Here we can argue from symmetry: once the first player has failed to win on the first roll, the situation for the second player is exactly the same as it was on the previous roll for the first player. That is, the probability that the second player wins, given that the first player did not win on the first roll, must also be Pr {W }:

Pr \{second player wins | \overline{E}\} = Pr \{W \} .  (2)

Now let’s make a simplifying assumption about this game which we will justify shortly: assume that somebody must always win, that is, ties are impossible. This means that at any point in the game, the first player wins iff the second player does not win. In particular, if the first player did not win on the first roll, then

Pr \{W | \overline{E}\} = Pr \{first player wins | \overline{E}\}  (3)
= Pr \{second player does not win | \overline{E}\}  (4)
= 1 − Pr \{second player wins | \overline{E}\}  (5)
= 1 − Pr {W } ,  (6)

where the last equality follows from equation (2).

Combining this with equation (1), we conclude

Pr \{W \} = \frac{1}{6} + (1 − Pr \{W \}) · \frac{5}{6},

and solving for Pr {W } yields

Pr \{W \} = \frac{6}{11} ≈ 0.545.

In other words, the first player has about a 4.5% advantage.

2 The Possibility of a Tie

To complete the analysis, we have to justify the assumption that somebody always wins. Now that’s not really true according to the rules of the game: if both players always roll numbers other than 1, the game could go on forever without a winner. But we used the “always a winner” assumption above only to justify equation (4). Looking more carefully, we can justify it as long as the probability of there being no winner is zero—rather than requiring that there is always a winner.

Namely, when the probability of no winner is zero, we have

Pr \{first player wins | \overline{E}\} = Pr \{first player wins | \overline{E}\} + Pr \{no winner | \overline{E}\}
= Pr \{first player wins or there is no winner | \overline{E}\}
= Pr \{second player does not win | \overline{E}\} ,

proving equation (4).

So all that remains is verifying that the probability of no winner is zero. To do this, we will, finally, have to describe explicitly the probability space with which we model the game.

3 The Probability Space

Since a game involves a series of dice rolls until a 1 appears, it’s natural to include as sample points the sequences of rolls which determine a winner. Namely, we include as sample points all sequences of integers between 1 and 6 that end at the first occurrence of a 1. For example, the sequences (3, 2, 5, 2, 4, 6, 1), (1), (6, 6, 2, 3, 1) are sample points describing wins by the first player. On the other hand, (3, 2, 3) is not a sample point because no 1 occurs, and (3, 1, 2, 1) is not a sample point because it continues after the first 1.

Now since we assume the die is fair, each number is equally likely to appear, so it’s natural to define the probability of any winning sample point of length n to be (1/6)^{n}.

Besides the necessarily finite length winning sequences, we should consider including sample points corresponding to games with no winner. For example, any infinite sequence of integers between 2 and 6 describes a possible situation in which there is no winner.

Before we throw in any such non-winning sample points, let’s verify that the probabilities we have already assigned guarantee that the probability of a winner is indeed equal to one:

Pr {someone wins} = ∑_{m≥1} Pr {someone wins on the mth roll}

= ∑_{m≥1}(\frac{1}{6})^{m} · |winning sequences of length m|

= ∑_{m≥1}(\frac{1}{6})^{m} · 5^{m−1}

= \frac{1}{6} ∑_{m≥1}(\frac{5}{6})^{m−1}

= \frac{1}{6} ∑_{n≥0}(\frac{5}{6})^{n}

= \frac{1}{6} · \frac{1}{1 − \frac{5}{6}} = 1.

This means that if we choose to throw in some sample points corresponding to no-win situations, we know that each of them must be assigned probability zero, and moreover the total probability of the no-win points we include must be zero. It follows that for the analysis we did in previous sections, and really for any practical purpose at all, it doesn’t matter whether we include any nowin points or not. But we should note one technical quibble: in order to work with sums rather than integrals, sample spaces in 6.042 must be countable. So we are not allowed to throw in all the infinite sequences of integers between 2 and 6 as sample points.

For definiteness, let’s define our sample space to include a single additional point with probability zero, which we regard as describing the no-win event.

Now that we have the space defined explicitly, we can verify the informal argument “by symmetry” above with a rigorous proof, as in the third exercise here.

Exercise 1: Suppose a game involves tossing a fair coin until a head first arises. What is the probability that a head first arises on an even-numbered throw?

Exercise 2: Two players throw 2 dice until the first time one gets 7 or 11. What’s the probability that it is the first player?

Exercise 3: Carefully prove that, in the game described in the body of this handout,

Pr \{W \} = Pr \{second player wins | \overline{E}\} ,

by describing a suitable bijection between the event \overline{E} and the whole probability space.