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