Try
A synthetic review process has two continuing states, A and B, and two terminal labels, C and D. Start at A. Each row below gives the next-state probabilities. A terminal label is absorbing: once reached, the process stays there.
| From / to | A | B | C | D |
|---|
| A | 0 | 1/2 | 1/4 | 1/4 |
| B | 1/3 | 0 | 1/2 | 1/6 |
| C | 0 | 0 | 1 | 0 |
| D | 0 | 0 | 0 | 1 |
Draw the paths of at most two transitions starting at A. Keep A→B→A in the drawing: it is unresolved, not a failed D outcome. Each next transition is sampled from the current row conditional on the complete past. This is the Markov assumption; successive states themselves need not be independent.
Predict
Predict whether the route always stops eventually and whether its mean number of steps is finite. It can revisit A, so “there are only four states” is not a proof. Before solving any mean-time equation, identify a bound on the probability of staying in A or B for one more step.
The directed-walk transition lesson supplies row conventions and weighted paths. The restart lesson explains why a finite cap and eventual termination are different questions.
Experiment
From A the next state is continuing with probability 1/2; from B it is continuing with probability 1/3. Therefore, conditional on still running, the chance of surviving one more step is at most 1/2. Repeating this argument gives P(T > n) ≤ (1/2)ⁿ, where T is the number of transitions before first entering C or D. The probability of never stopping is zero, and the nonnegative survival sum gives E(T) ≤ 2.
Let h_A and h_B be the eventual probabilities of D from each continuing state. Conditioning on the first transition gives
Substitute the second equation into the first: h_A = 1/3 + h_A/6. Hence h_A = 2/5 and h_B = 3/10. Check these values in both original equations.
For expected steps, let t_A and t_B count the terminal transition too. The equations are t_A = 1 + t_B/2 and t_B = 1 + t_A/3. They give t_A = 9/5 and t_B = 8/5. These numbers measure transitions, not minutes. The earlier tail argument justified that finite means exist before we canceled terms in the equations.
Understand
From a finite table to a general certificate
Keep only the continuing-state probabilities in the matrix Q. For the worked table, Q has rows (0,1/2) and (1/3,0). The missing row mass exits to C or D; a matrix with row sums at most one is called substochastic. The column r_D = (1/4,1/6) records direct transitions to D.
Suppose more generally every row sum of a finite nonnegative Q is at most q, with q strictly less than one. Let 1 denote the column whose entries are all one. Induction gives Qⁿ1 ≤ qⁿ1 coordinate by coordinate. Starting at state i, the i-th entry of Qⁿ1 is the probability of surviving n transitions.
The entrywise series H = I + Q + Q² + ⋯ converges by comparison with a geometric series. For a finite partial sum, multiplication on either side by I − Q gives I − Qⁿ⁺¹. The remainder tends to zero. Therefore H is the inverse of I − Q. This proves inverse existence under the stated hypothesis; an inverse symbol alone would not prove it.
The vectors of eventual D probabilities and expected steps are
For h, the term Qᵏr_D is the probability of first reaching D on transition k + 1; these events are disjoint. For t, the term Qᵏ1 gives the survival probabilities in the expectation tail sum. The inverse also proves uniqueness of the corresponding first-step equations.
A cap leaves probability mass to account for
Starting at A in the worked chain, the two-step ledger is:
| By two transitions | Exact probability |
|---|
| Reached D | 1/4 + (1/2)(1/6) = 1/3 |
| Reached C | 1/4 + (1/2)(1/2) = 1/2 |
| Still at A | (1/2)(1/3) = 1/6 |
The probabilities sum to one. The capped mean is E[min(T,2)] = 1 + 1/2 = 3/2. The remaining mean is (1/6)t_A = 3/10, giving total 9/5. Reporting only paths that have ended loses the distinction between the capped and eventual quantities.
With a general cap m, define h_m and t_m by keeping terms k = 0 through m − 1 in the two series. Then
The first bound is omitted probability; the second is omitted expected transitions. These are analytic truncation bounds. They do not cover Monte Carlo error, a false real-world model or unbounded floating-point roundoff. Exact rational checks or a justified rounding enclosure are needed before calling a displayed decimal a numerical certificate.
A counterexample outside the theorem
Change A to move to B or C with equal probability, and make B stay at B forever. Starting at A, half the paths reach C immediately and half never reach either terminal label. D is unreachable; the expected absorption time is infinite. The continuing matrix has a row sum of one and I − Q is singular. A 64-step cap cannot repair that mathematical fact.
Conversely, the one-step exit bound is sufficient, not necessary. If every continuing state has a path of at most d steps to an exit, with probability at least ε > 0, then P(T > kd) ≤ (1 − ε)ᵏ and E(T) ≤ d/ε. A state may have zero immediate exit probability and still satisfy this block argument. The finite state space and explicit path probabilities matter; the lesson does not claim every countable chain with almost-sure absorption has finite mean time.
Apply
Write two independent checks of the worked answer: substitute h and t into the first-step equations, then enumerate the two-step path ledger and verify its unresolved mass. Explain what evidence you would need before treating the synthetic rows as observations of a real review process.
MIT’s Spring 2006 absorption recitation supplies a dated primary teaching reference for first-step absorption calculations. Our route, proof of the row-bound certificate and counterexamples are original. The broader Fall 2019 Markov-chain source remains a comparison baseline, not a claim of full source-course equivalence.
Continue
Continue to censored simulation and dependence to compare generated records with these calculations while retaining incomplete paths. Return to moments and tail sums if the expectation argument needs a refresher.
