Section 6.4

Small Absorbing Chains

The probability of ending in a given absorbing state of a small chain: walkers on small grids, checkers on a board, frogs jumping onto a target.

Toolkit

For a Markov chain with absorbing states, let $h_i=\mathbb{P}(\text{absorbed in target}\mid X_0=i)$ . These satisfy the first-step (harmonic) equations

h_i=\sum_j p_{ij}h_j,\qquad h_i=1 \text{ on the target set},\quad h_i=0 \text{ on other absorbing states.}

Solve by:

exploiting symmetry to collapse states (e.g. by distance to a reference point) before writing the equations;
discarding self-loops / no-op transitions and renormalising the remaining probabilities, since they don’t affect $h_i$ ;
treating boundary rows/layers (as in a grid) as known base cases and propagating inward via averaging over legal moves;
recognising the recursion $h_i=\tfrac12(h_{i-1}+h_{i+1})$ -type equations as linear recurrences, solved via characteristic roots, with the two boundary absorbing values fixing the constants.

Problems

6.9 Checker Reaching a Top Corner Easy Free
6.10 Frog Landing on k Medium
6.11 Passing a Ball Around a Circle Medium
6.12 Chopping Heads Off a Dragon Medium
6.13 Escaping on a Triangular Lattice Medium