◄ WORLD V · SONNY 5DART 202 · a helldive at the net

THE ABSORBING CHAIN the fundamental matrix: how long till you're trapped

Some chains have states you can never leave — absorbing states. Split P into a transient block Q and an absorbing block R. The fundamental matrix N = (I − Q)⁻¹ answers everything: Nᵢ⫺ is the expected visits to transient j starting from i, its row sums give the expected steps to absorption, and NR gives the probability of ending in each absorbing state. Gambler's ruin lives here.

THE TECHNIQUE N = (I − Q)⁻¹ : expected visits, steps, and where you end

Play gambler's ruin on {0..4} with absorbing ends and an adjustable bias — solve (not simulate) the expected steps to absorption and the probability of winning versus going broke: live demo







  
HISTORY & CREDIT Kemeny & Snell, 1960

  
“You have to simulate the walk to know how long it lasts on average.” — no; the answer is a linear solve. Expected steps to absorption satisfy (I − Q)t = 1, and the win-probabilities satisfy (I − Q)a = R — one Gaussian elimination, no dice thrown. cited

  
1656–57 · Pascal & Fermat then Huygens — the gambler's-ruin problem: two players, a fair or biased bet, who is broke first? (Their 1654 letters settled the separate problem of points; ruin came in 1656, published by Huygens 1657.)
1711 · de Moivre — the closed form for biased ruin, (1−rᵢ)/(1−rⁿ).
1960 · Kemeny & Snell, Finite Markov Chains — the fundamental matrix N=(I−Q)⁻¹ makes every absorption question one inverse.

  
Absorption is where randomness ends in certainty: eventually you are trapped, and the only questions are when and which — both answered without ever rolling a die. Kemeny–Snell 1960






  
RECOMMEND FOR I-13 expected steps and win-probability, computed

  
On the canonical compiler, biased gambler's ruin on {0..4} (up-probability 0.6) gives, from the middle, both the expected steps and the exact win-probability 9/13 by relaxation — matching de Moivre's formula:

  
$ i13 run absorb.i13   # ruin{0}/win{4}, up=0.6 from state 2
expected steps to absorption (symmetric): e = [3, 4, 3]
P(reach 4 before 0) from 1 = 0.4153846...
P(reach 4 before 0) from 2 = 0.6923076923076922   -- exactly 9/13
P(reach 4 before 0) from 3 = 0.8769230...

  
Recommend: the absorbing chain is LIT for I-13 — verified expected steps to absorption [3,4,3] for the symmetric walk and win-probability 9/13 = 0.69231 from the middle under a 0.6 up-bias, both by iterating the linear system, both matching the closed form. When and where you get trapped, computed with no randomness at all.