absorbing chains and the fundamental matrix

Some states are traps: once the chain lands there, it never leaves. An absorbing state i has P(i, i) = 1 — a self-loop with all the probability, so it swallows the chain forever. An absorbing chain is one where every state can eventually reach some absorbing state. Think of a game that must eventually end (you win or you lose), or a queue that eventually empties for good. The interesting questions become: which trap do we fall into, and how long do we wander first?

Organise the states into transient ones (those you eventually leave) and absorbing ones. Written in blocks, the transition matrix has a Q block giving transient-to-transient moves. The central object is the fundamental matrix N = (I - Q)^(-1), the inverse of identity minus Q. Its entry N(i, j) is the expected number of visits to transient state j before absorption, starting from transient state i. From N everything flows: the expected number of steps before absorption from state i is the i-th row sum of N; and the probabilities of being absorbed into each absorbing state are given by N times R, where R is the transient-to-absorbing block.

Why the inverse? N = I + Q + Q^2 + Q^3 + ... is a geometric series of matrices counting visits at step 0, 1, 2, ... and it sums to (I - Q)^(-1) exactly because, the chain being transient, Q's powers shrink to zero. This single matrix turns hard questions — expected game length, the chance each contestant wins, expected time to extinction — into one matrix inversion. Absorbing-chain analysis is everywhere: gambler's ruin, branching-process extinction, drunkard's walk to a wall, and the 'how many turns will this take?' of countless games.