\documentclass[12pt]{6042}
%\usepackage{psfig}

\begin{document}

\handout{dice-game}{Probabilities in a Dice Game}{May 1, 1998, 11am}

In Lecture 19 on 4/8/98 we described a simple dice game: two players take
turns rolling two dice and whoever rolls an eleven first wins.  It's
pretty clear that the first player has an advantage, since he has the
first chance to win.  How much of an advantage?  Here's a simple analysis.

\section{The Probability that the First Player Wins}
The first player has a probability of~1/18 of winning immediately on his
first turn---even before the second player has had a turn---because two of
the 36 outcomes of rolling a pair of dice yield a sum of eleven.  So if we
let $E$ be the event that the first player rolls eleven on the first roll,
we have
\[\Pr(E) = 1/18.\]

Let $W$ be the event that the first player wins.  We want to find
$\Pr(W)$.

The first player wins with probability $1/18$th on his first roll.  With
probability $17/18$ he does not win on his first roll, in which case his
probability of winning is, by definition, $\Pr(W | \overline{E})$.  In
other words, we have
\begin{eqnarray}\label{eq1}
\Pr(W) & = & \frac{1}{18} + \Pr(W | \overline{E}) \cdot \frac{17}{18}.
\end{eqnarray}
This leaves us the problem of finding $\Pr(W | \overline{E})$.

Instead of considering the case when the first player wins later than his
first roll, let's consider the case when the second player wins.
Now we can argue from symmetry: once the first player has failed to
roll an eleven on his 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 roll an eleven on his first term, must also be $\Pr(W)$:
\begin{eqnarray}\label{eq2}
\Pr(W) & = & \Pr(\mbox{second player wins} \mid \overline{E}).
\end{eqnarray}

Now let's make a simplifying assumption about this game which we will
justify shortly: assume that \emph{somebody must always win}, that is,
ties are impossible.  This means that the second player wins
iff the first player does \emph{not} win, so
\begin{eqnarray}\label{eq3}
\Pr(\mbox{second player wins} \mid \overline{E}) & = &
\Pr(\overline{W} \mid \overline{E}).
\end{eqnarray}
Then from equations~(\ref{eq2}) and~(\ref{eq3}),
\begin{eqnarray*}
\Pr(W) & = & \Pr(\overline{W} \mid \overline{E}),
\end{eqnarray*}
and since $\Pr(\overline{W} \mid \overline{E}) = 1 - \Pr(W \mid
\overline{E})$, we conclude
\begin{eqnarray}\label{eq4}
\Pr(W \mid \overline{E}) = 1 - \Pr(W).
\end{eqnarray}
Finally, from equations~(\ref{eq1}) and~(\ref{eq4}) we have
\[\Pr(W) = \frac{1}{18} + (1- \Pr(W)) \cdot \frac{17}{18}.\]
Solving for $\Pr(W)$ we conclude
\[\Pr(W) = \frac{18}{35} \approx 0.514.\]
In other words, the first player has about a $1.4\%$ advantage.

\section{The Possibility of a Tie}
To complete the analysis, we have to justify the assumption that ties are
impossible.  Now that's not really true according to the rules of the
game: if both players always roll non-elevens, the game could go on
forever without a winner and would be a tie.  But we used the ``no ties''
assumption above only to justify equation~(\ref{eq3}), and we can justify
it assuming that a tie, rather than being impossible, merely has
probability zero.  That's because at any point in the game, the first
player does \emph{not} win iff the second player \emph{wins or ties}, so
\begin{eqnarray*}
\Pr(\overline{W} \mid \overline{E}) &  = &
           \Pr(\mbox{second player wins or ties}\mid \overline{E})\\
 & = & \Pr(\mbox{second player wins} \mid \overline{E})
         + \Pr(\set{\mbox{a tie}}\mid \overline{E})\\
 & = & \Pr(\mbox{second player wins} \mid \overline{E}) + 0\\
 & = & \Pr(\mbox{second player wins} \mid \overline{E}),
\end{eqnarray*}
proving equation~(\ref{eq3}).

So, we need to establish that the probability of a tie is zero.  To do
this, we will, finally, have to describe explicitly the probability space
by which we model the game.

\section{The Probability Space}

In this game all that matters about a dice roll is whether or not it sums
to eleven, so it seems natural to model a sequence of dice rolls by a
binary sequence, where the $i$th bit is 1 iff the $i$th roll was eleven.
There is a winner in a particular game iff the game consisted of a
sequence of non-eleven rolls and ended with an eleven; this corresponds to
a sample point consisting a sequence of $n \ge 0$ zeroes followed by a
one.  We also expect the probability of eleven on any give roll remains
$1/18$ no matter what happens on the other rolls---the outcomes of
different rolls are independent.  So it's natural to take the probability
of such a sequence to be $(17/18)^n(1/18)$.

In addition to these winning sample points, there is one more sample point
corresponding to a tie, namely, the infinite sequence of 0's.  There's no
reason to include any other binary sequences---finite or infinite---in our
sample space, since they do not correspond to game outcomes.

Now
\begin{eqnarray*}
\Pr(\mbox{someone wins}) & = & \sum_{m\ge 1}\Pr(\mbox{someone wins on the
$m$th roll})\\
& = & \sum_{m\ge 1}(\frac{17}{18})^{m-1}\frac{1}{18}\\
& = & \frac{1}{18}\sum_{n\ge 0}(\frac{17}{18})^n\\
& = & \frac{1}{18}\cdot \frac{1}{1-\frac{17}{18}} = 1,
\end{eqnarray*}
and
\[\Pr(\mbox{a tie}) = 1 - \Pr(\mbox{someone wins}) = 1 - 1 = 0.\]
This completes the definition of the probability space on which the
analysis above implicitly rested.

Now that we have the space defined explicitly, we can verify the informal
argument ``by symmetry'' above with a rigorous proof:

\textbf{Exercise}: Prove that
\[\Pr(W) = \Pr(\mbox{second player wins} \mid \overline{E}),\]
by describing a suitable bijection between the event $\overline{E}$ and
the whole probability space.
\end{document}
