\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer} \&
Dr.~Radhika~Nagpal}

\renewcommand{\reading}{
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln13-14.pdf}
{Week 13-14 Notes}}

\begin{document}
\problemset{13-14}

%%-----------------------------------------------------------------------%%
%\problemdata      
%        {?} % latex-friendly label for the prob.
%        {Probability-Variance} % The topic(s) of the problem content.
%        {?} % Source (if known)
%        {Fall 2001, final} % Usage (list ones you are aware of).
%        {Christos Kapoutsis, S02} % Last revision info (author, date).


\begin{problem}
A gambler plays 120 hands of draw poker, 60 hands of black jack,
and 20 hands of stud poker per day.  He wins a hand of draw poker with
probability 1/6, a hand of black jack with probability 1/2, and a hand of
stud poker with probability 1/5.  Assume the outcomes of the card games are
mutually independent.  %He hopes to win 108 hands per day.

\bparts

\ppart What is the expected number of hands the gambler wins in a day?

\solution{
$120(1/6)+60(1/2)+20(1/5)=54$.
}

\ppart What is the variance in the number of hands won per day?

\solution{
The variance can also be calculated using linearity of
variance.  For an individual hand the variance is $p(1-p)$ where $p$ is
the probability of winning.  Therefore the variance is
$120(1/6)(5/6) + 60(1/2)(1/2) + 20(1/5)(4/5) = 50/3 + 15 + 16/5 = 250/15 +
225/15 + 48/15 = 523/15 = 34\ 13/15$.
}

\ppart What would the Markov bound be on the probability that the
gambler will win 108 hands on a given day?

\solution{
The expected number of games won is 54, so
by Markov, $\pr{R \geq 108} \leq 54/108 = 1/2$.
}

\ppart What would the Chebyshev bound be on the probability that the
gambler will win 108 hands on a given day?

\solution{
\[
\pr{R - 54 \geq 54} \leq \pr{\abs{R - 54} \geq 54} \leq \frac{V}{54^2} = 
\frac{523/15}{54^2} \approx 1/85.
\]

}

\ppart Apply the Chernoff bound for the probability that the gambler will
win the 108 hands to find the largest integer, $n$, such that the bound is
less than $e^{-n}$.  \hint $\ln 2 \approx 0.7$.

\solution{
Answer: $n=21$.
\begin{align*}
\pr{R \geq 108} & = \pr{R \geq 2\cdot 54}\\
     & \leq \textup{exp}(- (2\ln 2 - 2 + 1)54)\\
     & = \textup{exp}(-108\ln 2 + 54)\\
     & \approx \textup{exp}(- 108\cdot0.7+54)\\
     & \approx \textup{exp}(- 75.6 -54)\\
     & \approx \textup{exp}(- 21.6)\\
     & \approx \cfrac{1}{2,400,000,000}
\end{align*}
}

\eparts
\end{problem}

\iffalse

%       \problemdata       % Takes 5 *mandatory* arguments
%        {variance-6}             % latex-friendly label for the prob.
%        {variance}               % The topic of the problem content.
%        {Velleman}               % Source (if known)
%        {S98 PS11-7; F97 PS11-8} % Usage (list ones you are aware of).
%        {Theory Pig, S02}        % Last revision info (author, date).
\begin{problem} %source: spring00 ps10-5
Let $X$ and $Y$ be independent random variables taking on
integer values in the range $1$ to $n$ uniformly.  Compute the
following quantities: 

\begin{problemparts}

\problempart $\variance{aX+bY}$

\solution{First, we compute $\variance{X}$, 
which is also $\variance{Y}$ since $X$ and $Y$ are identically distributed.
\begin{align*}
\variance{X}
        & = \expect{X^2} - \expect{X}^2 
        = \sum_{i=1}^n i^2 \cdot \frac{1}{n}
                - \left( \sum_{i=1}^n i \cdot \frac{1}{n} \right)^2 \\
        & = \frac{(n+1)(2n+1)}{6} - \frac{(n+1)^2}{4} 
        = \frac{n^2 - 1}{12}
\end{align*}

We now use this to compute $\variance{aX + bY}$: 
\begin{align*}
\variance{aX+bY}
        & = \variance{aX} + \variance{bY} 
                & & \text{because $aX$ and $bY$ are independent} \\
        & = a^2 \variance{X} + b^2 \variance{Y}
                & & \text{Theorem~4.4 in Lecture Notes 24} \\
        & = (a^2 + b^2) \variance{X}
                & & \text{because $\variance{X} = \variance{Y}$} \\
        & = (a^2 + b^2) \frac{n^2 - 1}{12}
                & & \text{substitution from computation above}
\end{align*}
}

\problempart $\expect{|X-Y|}$

\solution{We could compute this directly. 
However, note that $|X - Y| = \max(X,Y) - \min(X, Y)$.  
Thus,
\begin{align*}
\expect{|X - Y|}
        & = \expect{\max(X, Y) - \min(X, Y)} \\
        & = \expect{\max(X, Y)} - \expect{\min(X, Y)} \\
        & = \frac{(n+1)(4n-1)}{6n} - \frac{(n+1)(2n+1)}{6n} \\
        & = \frac{n^2 - 1}{3n}
\end{align*}
}

\problempart $\variance{|X-Y|}$.

\solution{
We start with one of the standard formulas for variance:
\[
\variance{|X - Y|}
        = \expect{|X-Y|^2} - \expect{|X-Y|}^2 
        = \expect{(X-Y)^2} - \expect{|X-Y|}^2
\]

We could compute $\expect{(X-Y)^2}$ directly, 
but note that 
$\variance{X-Y} = \expect{(X-Y)^2} - \expect{X-Y}^2$, 
and $\expect{X-Y} = 0$. 
We can compute $\variance{X-Y}$ using the 
result in part (a). 
Thus, 
\begin{align*}
\variance{|X - Y|}
        & = \variance{X - Y} - \expect{|X-Y|}^2 \\
        & = (1^2 + (-1)^2) \cdot \frac{n^2 - 1}{12} -
                \left(\frac{n^2 - 1}{3n}\right)^2 \\
        & = \frac{(n^2 - 1)(n^2 + 2)}{18 n^2}
\end{align*}
}

\end{problemparts}
\end{problem}
\fi

%        \problemdata       % Takes 5 *mandatory* arguments
%        {variance-6}             % latex-friendly label for the prob.
%        {variance}               % The topic of the problem content.
%        {Velleman}               % Source (if known)
%        {S98 PS11-7; F97 PS11-8} % Usage (list ones you are aware of).
%        {Theory Pig, S02}        % Last revision info (author, date).
\begin{problem}
A man has a set of $n$ keys, one of which fits the door
to his apartment.  He tries the keys until he
finds the correct one.  Give the expected number and variance
for the number of trials until success if

\begin{problemparts}

\problempart he tries the keys at random (possibly repeating a key tried
       earlier)


\solution{
There are $n-1$ wrong keys and $1$ right key. 
Each time the man chooses a key, he tries it and then places it back to the key set.
Let $T$ be the waiting time for the man to pick the right key. 
$T=k$ means that on the $k$-th trial the man picks the right key.
The probability of picking the right key on the first trial is $1/n$,
and the probability of picking the wrong key is $(n-1)/n$.  The
probability stays the same on all subsequent trials since the picked
key is always returned to the key set. Thus
\[
P(T=k) = \left(\frac{n-1}{n}\right)^{k-1}\frac{1}{n}{.}
\]
Note: this is the same as the waiting time for the first head in the
Bernouli process with a biased coin. Let $p=1/n$ and let $q=1-p$.
Then, the expectation of $T$ is
\[
E(T) = \sum_{k=1}^\infty{k q^{k-1}p}
= p\sum_{k=1}^\infty{k q^{k-1}}
= p\frac{1}{(1-q)^2} = \frac{1}{p} = n
\]

The variance of $T$ can be computed directly from the formula,
\[
\variance{T} = E(T^2) - E^2(T){.}
\]
Again, by definition we have
\[
E(T^2) = \sum_{k=1}^\infty{k^2 pq^{k-1}}{.}
\]
How do we evaluate this sum? We use the following trick. We know that
\[
\sum_{k=1}^\infty{kq^k} = q\sum_{k=1}^\infty{kq^{k-1}} = \frac{q}{(1-q)^2}{.}
\]
Moreover,
\begin{eqnarray*}
\sum_{k=1}^\infty{k^2 q^{k-1}} &=& \sum_{k=1}^\infty{\frac{d}{dq}k q^k}\\
 &=& \frac{d}{dq}\sum_{k=1}^\infty{k q^k}\\
 &=& \frac{d}{dq}\frac{q}{(1-q)^2}\\
 &=& \frac{1}{(1-q)^2} + \frac{2q}{(1-q)^3} = \frac{1}{p^2} + \frac{2q}{p^3}{.}
\end{eqnarray*}
Finally, the expectation $E(T^2)$ is
\[
E(T^2) = p \left(\frac{1}{p^2} + \frac{2q}{p^3}\right) = \frac{1}{p} + \frac{2q}{p^2} {,}
\]
and the variance is
\[
\variance{T} = \frac{1}{p} + \frac{2q}{p^2} - \frac{1}{p^2} = \frac{q}{p^2} = n(n-1){.}
\]
}

\problempart he chooses keys randomly from among those he has not
       yet tried.

\solution{
$T=k$ means that the man picks the wrong key on the first
trial, and he picks the wrong key on the second trial, etc, and he picks
the right key on the $k$-th trial. Let $K_i$ be the indicator random
variable for the $i$-th trial, i.e. $K_i=1$ if he picks the right key
on the $i$-th trial, and $0$ otherwise. Then
\[
P(T=k) = P((K_1=0) \& (K_2=0) \&\cdots\& (K_{k-1}=0) \& (K_k=1)){.}
\]
By the Multiplication Theorem we can compute
\begin{eqnarray*}
P(T=k) &=& P(K_1=0)P(K_2=0|K_1=0)P(K_3=0|K_1=0,K_2=0)\cdots\\
 & &\hspace{2in}\cdots P(K_k=1|K_1=0,\dots,K_{k-1}=0)\\
 &=& \frac{n-1}{n}\ \frac{n-2 }{n-1}\ \frac{n-3 }{n-2}\ \cdots\ \frac{n-k+1}{n-k+2}\ \frac{1}{n-k+1}\\
 &=& \frac{1}{n}{.}
\end{eqnarray*}
The expectation and variance are now easy to compute from the definitions.
\[
E(T) = \sum_{k=1}^n{kP(T=k)} = \frac{1}{n}\sum_{k=1}^n{k} = \frac{n+1}{2}{.}
\]
\begin{eqnarray*}
\variance{T} &=& E(T^2) - E^2(T)\\
 &=& \sum_{k=1}^n{k^2 P(T=k)} - \left(\frac{n+1}{2}\right)^2\\
 &=& \frac{1}{n}\sum_{k=1}^n{k^2} - \left(\frac{n+1}{2}\right)^2\\
 &=& \frac{1}{n}\ \frac{n(n+1)(2n+1)}{6} - \left(\frac{n+1}{2}\right)^2\\
 &=& \frac{n^2-1}{12}{.}
\end{eqnarray*}
}

\end{problemparts}
\end{problem}


\begin{problem} %source: spring00 ps10-5
We have two coins: one is a fair coin and the other is a coin that
produces heads with probability 3/4.  One of the two coins is picked,
and this coin is tossed $n$ times. How many tosses suffice to make us
95\% confident which coin was chosen?  Explain.

\iffalse
\bparts

\ppart Does the Weak Law of Large Numbers allow us to \emph{predict}
what limit, if any, is approached by the expected proportion of heads
that turn up as $n$ approaches infinity?  Briefly explain.

\solution{ The Weak Law of Large Numbers tells us that the proportion
of heads will approach $1/2$ if the fair coin was picked, and it will
approach $3/4$ if the other coin was picked.  But it does not tell us
anything about which of these two numbers it will approach, as we have
no information about which coin is picked.  }

\ppart How many tosses suffice to make us 95\% confident which coin
was chosen?  Explain.
\fi

\solution{

To guess which coin was picked, set a threshold $t$ between $1/2$ and
$3/4$.  If the proportion of heads is less than the threshold, guess
it was the fair coin; otherwise, guess the biased coin.  Let the
random variable $H_n$ be the number of heads in the first $n$ flips.
We need to flip the coin enough times so that $\Pr(H_n/n > t) \leq
0.05$ if the fair coin was picked, and $\Pr(H_n/n < t) \leq 0.05$ if
the biased coin was picked.  A natural threshold to choose is $5/8$,
exactly in the middle of $1/2$ and $3/4$.

$H_n$ is the sum of independent Bernoulli variables, which each have
variance $1/4$ for the fair coin and $3/16$ for the biased coin.
Using Chebyshev's Inequality for the fair coin,
\begin{align*}
\Pr\left(\frac{H_n}{n} > \frac{5}{8} \right) 
        & = \Pr\left(\frac{H_n}{n} - \frac{1}{2} > \frac{5}{8} - \frac{1}{2}\right) 
          = \Pr\left(H_n - \frac{n}{2} > \frac{n}{8} \right) \\
        & = \Pr\left(H_n - \expect{H_n} > \frac{n}{8} \right) 
          \leq \Pr\left(|H_n - \expect{H_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{n/4}{n^2/64} 
          = \frac{16}{n}
\end{align*}
For the biased coin, we have
\begin{align*}
\Pr\left(\frac{H_n}{n} < \frac{5}{8} \right) 
        & = \Pr\left(\frac{3}{4} - \frac{H_n}{n} > \frac{3}{4} - \frac{5}{8}\right) 
          = \Pr\left(\frac{3n}{4} - H_n > \frac{n}{8} \right) \\
        & = \Pr\left(\expect{H_n} - H_n > \frac{n}{8} \right) 
          \leq \Pr\left(|H_n - \expect{H_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{3n/16}{n^2/64} 
          = \frac{12}{n}
\end{align*}
We are 95\% confident if these are at most $0.05$, 
which is satisfied if $n \geq 320$. 

Because the variance of the biased coin is less that of the fair coin, 
we can do slightly better if make our threshold 
a bit bigger, to about $0.634$, 
which gives 95\% confidence with 279 coin flips. 

Because $H_n$ has a binomial distribution, 
we can get a much better bound using the estimates 
from Lecture 21, 
giving 95\% confidence when $n > 42$. 
}

\end{problem}



%        \problemdata       % Takes 5 *mandatory* arguments
%        {variance-6}             % latex-friendly label for the prob.
%        {variance}               % The topic of the problem content.
%        {Velleman}               % Source (if known)
%        {S98 PS11-7; F97 PS11-8} % Usage (list ones you are aware of).
%        {Theory Pig, S02}        % Last revision info (author, date).
% fall 01, problem set 12, problem 4

\begin{problem} \textbf{An Unbiased Estimator}

Suppose we are trying to estimate some physical parameter $p$.  When
we run our experiments and process the results, we obtain an estimator
of $p$, call it $p_e$.  But if our experiments are probabilistic, then
$p_e$ itself is a random variable which has a pdf over some range of
values.  We call the random variable $p_e$ an \emph{unbiased}
estimator if $\expect{p_e}=p$.

For example, say we are trying to estimate the height, $h$, of Green
Hall.  However, each of our measurements has some noise that is, say,
Gaussian with zero mean.  So each measurement can be viewed as a
sample from a random variable $X$.  The expected value of each
measurement is thus $\expect{X} = h$, since the probabilistic noise
has zero mean.  Then, given $n$ independent trials, $x_1, ..., x_n$,
an unbiased estimator for the height of Green Hall would be
\[
h_e = \frac{x_1+...+x_n}{n},
\]
since
\[
\expect{h_e} = \expect{\frac{x_1+...+x_n}{n}} = \frac{\expect{x_1} + ... +
\expect{x_n}}{n} = \expect{x_1}= h.
\]

Now say we take $n$ independent observations of a random variable $Y$.
Let the true (but unknown) variance of $Y$ be $\variance{Y} = \sigma^2$.
Then, using the alternative definition of variance:
\[
\variance{Y} = \expect{Y^2} - \expectsq{Y},
\]
we could by the same reasoning use $\sigma_e$ as an estimate of
$\sigma$, where
\[
\sigma_e^2 \eqdef \frac{y_1^2 + y_2^2 + \ldots + y_n^2}{n} -
               \left(\frac{y_1 + y_2 + \ldots + y_n}{n}\right)^2.
\]


\iffalse
(see section 6.4 in the
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l13.pdf}{notes}),
we can define the following estimator $\sigma_e^2$ for $\variance{Y}$ 
using the data from our observations:
\[
\sigma_e^2 =  \frac{y_1^2 + y_2^2 + \ldots + y_n^2}{n} -
                \left(\frac{y_1 + y_2 + \ldots + y_n}{n}\right)^2.
\]
\fi

Now it turns out that $\expect{\sigma_e^2} \neq \sigma^2$, but a minor
modification of the definition yields an unbiased estimator
$\paren{\sigma^{\prime}_e}^2$.

\bparts

\ppart What is $\expect{\sigma_e^2}$?

\solution{
Let $\sigma^2=\variance{X}, \mu=\expect{X}$.  Then our estimator
$\sigma^2_e$ is given by
\begin{eqnarray*}
\sigma^2_e&=&\frac{\sum
  y_i^2}{n} - \left(\frac{\sum y_i}{n}\right)^2\\
\expect{\sigma^2_e}&=&\expect{\frac{\sum
  y_i^2}{n} - \left(\frac{\sum y_i}{n}\right)^2}\\
&=&\frac{\sum
  \expect{y_i^2}}{n} - \frac{\expect{(\sum y_i)^2}}{n^2}\\
&=&\frac{\sum(\sigma^2+\mu^2)}{n} - \frac{\variance{\sum
    y_i}+\expectsq{\sum y_i}}{n^2}\\ 
&=&\frac{n(\sigma^2+\mu^2)}{n} - \frac{n\sigma^2+n^2\mu^2}{n^2}\\
&=&\sigma^2\left(1-\frac{1}{n}\right)
\end{eqnarray*}
So this gives a biased estimator.
}

\ppart How should the unbiased estimator $\paren{\sigma^{\prime}_e}^2$ be
defined?

\solution{We can make the previous estimate unbiased simply by
defining
\[
\paren{\sigma^{\prime}_e}^2 \eqdef \frac{n}{n-1}\sigma_e,
\]
so
\[
\expect{\paren{\sigma^{\prime}_e}^2} = \frac{n}{n-1}\expect{\sigma_e} =
\frac{n}{n-1}\left(1-\frac{1}{n}\right)\sigma^2 = \sigma^2.
\]
}

\eparts

\end{problem}

\begin{problem}
The covariance, ${\rm Cov}(X,Y)$, of two random variables, $X$ and $Y$, is
defined to be $E(XY) - E(X)E(Y)$. Note that if two random variables are
independent, then their covariance is zero.

\bparts 

\ppart Give an example to show that having ${\rm Cov}(X,Y)=0$ does not
necessarily mean that $X$ and $Y$ are independent.

\solution{

Let $(X,Y)$ have joint probability given by the table below:

\begin{center}
\begin{tabular}{|c|c|c|} \hline
$X$ & $Y$ & P \\ \hline
$-1$ & $1$ & $\frac{1}{3}$ \\ \hline
$0$ & $0$ & $\frac{1}{3}$ \\ \hline
$1$ & $1$ & $\frac{1}{3}$ \\ \hline
\end{tabular}
\end{center}

Note that $X$ and $Y$ are not independent.  $P(X=1 \mbox{ \& } Y=1) =
\frac{1}{3} \neq \frac{2}{9} = P(X=1)P(Y=1)$.  But $E(X) = 0$ and $E(XY) =
0$ (since $XY=X$).  Thus ${\rm Cov}(X,Y) = 0$.
}

\ppart Let $X_1,\ldots,X_n$ be random variables.  Prove that
\[
{\rm Var}(X_1+\ldots+X_n)=\sum_{i=1}^n {\rm Var}(X_i) + 2\sum_{i<j} {\rm Cov}(X_i,X_j)
\]

\solution{

\begin{eqnarray*}
{\rm Var}(X_1+\ldots+X_n) & = & E\left[X_1 + \ldots +X_n)^2\right] -
E\left[X_1+\ldots+X_n)\right]^2 \\
& = & E\left[\sum_i X_i^2+(\sum_{i < j}2X_iX_j)\right] - \left[\sum_iE(X_i)^2 +
\sum_{i<j}2E(X_i)E(X_j)\right] \\
& = & \sum_i E(X_i^2) + \sum_{i<j} 2E(X_iX_j) - \sum_iE(X_i)^2 -
\sum_{i<j} 2E(X_i)E(X_j) \\
& = & \sum_i E(X_i^2) - E(X_i)^2 + \sum_{i<j}2(E(X_iX_j) - E(X_i)E(X_j))
\\
& = & \sum_i {\rm Var}(X_i) + 2\sum_{i<j} {\rm Cov}(X_i,X_j)
\end{eqnarray*}
}


\eparts

\end{problem}


%F01 pset10
\begin{problem}

A Gambler plays a game in casino. Let $p$ be some fixed probability he
will win an individual \$1 bet and get back \$2.  Let $q = 1-p$ be the
probability he will lose the \$1 bet. The Gambler has some fixed goal
of $T$ dollars.

\bparts

\ppart
Let $e(n)$ be the expected \emph{number of bets} the Gambler must make
until the game ends (the Gambler either gets \$T or is bankrupt), 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$. What are a, b and c?

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


We consider $T = \infty$. 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}$.

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

