\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

\iffalse

\problem  %F97 PS11 Problem 4

Let $X$ be a random variable whose value is an observation drawn with
uniform distribution from $\set{i\in \integers \mid -n \le i \le n}$.
Let $Y = X^2$.

\bparts

\ppart Show that $X$ and $Y$ are {\em not} independent.

\solution{

Since $Y$ is determined by $X$, there are many cases indicating where $X$
and $Y$ are not independent, e.g., 
\[\prob{Y = 0} = 1/(2n+1),\mbox{  but } \prob{Y=0 \mid X= 0} = 1.\]

}

\ppart Show that
\[
\expect{XY} = \expect{X} \expect{Y}.
\]

\solution{

Note that $\expect{X} = 0$ and $\expect{XY} = \expect{X^3} = 0$ since $X$
and $X^3$ are both symmetrical.

}

\ppart Conclude that $\variance{X+Y} = \variance{X} + \variance{Y}$, even
though $X$ and $Y$ are not independent.  \hint Show that in general for
any two random variables $X$ and $Y$ that if $\expect{XY} = \expect{X}
\expect{Y}$, then $\variance{X+Y} = \variance{X} + \variance{Y}$.

\solution{

We have that $\variance{X + Y} = \expect{(X+Y)^2} - (\expect{X+Y})^2 =
\expect{X^2 + 2XY + Y^2} - (\expect{X}+ \expect{Y})^2 = \expect{X^2} -
(\expect{X})^2 + \expect{Y^2} - (\expect{Y})^2 + 2\expect{XY} -
2\expect{X}\expect{Y} = \variance{X} + \variance{Y}$.

}

\eparts
\fi

\problem \textbf{The Coupon Collector Problem} %S98 Tut12

We are trying to collect baseball cards.  Assume there are $n$ different
cards.  We can buy them one at a time.  When we buy a card, it is equally
likely that we get any one of the $n$ cards, and purchases are mutually
independent.  We want to study how many cards we need to buy before we get
one each of the $n$ different kinds.

\bparts

\ppart Suppose we already have $k$ different cards.  What is the expected
number of cards we need to buy to get a new card?  \hint Let $X_k$ be the
random variable equal to the number of purchases from the first time we
accumulated $k$ cards until we managed to purchase a $(k+1)$st new card.

\solution{

After getting $k$ different cards, a new purchase has probability
$(n-k)/n$ of getting a new card.  We can view each new purchase as
Bernoulli trial with probability of success $p = (n-k)/n$.   Hence
the expected number of trials to success is $1/p = n/(n-k)$.
That is,
\[E(X_k) = \frac{n}{n-k}.\]
}

\ppart Show that the expected number of cards we need to buy to get one of
each kind?  Express your answer as a simple expression involving a
Harmonic number $H_k$ for some $k$.  \hint Consider $\sum_{i=0}^{n-1}
X_i$.


\solution{

The number of purchases we need is $1+\sum_{i=1}^{n-1}X_i$.
Note that $X_0 = 1$.  By linearity of expectation,
\begin{eqnarray*}
E(1+\sum_{i=1}^{n-1} X_i) &=& 1+\sum_{i=1}^{n-1}E(X_i)\\
&=& 1+\sum_{i=1}^{n-1} \frac{n}{n-i}\\
&=& n\sum_{i=1}^{n} \frac{ 1}{i}\\
&=& n\text{H}_n \sim n \ln n+\gamma n+\Theta(1)
\end{eqnarray*}
Where $\gamma$ is Euler's constant.

}

\ppart Suppose we buy $n\ln n+cn$ cards, where $c>0$ is a real number.
Prove that the probability that we don't have the first card is at most
$1/ne^c$.  \hint $1-x \leq e^{-x}$ for $x<1$.

\solution{

Let $A_1$ be the event that we don't have the first card in $n\ln n + cn$
trials.  In any single trial the probability that we don't get $A_1$ is $1
- 1/n$.  Since the trials are independent,
\begin{eqnarray*}
\Pr(A_1) & = &(1-\frac{1}{n})^{n \ln n + cn}\\
& \leq & e^{-\frac{1}{n} (n \ln n +cn)}\\
& = & e^{-(\ln n + c)} = \frac{1}{ne^c}
\end{eqnarray*}

}

\ppart Suppose we buy $n\ln n + cn$ cards.  Prove that the probability
that we don't have all $n$ cards is at most $e^{-c}$.

\solution{

Let $A_i$ be the event that we don't have the $i^{th}$ card after $n \ln n
+ cn$ trials.

Then the probability that we don't have all the cards is
\[
\Pr(A_1 \cup \ldots \cup A_n) \leq \sum_{i=1}^n \Pr(A_i)
\]
by Boole's inequality.  But this is
\[
n \frac{e^{-c}}{n} = e^{-c}.
\]

}

\ppart Use the previous result to estimate the number of times a cards
must be drawn from a standard deck of 52 in order to have 99\% confidence
of drawing each possible card at least once.  Each drawn card is replaced,
and the deck is freshly shuffled, between draws.

\solution{PLUG IN NUMBERS}

\eparts


\end{problems}

\end{document}
        
