Lagmental Vicfred

Gambler's Ruin Solves a Discrete Harmonic Equation by Vicfred

tags: mathematics, Markov chains, stationary distributions, random walks

A biased random walk between zero and N reaches N with a probability satisfying a two-point recurrence. This is a compact note, but the quantifiers and hypotheses stay on the page.

Objects and notation

A discrete-time Markov chain has transition matrix \(P=(p_{ij})\) and forgets the past after conditioning on the present. Matrix powers \(P^n\) give multi-step transition probabilities.

$$ h_i=p\,h_{i+1}+q\,h_{i-1},\qquad h_0=0,\quad h_N=1 $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ h_i=\begin{cases}\dfrac{1-(q/p)^i}{1-(q/p)^N},&p\ne q,\\[8pt]\dfrac iN,&p=q=\tfrac12,\end{cases} $$

Push the symbols

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ \begin{aligned}p r^2-r+q&=0,\\r&\in\left\{1,\frac qp\right\},\\h_i&=A+B(q/p)^i.\end{aligned} $$

Structural reading

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad h_i=p\,h_{i+1}+q\,h_{i-1},\qquad h_0=0,\quad h_N=1,\\[5pt] \mathsf{C}\;&:\quad h_i=\begin{cases}\dfrac{1-(q/p)^i}{1-(q/p)^N},&p\ne q,\\[8pt]\dfrac iN,&p=q=\tfrac12,\end{cases}. \end{aligned} $$

A hypothesis worth keeping

A stationary distribution need not be unique without irreducibility, and convergence to it can fail without aperiodicity.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] h_i=\begin{cases}\dfrac{1-(q/p)^i}{1-(q/p)^N},&p\ne q,\\[8pt]\dfrac iN,&p=q=\tfrac12,\end{cases} \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Wed 25 March 2009. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.