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

%\usepackage{psfig}

\input{macros-course}


\begin{document}

\tutn{19}{12/2/99}{December 3, 1999}

\begin{problems}


\problem  %S99 Tut12

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?

%\solution{

The model ignores the fact the both the casino and the player can lose
only bounded amounts of money before going bankrupt.  Truncating the game
when either party goes bankrupt can completely change the expected
winnings.

For example, since the probability of the gambler coming out ahead by any
amount in a single game with the \$10,000 entry fee is $2^{-14}$, the
expected number of games that must be played before this happens is
$2^{14}$, so if the player has less than $\$2^{14} \cdot 10^5 =
\$163,840,000$, he can expect to go bankrupt before coming out ahead in
even one game.

\textbf{Optional exercise}: What should the casino's and the gambler's net
worths be in order for the gambler's expectation to be positive when the
fixed wager is $\$10$?  How about $\$10,000$?

%}

\eparts


\problem 

\bparts

\ppart Suppose we flip a fair coin until two heads in a row come up.  What
is the expected number, $F$, of flips we perform?  \hint Let
$F_{\text{T}}$ be the expected number of further flips until two heads
comes up, given that the previous flip was T, and likewise let
$F_{\text{H}}$ be the expected number of further flips until two heads
comes up given that the previous flip was H.  Argue that $F_{\text{T}}$
will equal 1 plus the average of $F_{\text{T}}$ and $F_{\text{H}}$.

%\solution{
Clearly $F=F_{\text{T}}$.  Assuming the hint
\[
F_{\text{T}} = 1 + \frac{F_{\text{T}}+ F_{\text{H}}}{2}.
\]
Similarly,
\[
F_{\text{H}} = 1 + \frac{F_{\text{T}}+ 0}{2}.
\]
Solving for $F_{\text{T}}$ yields $F=6$.
%}

\ppart Suppose we flip a fair coin until a head followed by a tail come
up.  What is the expected number, $G$, of flips we perform?

%\solution{
Clearly $G=G_{\text{T}}$.  As above
\begin{eqnarray*}
G_{\text{T}} &=& 1 + \frac{G_{\text{T}}+ G_{\text{H}}}{2},\\
G_{\text{H}} &=& 1 + \frac{0+G_{\text{H}}}{2}.
\end{eqnarray*}
So $G=G_{\text{T}}=4$.
%}

\ppart Suppose we now play a game: flip a fair coin until either HH or HT
first occurs.  You win if HT comes up first, lose if HH comes up first.
What odds should you offer an opponent to make this a fair game?

%\solution{
Even money odds.  Although the expected time for HH is larger
than for HT, the game of waiting for one or the other to come up first is
fair!

To prove this, let W be the probability of winning.  Clearly,
\[
W = (1/2)\prob{W \mid \text{first roll is }T} + (1/2)\prob{W \mid \text{first
roll is }
H} = (1/2)W + (1/2)(1/2)
\]
so $W = 1/2$.
%}

\eparts


\problem An urn contains red and blue colored balls.  The fraction of red
balls is $r$ where $0 \leq r \leq 1$.  A gambler repeatedly pulls a ball
at random from the urn.  That is, at any point during succesive pulls,
each ball in the urn is equally likely to be the next one pulled.  The
gambler puts the ball back into the urn before making the next pull.  He
keeps pulling balls until he pulls \emph{two red balls in a row}.

The sequence of pulls by the Gambler can be regarded as a sequence of
\emph{tries}, where the first try begins with the first ball pulled.  Each
try consists of a sequence of pulled balls continuing until either a blue
ball, or two red balls in a row, are pulled.  For example, if the colors
of pulled balls are RBBBRBRR, then there are five tries which we indicate
with slashes: /RB/B/B/RB/RR/.  Note that each try consists of one or two
consecutive balls.

\bparts

\ppart What is the expected length of the $i$th try, assuming that there
are at least $i$ tries?

%\solution{
Given that there is an $i$th try, it is of length 1 iff it
starts with a blue ball.  It is of length 2 iff it consists of 2 red
balls.  Hence,
\[\expect{\mbox{length of $i$th try} \mid \mbox{there is an
$i$th try}} = 1\cdot (1-r) + 2 \cdot r = 1 + r.
\]
%}

\ppart What is the expected number of tries?

%\solution{
A series of tries ends iff only the last try consists
of two reds.  We know from lecture that the ``mean time to failure'' is
the reciprocal of the probability of failure, so $\expect{\mbox{num
tries}}$ is the $1/\pr{\mbox{2 reds}}= 1/r^2$.
%}

\ppart Write a simple expression in terms of your answers to the previous
parts of this problem for the expected number of balls pulled by the
Gambler.  Briefly justify your reasoning.

%\solution{ 
Wald's Thm applies because $\expect{\mbox{length of $i$th try}
\mid \mbox{there is an $i$th try}}$ is the same expression from part
(a) for all $i$.  Hence,
\[
\expect{\mbox{num pulls}} = \expect{\mbox{pulls per
try}} \cdot \expect{\mbox{num tries}} = (1+r)\frac{1}{r^2}.
\]
%}

\eparts

\end{problems}

\end{document}
        
