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

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

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

\begin{document}
\inclassproblems{14M}

%F01 final exam

\begin{problem} (Carried over from Friday)
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} (Carried over from Friday)
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}


\begin{problem}\label{noAi} (Carried over from Wednesday)

In this problem you will check a proof of the following:
\begin{theorem*}
Let $A_1, A_2, \dots, A_n, \dots$ be mutually independent events, and let
$T$ be the number of these events that occur.  The probability that none
of the events occur is at most $e^{-\expect{T}}$.
\end{theorem*}

To prove the Theorem, note that
\begin{equation}\label{Tsum}
T = \sum_{i=1}^\infty T_i,
\end{equation}
where $T_i$ is the indicator variable for the event $A_i$.  Also, remember
that
\begin{equation} \label{1+xeleq}
1 + x \leq e^x
\end{equation}
for all $x$ and
\begin{equation} \label{1+xesim}
1 + x \approx e^x,
\end{equation}
for $0 \leq x \leq 1$.  Both~(\ref{1+xeleq}) and~(\ref{1+xesim}) follow
from the Taylor's expansion of $e^x$.

\bparts

\ppart
Justify each line in the following derivation:

\begin{proof}
\begin{align*}
\pr{T = 0}
  & = \pr{\bar{\lgunion_{i=1}^\infty A_i}}\\
  & =  \pr{\lgintersect_{i=1}^\infty \bar{A_i}}\\
  & =  \prod_{i=1}^\infty (1 - \pr{A_i})\\
  & \leq  \prod_{i=1}^\infty e^{-\pr{A_i}}\\
  & =  e^{-\sum_{i=1}^\infty \pr{A_i}}\\
  & =  e^{-\sum_{i=1}^\infty \expect{T_i}}\\
  & =  e^{-\expect{T}}.
\end{align*}
\end{proof}

\solution{
\begin{proof}
\begin{align*}
\pr{T = 0}
  & = \pr{\bar{\lgunion_{i=1}^\infty A_i}}
               & \text{(def. of $T$)}\\
  & =  \pr{\lgintersect_{i=1}^\infty \bar{A_i}}
          & \text{(De Morgan's law)}\\
  & =  \prod_{i=1}^\infty \pr{\bar{A_i}} & \text{(mutual independence of $A_i$'s)}\\
  & =  \prod_{i=1}^\infty 1 - \pr{A_i} & \text{(complement rule)}\\
  & \leq  \prod_{i=1}^\infty e^{-\pr{A_i}} & \text{(by~(\ref{1+xeleq}))}\\
  & =  e^{-\sum_{i=1}^\infty \pr{A_i}} & \text{(exponent algebra)}\\
  & =  e^{-\sum_{i=1}^\infty \expect{T_i}} & \text{(expectation of indicator variable)}\\
  & =  e^{-\expect{T}}. & \text{((\ref{Tsum}) \& linearity of expectation)}
\end{align*}
\end{proof}
}

\eparts

Two special cases of the Theorem are worth singling out because they come
up all the time.
\begin{corollary*}
Suppose an event has probability $1/m$.  Then the probability that the
even will occur at least once in $m$ independent trials is approximately
$1- 1/e \approx 63\%$.  There is a 50\% chance the event will occur in $n
= \log 2 m \approx 0.69m$ trials.
\end{corollary*}

\bparts

\ppart
Prove the Corollary.

\solution{
In this case, $\pr{A_i}=1/m$ for $1\leq i \leq n$ and
\[
\expect{\text{\# occurrences}} = n \frac{1}{m} = \frac{n}{m}.
\]
So by the Theorem,
\[
\pr{\text{no occurrence}} \leq e^{-(n/m)},
\]
and therefore
\begin{equation}\label{1-enm}
\pr{\text{at least one occurrence}} \geq 1 - e^{-(n/m)}.
\end{equation}
In fact, it follows from by~(\ref{1+xesim}), that the $\geq$
in~(\ref{1-enm}) is an approximate equality.

So if the number, $n$ of trials is $m$, we have
\[
\pr{\text{at least one occurrence}} \approx 1- e^{-(m/m)} = 1-\frac{1}{e}.
\]

If we want
\[
1 - e^{-(n/m)} \approx \pr{\text{at least one occurrence}} \approx
\frac{1}{2},
\]
then we need
\[
e^{-(n/m)} \approx \frac{1}{2},
\]
so taking log's we conclude
\[
n \approx m\log 2.
\]
}
\eparts

\end{problem}

\end{document}
