Motivation
A finite Markov model may finish in several different ways. A task can terminate successfully, fail permanently, or enter a closed group of modes that keep switching forever. The first two outcomes are absorbing states; the third is an absorbing destination class but not an individual absorbing state. A computation that collapses these distinctions too early can report the wrong probabilities.
The right order is structural before algebraic. First identify the communicating classes and determine which are closed. Then separate the states that can still leave from the destinations they eventually reach. The resulting block matrix turns occupation counts, completion times and destination probabilities into different calculations using one common inverse.
We assume finite stochastic matrices, conditional probability and the hitting-time Markov property proved in earlier notes. The proofs below establish why the inverse exists and what its entries mean; no numerical matrix inverse is used as a substitute for those arguments.
Definitions
Definition 2.7.1
(Communicating classes and the block form)
A state reaches another if some finite-step transition probability is positive. Mutual reachability partitions a finite state space into communicating classes. A class is closed if no transition leaves it. Write the closed irreducible classes as and their union as . Let contain all remaining states. Reorder the states so that
Here describes transitions within , enters individual states of , and is the stochastic transition matrix within class . If every closed class is a single absorbing state, . For genuinely switching destination classes, it is generally not the identity.
Definition 2.7.2
(Exit time and class indicator)
Let . Starting in , the count includes every transient visit at times and excludes the entrance visit at time . Define when closed state belongs to , and zero otherwise. Thus gives one-step probabilities of entering destination classes, whereas retains the exact entrance state. Empty is a trivial already-closed case; the inverse calculations below concern nonempty .
Theorem/proposition
Theorem 2.7.3
(Exit occurs with a geometric block bound)
Every state in eventually reaches almost surely, with finite moments of . More precisely there are finite and such that
Consequently and
exists as a finite matrix with nonnegative entries.
Theorem 2.7.4
(Occupation, destinations and duration)
For , the fundamental matrix satisfies
The exact entrance-state matrix is , and the destination-class matrix is . Both have probability rows summing to one. Mean and second-moment columns of are
A transient-state cost column , paid on each transient visit, and a terminal class reward column give expected total .
Concept lensAnalytic
Destination probabilities as a boundary-value problem
Fix a class and put for and for . First-step conditioning makes harmonic at every transient state, , with boundary values one on and zero on the other closed classes. On this reads , where is the th unit column, and invertibility of makes the only solution. Destination probabilities are thus the unique harmonic extension of boundary data; mean durations solve the same problem with a source term, , and zero boundary values.
Proof sketch or proof idea
Find the eventual destination before taking an inverse
Proof
(A uniform exit path from the class graph)
The directed graph of communicating classes has no directed cycles among distinct classes: a cycle would make them mutually reachable, so they would be one class. A finite directed acyclic graph has a terminal vertex reachable from each vertex. Terminal classes are precisely the closed ones. Therefore every transient candidate has a finite positive-probability path to .
Choose one such path from each state of . Finiteness supplies a common length upper bound and a common positive lower bound on their probabilities. Conditional on any history still outside , the next steps reach with probability at least . Repeated conditioning proves the block tail. This also proves that states of are transient: expected total time outside is finite, so each individual state's expected visit count is finite. They were not declared transient just because they were not absorbing.
The row sum of is the probability of remaining outside through time . Thus the tail bound gives convergence of the matrix series. Multiplying its finite partial sums by telescopes to ; the remainder tends to zero. This proves both left and right inverse identities, without assuming a spectral calculation. The same geometric bound gives an exponential moment of in a neighborhood of zero and hence all its ordinary moments.
Proof X-ray
Why finiteness gives a geometric exit
Finiteness is used twice. It makes the class graph a finite acyclic graph, so every class has a path to a terminal, that is closed, class; and it lets one length and one probability serve every starting state in . The key move is to apply the path bound afresh after each block of steps: conditional on any history still outside , the chain is at some state of , from which the chosen path succeeds with probability at least . Multiplying these conditional failure bounds gives . The argument closes algebraically, not spectrally: the row sums of are survival probabilities, so the geometric tail makes converge, and the telescoping identity identifies the sum as .
Without finiteness the uniform constants can fail. On , let state enter with probability and otherwise move to . Every state has a one-step path to , yet from state the chain stays in forever with probability .
Interpret the inverse and its products
Proof
(Reading the inverse as counts, entrances and durations)
For , is the probability of being at at time without having entered . There is no possibility of returning from , because it is closed. Summing these nonnegative indicators and using Tonelli gives the occupation interpretation of .
An entrance into closed state on step has probability . These entrance events are disjoint over times and exhaust all paths up to a null set. Summing gives . Grouping entrance states by class gives . There is also a useful algebraic check: , so . Nonnegativity and the row sum verify genuine probability rows, not merely a solution to a linear system.
At a transient starting state one step always elapses before either another transient state or the destination is reached. First-step conditioning yields . On a transient continuation, squaring one plus the remaining time yields . Multiplying by gives the displayed formulas, using . Finiteness was established beforehand, so the second-moment equations are legitimate. For costs and terminal rewards, the analogous equation is , whose solution is . No independence of successive visits is assumed.
Entrance is not equilibrium within a destination
For clarity, the full finite-time matrix has the block form
Each summand chooses the time of first entrance and then evolves within the closed class. This identity follows by induction or by disjoint path decomposition. In contrast, records where the chain first enters; it is not generally the final state's limiting law.
If each closed irreducible class is aperiodic, its previously proved finite-chain convergence theorem applies inside the class. Conditional on a finite entrance time and entrance state, the future law converges to that class's stationary law. Bound the late-entrance tail by , first let time increase for finitely many entrance times through , then let increase. This proves the limiting mixture with class weights . If a destination class is periodic, the entrance calculation remains correct, but ordinary convergence requires a separate examination; it is not a consequence of .
Deadlines and conditioning on a destination
A deadline retains the difference between finished and unfinished paths. The matrix of class probabilities reached by step is
Thus : survive outside the destinations for steps, then eventually enter the indicated class. Summing this remainder over classes gives , the unfinished probability. This identity is a useful way to check a finite-deadline calculation without simulating paths. Dividing the finished probabilities by their row sum would instead condition on having finished by the deadline, a different question.
The time and destination can also be retained together. First-step conditioning gives the matrix generating function
The geometric exit bound justifies differentiating near one. Its derivative at one is , since differentiating the inverse gives and . Whenever , the mean duration conditional on that destination is therefore . A zero-probability destination does not define such a conditional mean. The derivative is a joint quantity of time and destination, not a conditional generating function; conditioning requires a further division by the positive destination probability. This formula also shows why a rare destination may take a different average time from a common one; the unconditional time does not settle the conditional question.
For the first example below, the conditional means from are three steps given destination and four given . Their probability-weighted average is , agreeing with the unconditional mean. Conditioning here changes the path distribution; it does not change the original transition matrix or justify using its ordinary mean formula without the destination weights.
Worked examples
Worked example 2.7.5
(A complete two-transient, two-destination calculation)
Order states as , with absorbing, and take
Rows of sum to one. Each destination is a singleton, so and the class matrix here is . The inverse and entrance probabilities are
Starting at , the chain visits an expected times before completion and ends at with probability . The mean duration column is . Multiplying again gives , so variances are and . Check that , every destination row sums to one, and the means solve . These checks test different claims rather than repeating a single arithmetic step.
The explorer below computes N = (I − Q)⁻¹, B = NR, the mean and variance of the duration exactly for the worked example, gambler's ruin and a chain with a closed class mislabeled as transient, and checks each against a separate identity.
Worked example 2.7.6
(A closed class can keep moving)
Let transient state stay at itself with probability , enter state with probability , and enter absorbing state with probability . Within the other closed class, and alternate deterministically. Then , the exact entrance probabilities to are , and the two destination-class probabilities are . Mean entrance time is two. Once the chain enters , it does not remain there; from initial state its law alternates forever. The destination-class calculation never promised an absorbing state at or ordinary convergence inside its class.
Worked example 2.7.7
(A proposed transient block containing a trap)
Suppose a state stays at itself with probability and otherwise enters absorbing , while state stays at itself forever. If both are incorrectly placed in the transient block, and is singular. Starting at , the proposed completion time is infinite. The repair is structural: is another closed destination class. With only transient, is valid and the destination probability of reaching from is one. An arbitrary collection of non-designated states is not automatically a transient set.
Common mistakes
Common mistake
(Dropping the initial transient visit)
The fundamental matrix counts the initial transient visit. Omitting that visit changes to and corrupts mean-time and cost calculations. The terminal visit, however, belongs to the destination and is excluded from transient occupation. State ordering and the row-distribution convention determine which side the matrices multiply on.
Common mistake
(Inverting before classifying)
Inverting before checking the communicating structure reverses the correct order. A numerical solver may flag singularity, but the meaningful explanation is a retained closed class.
Common mistake
(Renormalizing probabilities at a deadline)
Destination probabilities describe what happens eventually; they are distinct from probabilities by a finite deadline. The latter use finite sums of and retain the unfinished probability mass. Dividing the finished probabilities by their row sum answers a different question: what happens given completion by the deadline.
Summary
The finite class graph identifies eventual destinations and supplies a uniform geometric exit bound. Its convergent transient powers produce the fundamental matrix. Occupation, durations, costs and multiple-destination entrances then follow from separate interpretations of its matrix products. Closed-class motion remains a separate part of the model.
Exercises
Quick check
(A single transient state stays with probability , exits to with probability and to with probability . Find , destination probabilities, mean and variance of exit time.)
With one transient state, is a scalar.
Solution · Answer
. Multiplication by the two exit probabilities gives . The mean is and the second moment is , so the variance is .
Quick check
(In the first worked example, charge costs per visit to and terminal extra costs at . Find the expected total from both starts.)
Use with the matrices of the first example.
Solution · Answer
Transient costs are . Terminal costs are , so totals are . The transient cost is charged before each transition, while the terminal cost is charged only once after entrance.
Quick check
(In the second worked example, distinguish the exact entrance distribution, destination-class distribution and the one-time law from initial state . Which one fails to converge?)
Separate where the chain enters from how it moves afterwards.
Solution
From , exact entrance into is ; class entrance into is . From , the one-time state distribution alternates between point masses at and and has no limit. Neither entrance probability is a claim about that time evolution.
Quick check
(Prove for transient . Use it to find the chance of visiting from before completion in the first example.)
Apply the hitting-time Markov property at the first visit to .
Solution
If is never hit, its occupation count is zero. On first hitting , the hitting-time Markov property makes expected subsequent occupation, including that first visit, equal to . Thus . Here , so division is valid. The requested probability is .