\documentclass[10pt]{article}	
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightyear}{2002}
\renewcommand{\coursecopyrightnames}{Prof. Albert~R.~Meyer}

\renewcommand{\problemdata}[5]{}

\begin{document}
\inclassproblems{13F}


%F01 pset10

\begin{problem}
A gambler has been studying the roulette wheel in a Las Vegas casino over
a long period of time, and his data confirms that the wheel is biased to
come up on a red number about 51\% of the time.  Since a bet on red pays
even money (bet \$1 and either lose it, or win and get back \$2), he
realizes the odds are in his favor.

So with high hopes and an initial stake of \$10,000, the gambler aims to
turn his stake into \$1,000,000.  He plans simply to continue making \$100
bets on red until either he is ahead the \$1,000,000, or he goes bankrupt.
He considers bankruptcy very unlikely because the odds are in his favor,
and the bets are small enough relative to his initial stake that he can
withstand a long run of losses.

\bparts

\ppart 
Based on this description, describe a reasonable probability space to
model this situation.

\solution{
An easy way to describe an appropriate sample space is to keep track of
the gambler's stake.  So sample points will be all the finite sequences of
nonnegative multiples of 100, that
\begin{itemize}
\item start at 10,000,
\item end at the first occurrence of either 0 or 1,000,000,
\item have successive integers in the sequence differ by exactly 100.
\end{itemize}
For example, the sample point describing two initial wins, followed by 102
losses and bankruptcy would be the length 105 sequence
\[
(10000, 10100,10200, 10100,10000,9900,9800,\dots,200,100,0).
\]
The sample point corresponding to his winning every bet until he reaches
his goal would the length 9,900 sequence
\[
(10000, 10100,10200, 10300,10400,\dots, 999800, 999900, 1000000).
\]
The probability of an outcome is defined to be $(0.51)^k(0.49)^j$ where
$k$ is the number of increases by 100, and $j$ is the number of decreases
by 100.  Note that either $j-k = 100$ for sample points that lead to
bankruptcy or $k-j = 9,900$ for those leading to \$1,000,000.}

\ppart Describe an positive constant, $\epsilon$, such that, at any point
during his play when the gambler has not gone bankrupt, there is a
probability of at least $\epsilon$ that he will reach his goal of
\$1,000,000 within the next 9,999 bets.

\solution{ $\epsilon \eqdef (0.51)^{9999}$ will do, since even if the
gambler's stake was down to \$100, there is still this much probability
that he will win the next 9,999 bets in a row and reach his goal of
\$1,000,000.}

\ppart Conclude that the probability that he bets forever---without either
going bankrupt or reaching his \$1,000,000 goal---is zero.

\solution{By part~(b) the probability that the gambler does \emph{not}
reach his \$1,000,000 goal during his first 9,999 bets is at most
$1-\epsilon$.  The conditional probability that he reaches \$1,000,000
during his second sequence of 9,999 bets, given that he hasn't already
reached his goal or gone bankrupt, is at most $(1-\epsilon)^2$.  The
conditional probability that he reaches \$1,000,000 during his $n$th
sequence of 9,999 bets, given that he hasn't already reached his goal or
gone bankrupt, is at most $(1-\epsilon)^n$.

This implies that the probability that he bets more than $9999n$ times is
at most $(1-\epsilon)^n$, and so the probability that he bets forever is
at most $(1-\epsilon)^n$ for every $n$.  Since $(1-\epsilon)^n$ approaches
0 as $n \rightarrow \infty$.  The probability that the gambler bets
forever is at most 0.}

\eparts
\end{problem}


%F01 final exam

\begin{problem}We consider the gambler's ruin game, where there is some fixed
probability, $0< p < 1$, that the gambler will win each individual 1
dollar bet, and the gambler has some fixed goal of $T$ dollars.

Let $e(n)$ be the expected \emph{number of bets} the gambler must make
until the game ends, where $n \leq T$ is his initial capital, \ie the number
of dollars he starts with.  Then the function $e$ satisfies a linear
recurrence of the form
\[
e(n) = a \cdot e(n+1) + b \cdot e(n-1) + c.
\]
for constants $a,b,c \in \reals$.

\begin{enumerate}
\item What are a\brule{0.5in}, b\brule{0.5in}, c\brule{0.5in}?

\solution{$a=p, b=1-p , c = 1$.

From Notes 13:
Let $Q$ be the number of bets till the Gambler's Ruin game ends.
So
\[
e(n) = \expect{Q} = p\expcond{Q}{\text{gambler wins first bet}} +
q\expcond{Q}{\text{gambler loses first bet}}.
\]
But after the gambler wins the first bet, his capital is $n+1$, so
he can expect to make another $e(n+1)$ bets.  That is,
\[
\expcond{Q}{\text{gambler wins first bet}} = 1 + e(n+1),
\]
and similarly, 
\[
\expcond{Q}{\text{gambler loses first bet}} = 1 + e(n-1).
\]
So we have
\[
e(n) =  p(1 + e_(n+1)) +  q(1 + e(n-1)) =  pe(n+1) + qe(n-1) + 1.
\]
}

\item What are $e(0)$ \brule{0.5in} and $e(T)$ \brule{0.5in}?

\solution{$0,0$.}

\end{enumerate}
\end{problem}



\begin{problem}
We consider an \emph{unbounded} Gambler's Ruin game (where $T = \infty$).
Let $p$ be the probability the Gambler will win an individual \$1 bet, let
$n>0$ be his initial capital, and let $q = 1-p$.  Define $R$ to be the
event that the the Gambler wins his first bet, but that his capital
eventually gets back to where it started at $n$, and let $r \eqdef
\pr{R}$.  Define $D$ to be the event the Gambler's capital ever goes down
to $n-1$, and let $d \eqdef \pr{D}$.

\bparts

\ppart  Explain why $r \leq p$.

\solution{ $R$ can only hold if the Gambler wins the first bet, so by
monotonicity
\[
\pr{R} \leq \pr{\text{Gambler wins first bet}}=p.
\]}

\ppart Explain why $r$ and $d$ do not depend on $n$.  Why isn't this true
in a bounded game?

\solution{Take any walk starting with \$1 and ending when it gets back to
\$1 for the first time after one or more bets.  Note that the first step
of such a walk has to be up, or the Gambler would have gone broke on the
first bet,

Now add $n-1$ to the $y$-coordinate of every point on this walk.  Because
the game is unbounded, the result is a path starting and with capital $n$
and ending when it gets back to $n$ for the first time.  Also, the shifted
path has the same probability as the original path.  This correspondence
is clearly a bijection, since it has an inverse---namely subtract $n-1$.
Hence the sum of the probabilities of the set of all paths starting with
\$1 and ending with a first return to \$1 is the same as the sum for all
paths starting at $n$ and ending at the first step where the capital is
again $n$.  So the probability, $r$, of return to $n$ is the same as the
probability of a return to 1, and therefore does not depend on $n$.  The
same correspondence holds between walks which start at \$1 and end at \$0,
and walks which start at $n$ and end the first time they reach $n-1$, so
$d$ similarly does not depend on $n$.

This correspondence fails if there is a bound on the game, \eg if the
Gambler starts with $n=T$, then the game ends immediately and there is no
chance that the Gambler will win his first bet, because there won't be any
first bet.}


\ppart
Explain why $r = pd$.

\solution{The only way $R$ can occur is if the Gambler wins his first bet, and then
his new stake of $n+1$ eventually goes down to $n$.  That is
\[
r = \pr{R} = \pr{\text{win first bet}}\pr{\text{go from $n+1$ to
$n$}} = pd.
\]
}

\ppart
Argue that
\[
r = pq + prq + pr^2q + \cdots + pr^kq + \cdots.
\]

\solution{ The stake can get back to $n$ for the first time after going up
to $n+1$, by returning to $n+1$ repeatedly $k$ times for some $k \geq 0$
and then going down to $n$.  The probability of this is the probability,
$p$, of going up on the first bet, times the probability, $r^k$, of
repeating $k$ times going above and returning to $n+1$, times the
probability of going from $n+1$ to $n$ on the final bet.  Hence the
probability of going up and eventually getting back to $n$ is the sum of
the probabilities of these disjoint events.}

\ppart
Conclude that if $p \leq 1/2$, then $r = p$.

\solution{
From the previous part, we have
\[
r = pq \sum_{k=0}^\infty r^k = \frac{pq}{1-r}
\]
So we have a quadratic
\[
r^2 - r + pq = 0
\]
so
\begin{align*}
r & = 1 \pm \frac{\sqrt{1-4pq}}{2}\\
  & = 1 \pm \frac{\sqrt{1-4p(1-p)}}{2} \\
  & = 1 \pm \frac{\sqrt{1-4p + 4p^2}}{2} \\
  & = 1 \pm \frac{\sqrt{(2p-1)^2}}{2}\\
  & = 1 \pm \frac{2p-1}{2}\\
  & = \begin{cases}1-p, & \text{or}\\
                   p.
      \end{cases}
\end{align*}

If $p = 1/2$, then $p = 1-p$, so in any case $r = 1/2$.
If $p < 1/2$, then $p < 1-p$, and since $r \leq p$ by the part~(a), we
cannot have $r = 1-p$, so it must be that $r=p$.
}

\ppart Conclude that if $p \leq 1/2$, then the Gambler goes broke with
probability 1, no matter what his initial stake.
\hint First assume his initial capital is \$1.

\solution{
We know that if $p \leq 1/2$, then $r=p$, but we also know $r=pd$.  So $p
= pd$, and since $p\neq 0$, it follows that $d=1$.  In particular, the
Gambler goes broke with probability 1 if his initial capital in \$1.  Now
by induction, assume he goes broke with probability 1 when his initial
capital is $n$.  Then,
\begin{align*}
\lefteqn{\pr{\text{Gambler goes broke with initial capital $n+1$}}}\\
 & = \pr{\text{capital goes from $n+1$ to $n$}}\\
 & \quad \cdot \prcond{\text{go broke}}{\text{initial capital $n$}}\\
 & = d \cdot 1 & \text{(by induction hypothesis)}\\
 & =  1 \cdot 1 = 1.
\end{align*}
}

\ppart Now let $t \eqdef \expect{\text{number of bets till the gambler's
stake first goes down by $\$1$}}$.  Prove that if $t$ is finite, then
\[
\expect{\text{number of bets till the gambler goes bankrupt}} = 
\cfrac{n}{1-2p}.
\]
(It turns out that $t$ is finite iff $p < 1/2$, but we won't prove this
today.)

\hint Prove that $t= 1/(1-2p)$ by conditioning on the first bet.

\solution{
To go down 1, a walk must go down immediately, or else go up 1 and then eventually
down 1, and then eventually go down 1 again.  So,
\[
t = 1\cdot\pr{\text{lose first bet}} + \pr{\text{win first bet}}(1+2t) =
(1-p) + p(2t+1).
\]
That is,
\[
t = 1+2pt,
\]
so if $t\neq \infty$, we conclude that
\[
t= \frac{1}{1-2p}.
\]
Hence, if the gambler starts off with $\$n$, then the expected time to go
bankrupt is $nt=n/(1-2p)$.}

\eparts

\end{problem}

\end{document}
