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

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

%\renewcommand{\problemdata}[5]{}

\begin{document}
\inclassproblems{15, Wed.}


\begin{problem}
\bparts

\ppart 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.  The
gambler starts with $n$ dollars, where $n$ may vary between 0 and $T$.

Let $\epsilon \eqdef p^{T-1}$.  Explain why, if the gambler has not gone
yet bankrupt, he has probability $\geq \epsilon$ of reaching his goal in
$\leq T-1$ more bets.

\solution{Even if the gambler's stake was down to \$1, there is still this
much probability that he will win the next $T-1$ bets in a row and reach
his goal of $T$.}

\ppart Let $s \eqdef T-1$.  Explain why at any point during his play, the
probability that he will make at least $s$ more bets is at most
$1-\epsilon$.

\solution{ If he is not bankrupt, then there is at least an $\epsilon$
chance he will win in fewer than $s$ bets, and so there is at least this
probability that the game will end in fewer than $s$ more bets.  So there
is at most a $1-\epsilon$ probability that the game will not end in fewer
than $s$ bets.}

\ppart Conclude that the probability that the gambler bets forever
---without either going bankrupt or reaching his goal ---is zero.

\solution{We know the probability that the gambler initially makes at
least $s$ bets at most $1-\epsilon$.  The conditional probability that he
makes another $s$ bets given that he initially made $s$ bets is also
$1-\epsilon$, so the probability that he makes at least $2s$ bets is at
most $(1-\epsilon)^2$.  It follows by induction that probability that he
makes $sn$ bets is at most $(1-\epsilon)^{n}$.  Of course, the probability
that the gambler bets forever is $\leq$ the probability that he bets at
least $sn$ times.  But $(1-\epsilon)^n$ approaches 0 as $n \rightarrow
\infty$, so the probability that the gambler bets forever is at most 0.}

\eparts
\end{problem}

\iffalse %F01 pset10 and S02 cp13F

\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}
\fi


%F01 final exam

\begin{problem}
Let $e(n)$ be the expected \emph{number of bets} the gambler must make
until the game ends.

\bparts

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

\solution{$0,0$.}

\ppart The function $e(n)$ 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$.

\ppart What are a\brule{0.5in}, b\brule{0.5in}, c\brule{0.5in}?

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

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

\eparts
\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$.  In this problem, we show
that if $p \leq 1/2$, in particular even in the fair ($p = 1/2$) case, the
gambler is certain to go broke.

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{Call a walk ``good'' if it goes up on its first step and ends
the first time it returns to the height at which it began.  Given
initial capital, $n$, the probability of $R$ is simply the sum of the
probabilities of the good paths starting at $n$.

Now consider any good walk starting with initial capital 1 and add $n-1$
to the $y$-coordinate of every point on this walk.  \emph{Because the game
is unbounded}, the result is a good path starting with capital $n$.  The
shifted path obviously has the same probability as the original path since
it has the same number of up and down moves.

So the sum of the probabilities of the good paths starting at $n$ is the
same as the sum starting with 1, which proves that $r$ is the same for all $n$.

The same correspondence holds between
\begin{itemize}
\item walks which start with capital 1 and end going broke at 0, and
\item  walks which start at $n$ and end the first time they reach $n-1$, 
\end{itemize}
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{(1-2p)^2}}{2}\\
  & = 1 \pm \frac{1-2p}{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}
