Gambler's Ruin Problem

A gambler to play potentially infite number of games, each wins 1 unit with probability $p$ and lose 1 unit otherwise.
Starting with $i$ units, what is the probability that the gambler’s fortune will reach $N$ before reaching 0
Given that $P_{00}^{\infty} = P_{NN} = 1$
- meaing he stops playing when he lose all or reaching $N$
and $P_{i, i + 1} = p = 1 - q = 1 - P_{i + 1, i}$ for $i = 1, 2, ..., N - 1$

We have 3 classes, ${0}$ and ${N}$ are transient while ${1, .., N - 1}$ is recurrent
Define $P_{i}$ as probability that the fortune will eventually reach $N$ , $P_{i} = p . P_{i + 1} + q . P_{i - 1}$ for $i = 1, 2, ..., N - 1$
Next:
- $P_{0} = 0$
- $P_{i + 1} - P_{i} = \frac{q}{p} (P_{i} - P_{i - 1})$ for $i = 1, 2, ..., N - 1$
- $P_{2} - P_{1} = \frac{q}{p} (P_{1} - P_{0}) = \frac{q}{p} P_{1}$
- $P_{3} - P_{2} = \frac{q}{p} (P_{2} - P_{1}) = (\frac{q}{p})^{2} P_{1}$
- …
- $P_{i} - P_{i - 1} = \frac{q}{p} (P_{i - 1} - P_{i - 2}) = (\frac{q}{p})^{i - 1} P_{1}$
- Sum from $P_{2}$ to $i - i$ terms $\to P_{i} - P_{1} = P_{1} [(\frac{p}{q}) + (\frac{p}{q})^{2} + ... + (\frac{p}{q})^{i - 1}]$
- $P_{i} = \frac{1 - ( q / p ) ^{i}}{1 - ( q / p )} P_{1}$
  - As $P_{N} = 1 = \frac{1 - ( q / p ) ^{N}}{1 - ( q / p )} P_{1} \to P_{1} = \frac{1 - ( q / p )}{1 - ( q / p ) ^{N}}$
- $\to P_{i} = \frac{1 - ( q / p ) ^{i}}{1 - ( q / p ) ^{N}}$
$P_{i} = {\frac{1 - ( q / p ) ^{i}}{1 - ( q / p ) ^{N}} \frac{i}{N} if p \neq = \frac{1}{2} if p = \frac{1}{2}$
For $n \to \infty$ , $P_{i} = {1 - (\frac{q}{p})^{i} 0 if p > \frac{1}{2} if p \leq \frac{1}{2}$

StrixTheKiet Notes