\documentclass[12pt,twoside]{article}

\def\handouttype{problemset}

\usepackage{psfig}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \typein[\answer]{Include solutions? (y/n) }
% \def\yes{y}
% \ifx\answer\yes
%   \typeout{}
%   \typeout{Solutions *INCLUDED*.} 
%   \newcommand{\reading}[1]{}
%   \newcommand{\omitsolution}[1]{#1}
%   \usepackage[dark,first,bottom]{draftcopy}
%   \draftcopyName{Solutions}{155}
% \else 
%   \typeout{}
%   \typeout{Solutions *NOT INCLUDED*.} 
%   \newcommand{\reading}[1]{#1\vfill\mbox{}\newpage}
%   \newcommand{\omitsolution}[1]{\vspace*{0.5in}}
% \fi
% \typeout{}

\askaboutsolutions

\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{\Ex}{\text{Ex}}

\newcommand{\workspace}{ \bigskip \bigskip \bigskip \bigskip 
\bigskip \bigskip \bigskip \bigskip}

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
        \smallskip
  \else
     \workspace
  \fi}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut12}
\newcommand{\tutnum}{12}
\newcommand{\tutdate}{April 28, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item (Dice game handout, Ex. 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?

\solution{
The probability that a head first arises on an
even-numbered throw can be easily broken into two cases based on the
first flip. Half the time, a head comes up on the first flip and thus the
first head does not appear on an even toss. The other half of the time,
the first head will be on an even toss only if it is on a odd toss in
the remaining sequence of tosses. Thus:
\begin{eqnarray*}
p & = & \frac{1}{2}(1 - p) \\
p & = & \frac{1}{2} - \frac{1}{2}p \\
\frac{3}{2}p & = & \frac{1}{2} \\
p & = & \frac{1}{3} 
\end{eqnarray*}
}

\end{enumerate}

\newpage
\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage
\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\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 U.S. \ casinos, but they do in St.\ Petersburg) until it comes up
heads. The gambler receives \$1 if the coin shows heads at the first toss,
\$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.

\begin{problemparts}

\problempart 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}
\]
because the event that the money paid is $2^{n-1}$ is the same as the
event that the dealer tosses $n-1$ tails followed by a head. (The 
calculation of the total expectation as the sum of the conditional
expectations weighted by the probabilities of each outcome is justified
rigorously by Theorem 3.4 in Lecture 23).
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.

}

\problempart 
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*}
}

\problempart In reality, it would not be reasonable for the gambler to 
earn money by repeatedly playing the
game with the fixed wager of \$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 = \$1,638,400,000$, 
he can expect to go bankrupt before coming out ahead in even one game.

%% Should be modified and re-inserted, perhaps...
%\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$?
%
%This exercise should most likely \emph{remain} optional, since it does not
%make sense. It expresses a confusion about what constitutes a "game." 
%Repeated `rounds' are not required for an expectation. The expectation
%applies to a single, individual game.
%
%Otherwise, what are the rules for quitting? Will the gambler quit when he
%is even \$1 positive? Do we run until one of the two goes bankrupt?
%Even given these assumption, I do not see how to 
%solve this problem. It is incredibly complex.

As we will learn later, if both the gambler and the house have fixed amounts
of money, and they play repeated rounds of the game, 
one of them will go bankrupt with probability $1$. (In a sense,
it is equivalent to a random walk; random walks cover an expected diatance
that is infinite).
}

\end{problemparts}


\bigskip

\problem 

\begin{problemparts}

\problempart 
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 half of $F_{\text{T}}$ and half of $F_{\text{H}}$.

\solution{$F=F_{\text{T}}$, since the initial condition has no chance
of achieving two heads on the first flip and is thus the same as if the
previous flip had been tails. 

To calculate the expected number of flips, we take $1$ for the first 
flip and then consider the two equally-likely outcomes: the first flip
is tails, or the first flip is heads. The remaining flips we can expect
are simply $F_{\text{T}}$ and $F_{\text{H}}$, respectively.
This gives us a total expectation of:
\[
F_{\text{T}} = 1 + \frac{1}{2}F_{\text{T}} + \frac{1}{2}F_{\text{H}}
\]
If the previous flip was heads, we get a similar calculation. The biggest
difference is that if the first flip is heads, we have no more flips
beyond the current one (we are done).
\[
F_{\text{H}} = 1 + \frac{1}{2}F_{\text{T}}+ \frac{1}{2}(0)
\]
Solving for $F_{\text{T}}$ (by substitution) yields $F=6$.

This can also be solved using a single equation formed by examining
that cases for the first and second flips, but it is not as clean.
}

\problempart 
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{1}{2}G_{\text{T}}+\frac{1}{2}G_{\text{H}} \\
G_{\text{H}} &=& 1 + \frac{1}{2}(0) + \frac{1}{2}G_{\text{H}}
\end{eqnarray*}
So $G=G_{\text{T}}=4$.
}

\problempart 
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$.
}

\end{problemparts}


\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.

\begin{problemparts}

\problempart 
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}
\]
}

\problempart 
What is 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 $\sum_{i=0}^{n-1}X_i$.
Note that $X_0 = 1$.  By linearity of expectation,
\begin{eqnarray*}
E(1+\sum_{i=1}^{n-1} X_i) &=& \sum_{i=0}^{n-1}E(X_i)\\
&=& \sum_{i=0}^{n-1} \frac{n}{n-i}\\
&=& n\sum_{i=0}^{n-1} \frac{1}{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.

}

\problempart 
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
$\frac{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*}

}

\problempart 
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}
\]

}

\problempart 
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{
Note that this is a very loose bound, since it uses Boole's inequality 
above.

Using the previous part, we can solve for $c$ in
\begin{eqnarray*}
e^{-c}  & \leq &  0.01  \\
-c  & \leq &  ln(0.01)  \\
c  & \geq &  -ln(0.01)  \\
c  & \geq &  4.605
\end{eqnarray*}
so, given this, we should buy $52ln(52)+(4.605)52$ cards, or 445 cards.

It is possible to simply calculate the odds for $k$ cards directly,
instead of using the previous part. We then get:
\begin{eqnarray*}
n\left(1-\frac{1}{n}\right)^k  & \leq &  0.01  \\
\left(1-\frac{1}{52}\right)^k  & \leq &  \frac{1}{5200}  \\
\left(\frac{51}{52}\right)^k  & \leq &  \frac{1}{5200}  \\
ln\left[\left(\frac{51}{52}\right)^k\right]  & \leq &  ln\left[\frac{1}{5200}\right] \\
k \cdot ln\left[\frac{51}{52}\right]  & \leq &  -ln\left[5200\right]  \\
k  & \geq &  \frac{ln(5200)}{ln(52)-ln(51)}  \\
k  & \geq &  440.64  \\
\end{eqnarray*}
It should not be surprising that this is a somewhat tighter result --
the previous method relied on a further, looser bound.
}

\end{problemparts}


\end{problems}

\end{document}

\endinput
