An absorbing state is one the chain cannot leave, and that is a property of the matrix rather than a label put on it. Split the matrix into transient and absorbing blocks and two questions have one answer: how long until the chain stops, and which exit it takes. The answer runs through N = (I − Q)⁻¹, which is usually introduced as an inverse and then used as a count. It is the sum of the powers of Q, and the lab shows the partial sums climbing towards it entry by entry, because Qᵏ[i][j] is the chance of being at j after exactly k steps and adding those over k counts visits.
Core ideas
Three ideas. The first is a property of the matrix, the second is the identity that makes the inverse mean something, and the third is what the two block products say.
State i is absorbing when P[i][i] = 1, which forces every other entry of that row to zero. The lab checks this against the matrix you typed and refuses a state you have merely declared absorbing: listing one whose diagonal entry is 3/4 is a modelling error, and calling it a boundary condition would produce numbers for a chain that does not stop there.
Qᵏ[i][j] is the probability of being at transient state j after exactly k steps having started at i. Add over all k and you have counted the expected number of visits to j, which is what N[i][j] means. That the sum equals (I − Q)⁻¹ is the geometric series argument with matrices, and the slider on this page is the reason rather than the illustration: move it and the partial sums close on N while the page prints what is still missing.
t = N·1 adds the expected visits across a row: the total number of steps before absorption. B = N·R multiplies the expected visits by the one-step chance of exiting to each absorbing state: the probability of finishing there. Every row of B sums to one and the page checks it, which is the statement that the chain is absorbed with probability one rather than an assumption that it is.
The material
The canonical form, the series that N really is, the two products, and the case where I − Q has no inverse because the chain never stops.
State i is absorbing when P[i][i] = 1. Order the states with the transient ones first and the matrix splits into Q (transient to transient), R (transient to absorbing), a zero block and an identity block.
The fundamental matrix is N = (I − Q)⁻¹, when the inverse exists. t = N·1 is the vector of expected numbers of steps before absorption, and B = N·R is the matrix of probabilities of finishing in each absorbing state.
The lab extracts those blocks from the matrix you typed, given the positions of the absorbing states, and computes N by exact Gauss-Jordan on [I − Q | I] over the rationals. So the inverse of a matrix of halves and thirds is a matrix of halves and thirds, and the expected times come out as fractions you can check by hand.
If (I − Q) is invertible and Qᵏ → 0 then I + Q + Q² + ⋯ = (I − Q)⁻¹, and the (i, j) entry of that sum is the expected number of visits to transient state j starting from transient state i, counting the start.
Let Sₖ = I + Q + ⋯ + Qᵏ. Then (I − Q)Sₖ = I − Q^(k+1), because everything in between cancels — the same telescoping as the scalar geometric series, and matrix multiplication is all that was used.
As k grows, Q^(k+1) → 0 whenever every transient state can reach an absorbing one, so (I − Q)Sₖ → I and Sₖ → (I − Q)⁻¹. For the interpretation, note that the expected number of visits to j is the sum over k of the probability of being at j at step k, which is Σₖ Qᵏ[i][j] — the same sum, entry by entry.
□
That is why the slider matters. What is left over from the partial sum after k steps is exactly the probability mass still sitting in transient states after k steps, and the page prints it beside every entry. On the gambler's-ruin example the worst shortfall is 1 at k = 0, 1/2 at k = 2, 1/8 at k = 6, 1/32 at k = 10 and 1/1024 at k = 20: halving every two steps, which is the chain's own structure showing up in the remainder.
The diagonal of N is worth a second look. N[2][2] = 2 says the walk started at 2 is at 2 twice on average, counting the start; N[1][1] = 3/2 says the walk started at 1 is at 1 one and a half times. Those are counts of visits, and they are what makes the row sums 3, 4, 3 mean “total steps” rather than anything more mysterious.
Change the step probabilities to two-thirds up and one-third down. The expected times become (17/5, 18/5, 11/5) and the absorption probabilities (7/15, 8/15), (1/5, 4/5), (1/15, 14/15).
From the top transient state the walk now finishes at the far end fourteen times in fifteen, and the expected wait from there has dropped from 3 to 11/5. Notice that the middle row is no longer even and that the longest wait is still from the middle, but by a narrower margin: the drift shortens every journey and skews every destination, and both effects come out of the same N.
I − Q is singular exactly when some transient state cannot reach an absorbing one — there is a closed set of states you have not declared absorbing, the chain can enter it and never leave, and there is no expected number of steps to absorption because absorption does not happen. The lab reports this rather than producing a number, and the diagnosis it gives is the actionable one: every state you have not listed as absorbing has to be able to reach one that you have.
Take 1 0 0; 0 1/2 1/2; 0 1/2 1/2 and declare the first state absorbing. States two and three communicate with each other and with nothing else.
I − Q is singular, and the lab says so. The right reading is not “the arithmetic failed” but “the model has a second closed class in it”, which the material on communicating classes finds directly and which is very often an unintended consequence of a transition that was left out.
Interactive
the fundamental matrix as a sum of powers rather than as an inverse to memorise
Method
Four steps, and the first is a check on the matrix rather than on your arithmetic.
P[i][i] = 1 and the rest of the row zero. A state you intend to be an exit but which still has an arc out of it is not one, and every figure below would be answering a question about a different chain.
Otherwise I − Q is singular and there is no expected absorption time, because there is a set of states the chain can enter and never leave. This is a reachability question and it is answered from the arcs.
Q is the transient block, R the transient-to-absorbing block. Elimination on [I − Q | I] over the rationals gives N exactly. On small chains this is faster by hand than it looks, and the entries are checkable.
t = N·1 for the times, B = N·R for the destinations. Every row of B must sum to 1; if one does not, either the arithmetic slipped or the chain escapes absorption, and the two are worth telling apart before you report anything.
The even-money walk first, then the biased one, on the same state space with the same exits. Everything is exact and every row of B is added up.
The even-money t = (3, 4, 3) matches the closed form i(n − i) for a symmetric walk absorbed at 0 and n: 1·3, 2·2, 3·1. That is a useful coincidence to have met, because it means this instance has an independent answer and the fundamental matrix is being checked against something rather than being taken on trust.
The partial-sum block is the argument. At k = 6 the entry 23/16 is short of 3/2 = 24/16 by exactly 1/16, and the shortfall is halving every couple of steps. That remainder is the probability mass still in transient states after six steps — not an error term, not a truncation artefact, but the thing the series has not yet counted.
For a rehearsal, take the biased walk and predict B[3][2] before computing it. The supplied first move is that from state 3 the walk reaches 4 in one step with probability 2/3, so the answer is at least 2/3. Work out how much the remaining 1/3 contributes, and check against 14/15.
You should be able to identify absorbing states from the matrix, split it into Q and R, argue that I + Q + Q² + ⋯ telescopes to (I − Q)⁻¹, read expected times off the row sums and destinations off N·R, check the rows of B, and recognise a singular I − Q as a second closed class rather than as a numerical problem.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.