gambler's ruin

If a gambler, starting with x=1, plays a fair game (p = 1/2) in which he wins or loses 1 unit on each play, he would be certain to lose all his money eventually, even though the game is fair. However, a counter-intuitive fact is that the avg #(rounds) til bankruptcy is not finite.

In order to have an even chance of not going bankrupt, the game must be a favourable one with p = 2/3 or greater.

gambler has $i$ dollars to start. each round, he either wins $1 with probability p or loses $1 with probability q = 1-p. he will stop once he makes $N$ dollars or loses everything. P(he ends up with $N$ dollars)?

Let $P_i$ = the prob he ends up with $N$ dollars from any initial state $0\le i\le N$, so the boundary probabilities are $P_0=0$ and $P_N=1$

The probability of reaching $Nfromidollarsdependsontheprobabilitiesofreaching$N from $i+1(afterawin)andfrom$i-1 (after a loss), so we have the recurrence relation $P_i=p{P}_{i+1}+q{P}_{i-1}$

Let’s try to get a closed form solution:

$$\begin{array}{rl}{P}_{i+1}-P_i& =\frac{1}{p}(P_i-q{P}_{i-1})-P_i\\ & =\frac{1}{p}(P_i-q{P}_{i-1})-\frac{p{P}_i}{p}\\ & =\frac{1}{p}(P_i-q{P}_{i-1}-p{P}_i)\\ & =\frac{1}{p}((1-p)P_i-q{P}_{i-1})\\ & =\frac{q}{p}(P_i-P_{i-1})\\ & ={\left(\frac{q}{p}\right)}^2(P_{i-1}-P_{i-2})\\ & =\dots \\ & ={\left(\frac{q}{p}\right)}^i(P_1-P_0)\\ & ={\left(\frac{q}{p}\right)}^i{P}_1\\ P_{i+1}& ={\left(\frac{q}{p}\right)}^i{P}_1+P_i\end{array}$$

Using this, we get

$$\begin{array}{rl}{P}_2& =\left[1+\frac{q}{p}\right]P_1\\ P_3& =\left[1+\frac{q}{p}+{\left(\frac{q}{p}\right)}^2\right]P_1\\ & ⋮\\ P_i& =\left[1+\frac{q}{p}+\cdots +{\left(\frac{q}{p}\right)}^{i-1}\right]P_1\\ & =\{\begin{array}{ll}\frac{1-(q/p{)}^i}{1-q/p}{P}_1,& \text{ if }q/p\ne 1\\ i{P}_1,& \text{ if }q/p=1\end{array}\end{array}$$

Using $P_N=1$, we have

$$\begin{array}{rl}{P}_N=1& =\{\begin{array}{ll}\frac{1-(q/p{)}^N}{1-q/p}{P}_1,& \text{ if }q/p\ne 1\\ N{P}_1,& \text{ if }q/p=1\end{array}\\ \Rightarrow P_1& =\{\begin{array}{ll}\frac{1-q/p}{1-(q/p{)}^N},& \text{ if }q/p\ne 1\\ 1/N,& \text{ if }q/p=1\end{array}\\ \Rightarrow P_i& =\{\begin{array}{ll}\frac{1-(q/p{)}^i}{1-(q/p{)}^N}{P}_1,& \text{ if }p\ne 1/2\\ i/N,& \text{ if }p=1/2\end{array}\end{array}$$