xx. Gambler's Ruin

Problem. A gambler with $i$ units bets 1 unit per round, winning with probability $p$ (losing with $q=1-p$), until reaching $N$ or $0$. What is the probability of reaching $N$?

$P_i=\{\begin{array}{ll}\frac{i}{N}& p=\frac{1}{2}\\ \frac{1-(q/p{)}^i}{1-(q/p{)}^N}& p\ne \frac{1}{2}\end{array}\text{expected duration (fair): }i(N-i).$

double ruinWin(int i, int N, double p) {          // P(reach N before 0) from i, win each step with probability p
    if (fabs(p - 0.5) < 1e-12) return (double)i / N;
    double r = (1 - p) / p;
    return (1 - pow(r, i)) / (1 - pow(r, N));
}

Proof: the ruin probability and duration

$P_i$ satisfies $P_i=p{P}_{i+1}+q{P}_{i-1}$ with $P_0=0$, $P_N=1$. Rewrite as $P_{i+1}-P_i=\frac{q}{p}(P_i-P_{i-1})$, so the differences form a geometric sequence with ratio $r=q/p$ and $P_i=P_1(1+r+\cdots +r^{i-1})$. For $r=1$ this is $i{P}_1$, and $P_N=1$ gives $P_1=1/N$; otherwise $P_i=P_1\frac{1-r^i}{1-r}$ and normalizing at $N$ gives the formula. For the fair duration, $D_i=1+\frac{1}{2}(D_{i+1}+D_{i-1})$ with $D_0=D_N=0$ is solved by $D_i=i(N-i)$ (second difference $-2$). Checked against value iteration for $N\le 12$.