\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

A gambler with initial capital \pounds z (where z is a positive
integer) plays a coin tossing game against an infinity rich
opponent.  Two fair coins are tossed: if both show heads the
gambler wins \pounds 2; if both show tails the gambler wins
\pounds 1; otherwise the gambler loosed \pounds 1.

${}$


Letting $q_z$ denote the probability the the gambler is
eventuality ruined, show that $$q_{z+2} + q_{z+1} - 4q_z +
2q_{z-1} = 0$$

${}$

Find the general solution of this difference equation.  Using the
assumption that $q_z \to 0$ as $4z \to \infty$, show that $$q_z =
(\sqrt 3 - 1)^z.$$

${}$

What is the minimum initial capital the gambler needs in order
that he has a better than even chance of not being ruined?

${}$

Suppose the gambler starts with \pounds 1.  Considering the
various possible outcomes, show that the probability of ruin in 5
or fewer steps is $\ds \frac{78}{128}$



\vspace{.25in}

{\bf Answer}

Let $q_z$ denote the probability of ruin, with initial capitial
\pounds z.  Arguing conditionally on the result of the first bet
gives $$q_z = \frac{1}{4} \cdot q_{z+2} + \frac{1}{4} q_{z+1} +
\frac{1}{2}q_{z-1}$$ Rearranging this gives $$ q_{z+2} + q_{z+1}
-4q_z + 2q_{z-1}=0$$To find the general solution put $q_z =
\lambda ^z$.  This gives  the auxillary equation \begin{eqnarray*}
\lambda^3 + \lambda^2 - 4\lambda + 2 & = & 0 \\
(\lambda-1)(\lambda^+2\lambda-2) & = & 0 \\ {\rm So \ \ } \lambda
& = & 1, \, -1-\sqrt3, \, -1+\sqrt 3 \end{eqnarray*} Thus $\ds q_z
= A + B(-1 -\sqrt3)^z + C(-1+\sqrt3)^z$

Now $q_z$ is a probability  and since $-1-\sqrt3<-1$ and
$0<-1+\sqrt3<1$, we cannot have the righthand side between the )
and 1 unless B=0.  Now $\ds (-1-\sqrt3)^z\to0$ as $z\to \infty$
and so assuming $q_z \to 0$ as $z\to \infty$ we conclude that A=0.
Hence $$q_z = C(-1+\sqrt 3)^z, $$ and finally $q_0 = 1$ gives
$C=1.$

${}$

Now in order to have $q_z < \frac{1}{2}$ we must have
$\ds(-1+\sqrt3)^z < \frac{1}{2}$ i.e., $z \ln (-1+\sqrt3)<-\ln 2$
giving $\ds z>\frac{-\ln 2}{\ln(-1+\sqrt3)} = 2.22...$ so $\pounds
z \geq \pounds 3$.

Starting with \pounds 1, the paths leading to ruin in 5 or fewer
steps are:

\begin{tabular}{llr}

  1 step & L & prob $\ds \frac{1}{2}$ \\
  2 steps & IMPOSSIBLE &  \\
  3 steps & W(1) L L &  $\ds\frac{1}{2^4}$ \\
  4 steps & W(2) L L L  & $\ds\frac{1}{2^5}$ \\
  5 steps & W(1) W(1) L L L  & $\ds\frac{1}{2^7}$ \\
   & W(1) L W(1) L L  & $\ds\frac{1}{2^7}$ \\
\end{tabular}

So $\ds p= \frac{1}{2^7} (64 8 4 1 1) = \frac{78}{128}$

\setlength{\unitlength}{0.3in}
\begin{picture}(5,6)
\put(0.5,1){\line(1,0){8}}

\put(1,0.5){\line(0,1){5}}

\multiput(0.9,2)(0,1){4}{\line(1,0){0.2}}

\multiput(2,0.9)(1,0){6}{\line(0,1){0.2}}

\put(7,0.6){\makebox(0,0){steps}}

\put(2,0.6){\makebox(0,0){1}}

\put(3,0.6){\makebox(0,0){2}}

\put(4,0.6){\makebox(0,0){3}}

\put(5,0.6){\makebox(0,0){4}}

\put(6,0.6){\makebox(0,0){5}}

\put(0.5,5){\makebox(0,0){\pounds}}

\put(0.5,2){\makebox(0,0){1}}

\put(0.5,3){\makebox(0,0){2}}

\put(0.5,4){\makebox(0,0){3}}

\put(1,2){\line(1,-1){1}}

\put(1,2){\line(1,1){1}}

\put(2,3){\line(1,-1){2}}

\put(1,2){\line(1,2){1}}

\put(2,4){\line(1,-1){3}}

\put(1,2){\line(1,1){2}}

\put(3,4){\line(1,-1){3}}

\put(2,3){\line(1,-1){1}}

\put(3,2){\line(1,1){1}}

\put(4,3){\line(1,-1){1}}

\end{picture}



\end{document}
