= Gambler's ruin
{wiki}
<Gambler's ruin> is the absorption problem for a fortune that changes by one unit per game. Let $S_n\in\{0,1,\ldots,N\}$, with <independent> wins of <Probability> $p\in(0,1)$ and losses of <Probability> $q=1-p$. Stop when the fortune reaches zero or the target $N$. Zero is ruin; reaching $N$ is success.
The success <Probability> $h_i=\mathbb P_i(T_N<T_0)$ has boundary values $h_0=0$, $h_N=1$ and satisfies $h_i=ph_{i+1}+qh_{i-1}$. Solving this <recurrence relation>[second-order recurrence] gives
$$
h_i=\begin{cases}
i/N,&p=q=1/2,\\
(1-\rho^i)/(1-\rho^N),&p\ne q,\quad \rho=q/p.
\end{cases}
$$
<Finite-interval exit times have geometric tails>, so absorption occurs <almost surely> and ruin has <Probability> $1-h_i$. The fair case is linear because the fortune itself is <harmonic function for a Markov chain>[harmonic]; the biased case uses the <harmonic function for a Markov chain>[harmonic] <exponential function>[exponential] $\rho^i$.
For a fair game with initial fortune three and target ten, success has <Probability> $3/10$. The <Expected duration of symmetric gambler's ruin> is $i(N-i)$, giving 21 steps in this example. The same local <first-step analysis>[first-step method] produces expected durations, <discounted gambler's ruin hitting probability>[discounted absorption probabilities] and <conditional hitting time>[conditional durations]; their different boundary conditions encode different questions about the same paths.
Back to article page