\documentclass[11pt]{article}
%\usepackage{eepic}
\usepackage{psfig}
\usepackage{amsmath}
%\usepackage{graphics}
%\usepackage{eepic}
\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersect}{\bigcap}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}
\newcommand{\underdash}{\_}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\textbf{Solution}: \quad #1}


\begin{document}

\tutn{12}{4/30/99}{April 30, 1999}

\section{A Dice Game}
In lecture 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?  Let's review the simple analysis.

\subsection{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})$.

Now notice that at any point when the first player is about to roll, the
second player wins iff the first player loses or eleven never comes up
later.  But the probability that eleven never comes up is $\leq (17/18)^n$
for all $n$, that is, it is zero!  Hence, the probability that the second
player wins at any point when the first player is about to roll is the
same as $1-\prob{W}$.

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)$:
\[
\prob{W}  =  \Pr(\mbox{second player wins} \mid \bar{E}) =  1- \prob{W \mid \bar{E}}
\]
so
\[
\prob{W \mid \bar{E}} =  1- \prob{W}.
\]
Now 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.

\subsection{The Probability Space}
The above argument is a little too informal at this early stage of our
study of probability.  Let's work out clearly what the probability space
is and verify more carefully that the probability of a tie is zero.

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{Optional Exercise for after tutorial}: 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.

\section{Team Problems}

\begin{problems}

\problem You repeatedly roll two fair six-sided dice until either a six or
nine appears (that is, until the sum of the values of the dice on a given
roll is 6 or 9).  You \emph{win} if a nine is rolled before any six, you
\emph{lose} if a six is rolled before any nine, and you \emph{tie} if a
six or nine never comes up (it takes a long time to tie \texttt{:-)} ).

\bparts We model this dice game with a sample space $S$ consisting of the
outcomes of a finite number of dice rolls of other than six or nine,
followed by a six or nine, along with a single sample point ``tie.''
That is,
\begin{eqnarray*}
S & = & \{6;\ \ 9;\\
&   & \ 2,6;\ \ 3,6;\ \ 4,6;\ \ 5,6;\ \ 7,6;\ \ 8,6;\ \ 10,6;\ \ 11,6;\ \ 12,6;\\
&   & \ 2,9;\ \ 3,9;\ \ 4,9;\ \ 5,9;\ \ 7,9;\ \ 8,9;\ \ 10,9;\ \ 11,9;\ \ 12,9;\\
&   & \ 2,2,6;\ \ 2,3,6;\ \ 2,4,6;\ \ 2,5,6;\ \ 2,7,6;\ \ 2,8,6;\ \ 2,10,6;\ \ 2,11,6;\ \ 2,12,6;\\
&   & \ 2,2,9;\ \ 2,3,9;\ \ 2,4,9;\ \ 2,5,9;\ \ 2,7,9;\ \ 2,8,9;\ \ 2,10,9;\ \ 2,11,9;\ \ 2,12,9;\\
&   & \ 3,2,6;\ \ 3,3,6;\ \ 3,4,6;\ \ 3,5,6;\ \ 3,7,6;\ \ 3,8,6;\ \ 3,10,6;\ \ 3,11,6;\ \ 3,12,6;\\
&   & \ 3,2,9;\ \ 3,3,9;\ \ 3,4,9;\ \ 3,5,9;\ \ 3,7,9;\ \ 3,8,9;\ \ 3,10,9;\ \ 3,11,9;\ \ 3,12,9;\\
&   & \dots \} \union \set{\mbox{tie}}
\end{eqnarray*}

\ppart Why can't we model ties by adding a sample point for each tieing
sequence, that is a point for each infinite sequence of the numbers
2,3,4,5,7,8,10,11,12?

\solution{There are uncountably many such sequences, and in 6.042, sample
spaces must be countable.}

\ppart What is the most reasonable probability to assign to each sample
point?  Prove that this assignment of probabilities does make $S$ into a
probability space.

\solution{
\begin{eqnarray*}
\prob{6 \mbox{ on any given roll}} & = & 5/36\\
\prob{9 \mbox{ on any given roll}} & = & 4/36 = 1/9\\
\prob{\mbox{neither 6 nor 9 on any given roll}} & = & 1 - 5/36 - 4/36 = 3/4
\end{eqnarray*}
Let $x$ be a finite sequence of natural numbers between 2 and 12 not
containing any 6's or 9's, let $x_i$ be the number of occurrences of $i$
in $x$.  Then
\begin{eqnarray*}
\prob{x6} & ::= & p_2^{x_2} \dots p_{12}^{x_{12}} \frac{5}{36},\\
\prob{x9} & ::= & p_2^{x_2} \dots p_{12}^{x_{12}} \frac{1}{9},\\
\prob{\mbox{tie}} & ::= & 0.
\end{eqnarray*}
We must prove that the probabilities sum to 1.  In the following,
sequences indicated $2,\dots,12$ do \emph{not} include 6 or 9:
\begin{eqnarray*}
\prob{S} & = & \prob{\mbox{win}} + \prob{\mbox{lose}} + \prob{\mbox{tie}}\\
& = & \sum_{x6}p_2^{x_2} \dots p_{12}^{x_{12}} \frac{5}{36}
 + \sum_{x9}p_2^{x_2} \dots p_{12}^{x_{12}} \frac{1}{9}\\
& = & \frac{9}{36} \sum_x p_2^{x_2} \dots p_{12}^{x_{12}}\\
& = & \frac{1}{4}
        \sum_{n = 0}^\infty
        \sum_{\scriptsize
             \begin{array}{l}
               n_2,\dots, n_{12} \in \naturals \\
               n_2+\dots + n_{12} = n
             \end{array}}
          \binom{n}{n_2,\dots, n_{12}} p_2^{n_2} \dots p_{12}^{n_{12}}\\
& = & \frac{1}{4} \sum_{n = 0}^\infty (p_2 + \dots + p_{12})^n\\
& = & \frac{1}{4} \sum_{n = 0}^\infty (\frac{3}{4})^n\\
& = & \frac{1}{4} \cdot \frac{1}{1 - 3/4} = 1
\end{eqnarray*}
}

\ppart What is the probability you win?

\solution{
\begin{eqnarray*}
\prob{\mbox{win}} & = &  \prob{\mbox{first roll is 9}} + \prob{\mbox{first roll
neither 6 nor 9}} \cdot \prob{\mbox{win}}\\
& = & \frac{1}{9} + \frac{3}{4}\prob{\mbox{win}},
\end{eqnarray*}
so 
\[
\prob{\mbox{win}} = \frac{1/9}{1 - (3/4)} = \frac{4}{9}.
\]
}

\eparts

\problem Remember the game demonstrated in lecture: Albert shows you two
envelopes, each lying face down on a table.  He tells you there are
natural numbers between zero and $n$ in each envelope, and the numbers are
not equal.  You choose an envelope, and Albert shows you the number
written in it.  He now tells you that you can either choose to stay with
that envelope, or switch to the other envelope.  You {\em win} if the
number in the envelope you finally choose is the larger of the two.

\bparts

\ppart A \emph{randomized strategy} for you in this game is a function
that, for each number $i$, assigns a probability $p_i$ of switching {\em
given} that the number in the envelope you picked first was $i$.  Prove
that the strategy described in class for winning with probability at least
$1/2 + 1/2n$ is \emph{optimal} for you.  In particular, if Albert picks $i
\in [0,n-1]$ with uniform probability, and then places $i$ and $i+1$ in
each envelope with equal probability, then your probability of winning is
\emph{at most} $1/2 + 1/2n$.

\solution{Let $p_i$ denote the probability that you switch if you see the
number $i$.  Then, the probability that you win if Albert picks the pair
$(i,i+1)$ is the probability that you will see the smaller number and
switch, or that you will see the bigger number and stay.  Since the
probability of picking either number is $1/2$, the probability that you
win is
\[(1/2)p_i + (1/2)(1-p_{i+1}).
\]

Then, the probability that you win is:
\[
\sum_{i=0}^{n-1} \frac{1}{n} \left(\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})\right)
= \frac{1}{2} + \frac{1}{2n}\sum_{i=0}^{n-1} (p_i-p_{i+1})
= \frac{1}{2} + \frac{1}{2n} (p_0 - p_n) \leq \frac{1}{2} + \frac{1}{2n}
\]
}

\ppart Now suppose the numbers from the problem above are drawn from the
set of all natural numbers, $\naturals$.  Design a randomized strategy for
playing this game such that, no matter what two numbers, $i \neq j$, that
Albert might pick, you will still have \emph{more} than an even chance of
winning.

\solution{Choose \emph{any} distribution on $\naturals$ with a positive
probability, $p_i$, assigned to each $i \in \naturals$, so that larger
numbers have smaller probability.  For example, let $p_i = 2^{-i-1}$.  Now
suppose that Albert chooses the pair $\set{i,j}$ with $i<j$.  Then as
above with this randomized strategy, the probability that you win is the
probability that you see $i$ and switch, or that you see $j$ and don't
switch, namely,
\[
\prob{\mbox{win}} = \frac{1}{2}p_i +\frac{1}{2}(1-p_{j}) =  
\frac{1}{2} + \frac{1}{2}(p_i - p_j)  > \frac{1}{2}.
\]

\iffalse

Of course in this case, in contrast to the case when the choice of numbers
is bounded, Albert can force the probability that you win as close
to---but not equal to---1/2 as he chooses, by choosing sufficiently large
$i,j$,

\fi

}

\eparts

\problem

The St.\ Petersburg Casino offers the following game: the gambler bets a
fixed wager, and then the dealer flips a fair coin (dealers do not flip
coins in US casinos, but they do in St.\ Petersburg) until it comes up
heads. The gambler receives \$1 if the coin shows heads the first time,
\$2 if it shows the first head at second toss, and in general $\$2^{k-1}$
if the dealer tosses the coin $k$ times to get the first head.

\bparts

\ppart Suppose the fixed wager is \$10.  What is the expected amount of
money that the gambler will win in this game?  Suppose the fixed wager is
\$10,000?

\solution{
Let $V$ be the random variable corresponding to the amount of money
that the gambler is paid by the dealer. The distribution of
$V$ is as follows: for any $n\geq 1$,
\[
\prob{V= 2^{n-1}} = 2^{-n},
\]
where the probability refers to the event that the dealer
tosses $n-1$ tails followed by a head.
The average of $V$ is
\[
\expect{V} = \sum_{n=1}^{\infty} [2^{-n} 2^{n-1}]
= \sum_{n=1}^{\infty} 1/2 = \infty.
\]
So whatever the fixed wager, the gambler expects to win an infinite amount.}

\ppart What is the probability that the gambler does not lose money in a
game when the fixed wager is \$10,000?

\solution{The probability of recovering the
money of the wager is only
\begin {eqnarray*}
\prob{V \geq 10,000} & = & \prob{V \geq 2^{14}}\\
&=& \prob{\mbox{dealer flips at least 14 consecutive tails}}\\
& = & 2^{-14} = \frac{1}{16,384}
\end {eqnarray*}
}

\ppart In reality, it would not be reasonable for the gambler to play the
game with the fixed wager at \$10,000.  Why?  \hint Suppose the casino
goes bankrupt.

\solution{In reality, the casino goes bankrupt after a relatively
small number of consecutive tails, so the gambler's win in bounded by the
casino's net worth.  This makes the expectation finite.  Optional exercise:
what should the casino's net worth be in order for the gambler's
expectation to be positive?}

\eparts

\iffalse

\textbf{6042-STAFF: WE'LL USE AT MOST ONE OF THE FOLLOWING TWO PROBLEMS.
LET ME KNOW WHICH YOU PREFER -- ARM.}
\fi

\textbf{
The following two problems were considered for use as team problems but
not assigned in the end.  They're included here for review.
}

\problem Let $R$ and $T$ be independent random variables, and $f$ and $g$
be any functions on the real numbers, i.e. $f,g : \reals \to \reals$.
Prove that $f(R)$ and $g(T)$ are independent random variables.

\solution{The event $f(R) = a$ is the disjoint union of all the events $\set{R
= r}$ for $r \in f^{-1}(a)$, so
\[
\prob{f(R) = a} = \sum_{r \in f^{-1}(a)} \prob{R = r}.
\]
Similarly for the event $\set{g(T) = b}$.  Also, the event $\set{f(R) = a
\mbox{ and } g(T) = b}$ is the disjoint unon of the events $\set{R =
r\mbox{ and }T = t}$ for $(r,t) \in f^{-1}(a) \times g^{-1}(b)$.  Hence,
\begin{eqnarray*}
\lefteqn{\prob{f(R) = a \mbox{ and } g(T) = b}}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)}
                \prob{R = r \mbox{ and } T = t}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)} \prob{R = r} \prob{T = t}
            \hspace{0.5in}\mbox{[because $R,T$ independent]}\\
& = & \sum_{t \in g^{-1}(b)} \sum_{r \in f^{-1}(a)} \prob{R = r} \prob{T =
               t}\\
& = & \sum_{t \in g^{-1}(b)} \prob{T = t} (\sum_{r \in f^{-1}(a)} \prob{R = r})\\
& = & \sum_{t \in g^{-1}(b)} \prob{T = t} (\prob{f(R) = a})\\
& = & \prob{f(R) = a} \sum_{t \in g^{-1}(b)} \prob{T = t}\\
& = & \prob{f(R) = a} \prob{g(T) = b}
\end{eqnarray*}
}

\problem Let $A,B,C$ be events over some probability space, and let
$I_A,I_B,I_C$ be the corresponding index variables, e.g., the event
$\set{I_A = 1}$ is the same as the event $A$ and $\set{I_A = 0}$ is the
same as $\bar{A}$.  Prove that $A,B,C$ are mutually independent iff the
random variables $I_A,I_B,I_C$ are mutually independent.

\solution{
($\Longrightarrow$):  
\begin{eqnarray*}
\lefteqn{\prob{I_A = 1 \wedge I_B= 0 \wedge I_C = 1}}\\
 & = & \prob{A \intersect \bar{B} \intersect C}\\
& = & \prob{(A \intersect C) - B}\\
& = & \prob{A \intersect C} - \prob{A \intersect C \intersect B}\\
& = & \prob{A} \cdot \prob{C} - \prob{A} \cdot \prob{C} \cdot \prob{B}
    \hspace{0.5in}\mbox{[because $A,B,C$ independent]}\\
& = & \prob{A} \cdot \prob{C} (1 -  \prob{B})\\
& = & \prob{A} \cdot \prob{C} \prob{\bar{B}}\\
& = & \prob{I_A = 1} \cdot \prob{I_C = 1} \prob{I_B = 0}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 0} \cdot \prob{I_C = 1}
\end{eqnarray*}
and similarly for any other three binary values in place of 101.

($\Longleftarrow$):  
\begin{eqnarray*}
\prob{A \intersect B \intersect C} & = & 
        \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 1}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 1 } \cdot \prob{I_C = 1}\\
& = & \prob{A} \cdot \prob{B} \cdot \prob{C}
\end{eqnarray*}
Also,
\begin{eqnarray*}
\prob{A \intersect B} & = & \prob{A \intersect B \intersect C}
                       + \prob{A \intersect B \intersect \bar{C}}\\
& = & \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 1} + \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 0}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 1} \cdot \prob{I_C = 1}
       + \prob{I_A = 1} \cdot \prob{I_B = 1} \cdot \prob{I_C = 0}\\
& = & \prob{A} \cdot \prob{B} \cdot \prob{C} + \prob{A} \cdot \prob{B}
                       \cdot \prob{\bar{C}}\\
& = & \prob{A} \cdot \prob{B} (\prob{C} + \prob{\bar{C}})\\
& = & \prob{A} \cdot \prob{B}
\end{eqnarray*}
and similarly for ${B \intersect C}$ and ${A \intersect C}$.
}

\end{problems}

\end{document}

