\documentclass[11pt,twoside]{article}
\usepackage{amsmath}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

\begin{document}

\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}
\newcommand{\where}{{\, \mid \, }}
\newcommand{\size}[1]{\mathify{\left| #1 \right|}}
\newcommand{\equivalent}{\mathify{\ \Longleftrightarrow \ }}
\newcommand{\ifandonlyif}{\equivalent}
\renewcommand{\prob}[1]{\mathify{\textrm{Pr}\left[ #1 \right]}}
\newcommand{\compliment}[1]{\overline{#1}}

  \newcommand{\handoutlabel}{dicegame}
  \newcommand{\handouttitle}{Probabilities in a Dice Game}
  \newcommand{\handoutdate}{April 25, 2000}

\handout{dicegame}{Probabilities in a Dice Game}{April 25, 2000}

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.

\section{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
\[
\prob{E} = \frac{1}{6}.
\]
Now let $W$ be the event that the first player wins the game.  We want to
find $\prob{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,
$\prob{W \where \compliment{E}}$.  This means
\begin{equation}\label{eq1}
\prob{W}  =  \frac{1}{6} + \prob{W \where \compliment{E}} \cdot \frac{5}{6}
\end{equation}
So now let's find $\prob{W \where \compliment{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 $\prob{W}$:
\begin{equation}\label{eq2}
\prob{\mbox{second player wins} \where \compliment{E}}  =  \prob{W}
\end{equation}

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 at any point in the game, the first
player wins iff the second player does \emph{not} win.  In particular, if
the first player did not win on the first roll, then
\begin{eqnarray}
% \equiv here? seems wrong.
\prob{W \where \compliment{E}} & = & \prob{\mbox{first player wins} \where  \compliment{E}}\\
 & = & \prob{\mbox{second player does not win} \where \compliment{E}}\label{eq3}\\
 & = & 1 - \prob{\mbox{second player wins} \where \compliment{E}}\\
 & = & 1 - \prob{W}
\end{eqnarray}
where the last equality follows from equation~(\ref{eq2}).

Combining this with equation~(\ref{eq1}), we conclude
\[
\prob{W} = \frac{1}{6} + (1- \prob{W}) \cdot \frac{5}{6} 
\]
and solving for $\prob{W}$ yields
\[
\prob{W} = \frac{6}{11} \approx 0.545
\]
In other words, the first player has about a $9\%$ advantage.

\section{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~(\ref{eq3}).  Looking more
carefully, we can justify it as long as the \emph{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
\begin{eqnarray*}
\prob{\mbox{first player wins} \where \compliment{E}} & = & 
          \prob{\mbox{first player wins} \where \compliment{E}}
           + \prob{\text{no winner} \where \compliment{E}}\\
 & = & \prob{\mbox{first player wins or there is no winner} \where \compliment{E}}\\
 & = & \prob{\mbox{second player does not win} \where \compliment{E}}
\end{eqnarray*}
proving equation~(\ref{eq3}).

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.

\section{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 \emph{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 \emph{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:
\begin{eqnarray*}
\prob{\mbox{someone wins}} & = & \sum_{m\ge 1}\prob{\mbox{someone wins on the
$m$th roll}}\\
& = & \sum_{m\ge 1}(\frac{1}{6})^m\cdot \card{\text{winning sequences of length $m$}}\\
& = & \sum_{m\ge 1}(\frac{1}{6})^m\cdot 5^{m-1}\\
& = & \frac{1}{6}\sum_{m\ge 1}(\frac{5}{6})^{m-1}\\
& = & \frac{1}{6}\sum_{n\ge 0}(\frac{5}{6})^n\\
& = & \frac{1}{6}\cdot \frac{1}{1-\frac{5}{6}} = 1
\end{eqnarray*}

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 no-win 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 \emph{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.

\textbf{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?

\textbf{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?

\textbf{Exercise 3}:
Carefully prove that, in the game described in the body of this handout,
\[\prob{W} = \prob{\mbox{second player wins} \where \compliment{E}},\]
by describing a suitable bijection between the event $\compliment{E}$ and
the whole probability space.

\end{document}
