Motivation
Repeated random changes are easier to study when the present state captures the information needed for the next transition. This unit develops the resulting finite-state model and uses it to answer different questions about paths, first visits and long-run distributions.
Definitions
A state remembers what matters
A random walk records the successive positions of a particle whose next step is random. A finite Markov chain generalizes this idea: its state can represent any summary sufficient to determine the law of the next state. The state need not encode the entire history, but the model must justify discarding that history.
Definition 3.1.1
(Time-homogeneous Markov chain)
Let take values in a finite set . The process is a time-homogeneous Markov chain if, whenever the conditioning event has positive probability,
independently of . The transition matrix has nonnegative entries and every row sums to one.
We use row vectors: an initial distribution evolves as .
The Markov property is a conditional statement, not a claim that successive states are independent. Knowing the current state often changes the probabilities of the next state dramatically. Conversely, a process may fail to be Markov when an important hidden variable, such as a persistent machine mode, has been omitted from its state.
Proof sketch or proof idea
The path calculation below combines the multiplication rule with the Markov property; the hitting calculation then conditions on a first step. Neither method assumes that adjacent states are independent.
Paths and transition powers
For a particular path with initial probability , the multiplication rule and Markov property give
Summing over intermediate states gives the Chapman–Kolmogorov rule: the probability of reaching from in steps is . For two steps this is ; each term is the probability of a disjoint route through . Thus .
Worked example 3.1.2
(Two steps on three positions)
On states , suppose the particle moves from to and from to with probability one, while from it moves to either neighbor with probability . Starting at , it is back at after two steps with probability . Starting at , it is at after two steps with probability . Listing routes prevents the common error of multiplying probabilities for incompatible alternatives.
Hitting a boundary
Consider a walk on , where and are absorbing. From an interior state the walk moves right with probability and left with , independently at each step. Assume . Let be the probability of hitting before starting from .
Theorem 3.1.3
(Hitting probabilities between two absorbing ends)
For this walk with , absorption at or occurs with probability one. The probability of hitting before from is when , and
when .
Proof
(First-step equations and their unique solution)
Absorption: from an interior state , the next steps all to the right reach , so the walk is absorbed within steps with probability at least . Applying the Markov property at times , the probability of surviving beyond steps is at most , which tends to zero.
Equations: conditioning on the first step and using the Markov property at time one gives
Solution: since , the recurrence reads , so and . If this is , and forces , so . If it is , and forces , which gives the displayed formula. Every solution of the system has been forced into this form, so the system has exactly one solution, and the hitting probabilities are that solution.
Proof X-ray
Three jobs in one proof
The proof does three separate things. First-step conditioning produces the equations; it uses only the Markov property at time one and works on any state space. The key move is algebraic: read the recurrence as , which turns a second-order equation into a geometric progression with a single unknown . The second boundary value then fixes , and because when . The hypothesis is used twice: makes defined, and makes positive. Absorption is what makes the probability of hitting first, and the same geometric survival bound is reused below for expected durations. On an infinite state space there is no second boundary value, the recurrence leaves a one-parameter family of solutions, and an extra argument is needed to select the probability.
Worked example 3.1.4
(A biased walk)
Let , , , and start at . Here , so the chance of reaching first is . It exceeds the fair-walk value , but is still less than one because a first step left ends the experiment.
Stationarity and long-run behavior
Definition 3.1.5
(Stationary distribution)
A probability row vector is stationary if .
Starting with distribution gives the same marginal distribution at every time, by induction. This does not mean that individual paths are constant or that other initial distributions converge to .
Concept lensAlgebraic
A stationary distribution is a left eigenvector
The equation says that lies in the null space of : a stationary distribution is a left eigenvector of for the eigenvalue , scaled so that its entries are nonnegative and sum to one. A nonzero left eigenvector always exists, because every row of sums to one, so , , and is singular as well. The same view explains a practical step: summing all equations of gives the identity , so the equations are dependent and one of them may be replaced by . Linear algebra alone does not show that some eigenvector has nonnegative entries; for irreducible chains the next theorem supplies that.
Theorem 3.1.6
(Finite irreducible chains)
For a finite irreducible chain, there is a unique stationary distribution and all its entries are positive.
Irreducibility means every state can reach every other in some positive number of steps. If the chain is also aperiodic, for every initial distribution . These standard results are stated without proof here. Irreducibility is sufficient, not necessary, for uniqueness; aperiodicity is a further condition for the stated convergence.
Worked example 3.1.7
(Stationarity without convergence)
For the deterministic two-state alternating chain, has rows and . Its unique stationary distribution is , since the equation requires equal coordinates. Starting instead from state zero, the distribution alternates between and and never converges. The chain is irreducible but periodic with period two.
Expected absorption time
Probabilities of eventual outcomes do not say how long the walk takes. For the fair absorbing walk above, let be the expected number of steps until absorption starting at . Then and first-step analysis gives . The extra one counts the first step, including a step directly into a boundary.
Theorem 3.1.8
(Duration of a finite fair walk)
For the fair nearest-neighbor walk with absorbing endpoints , the expected absorption time from is .
Proof
(Finite expectation, then a unique solution)
To justify the recurrence, the absorption time must have finite expectation: the geometric survival bound in the previous proof gives . The recurrence is equivalent to . For the linear part has second difference zero and has second difference ; also . If two solutions existed, their difference would have zero second difference and zero values at both endpoints; it would be linear and hence identically zero. Thus is the unique solution.
Worked example 3.1.9
(Time from the middle)
With boundaries and , a fair walk started at has expected absorption time steps. Starting at gives five steps. These are averages, not deterministic stopping times; for example a walk from may hit in three consecutive right steps or wander for longer.
This calculation also shows why “equally likely to move in either direction” does not mean that the expected time to hit a boundary is one step. The state has to travel to an endpoint, and possible reversals extend the path. The finite boundary is essential to this particular formula.
The quadratic formula is replaced by one that combines the drift with the hitting probability.
A path to generalization
What changes for the duration of a biased walk?
The quadratic formula is replaced by one that combines the drift with the hitting probability.
For the same first-step equation , with , has the unique solution
Read as , it says that the expected displacement until absorption equals the mean step times the expected number of steps. As the formula tends to .
Common mistake
(A stationary equation is not a convergence proof)
Solving finds distributions preserved by the transition, but it does not by itself show that a chain approaches one. Check the communicating structure and periodicity before invoking the finite-chain convergence theorem.
Communication and closed classes
Definition 3.1.10
(Reachability and communication)
A state is reachable from if for some integer . Two states communicate when each is reachable from the other.
Communication partitions the state space into classes: reflexivity uses , symmetry is built into the definition, and transitivity follows by concatenating positive-probability paths. A class is closed if no one-step transition from it leads outside. Once a chain enters a closed class it cannot leave it.
This structure helps interpret stationary equations. In a finite chain with two distinct closed classes, each class supports a stationary distribution; different mixtures give different stationary distributions for the whole chain. Thus uniqueness cannot be assumed just because is a stochastic matrix. Conversely, irreducibility is not necessary for uniqueness. For example, state 0 may be absorbing while state 1 moves to 0 with probability one. The unique stationary distribution is concentrated at 0, although 0 cannot reach 1.
Worked example 3.1.11
(A reducible chain with two absorbing states)
On states , let both endpoints be absorbing and let state 1 move to either endpoint with probability . The vectors and are stationary, and every mixture with is stationary. Starting at 1 gives distribution after one step and thereafter. The limiting distribution depends on the start, so there is no single attracting distribution for all initial states.
For an irreducible finite chain, the period of a state is the greatest common divisor of its possible positive return times. All states share the same period. A self-loop of positive probability is a return in one step and therefore forces period one in an irreducible chain. Aperiodicity rules out the deterministic alternation seen above, but does not mean every state has a self-loop. Return paths of lengths two and three already have greatest common divisor one.
Deriving a stationary distribution from flow
The equation expresses balance: for each state, its probability at the next step is the sum of the probability flows into it. It is not necessary for every individual pair of states to exchange equal flows. Nevertheless, a stronger pairwise condition, called detailed balance, is often convenient.
Theorem 3.1.12
(Detailed balance implies stationarity)
If a probability vector satisfies
then .
Proof
(Sum the pairwise equations)
Fix and sum the hypothesis over : , because row sums to one. The left side is the -th entry of .
Counterexample mode
A stationary chain without detailed balance
Claim: every stationary distribution satisfies detailed balance. On states let the chain move deterministically , so and all other entries are zero. Each column of contains exactly one entry , so satisfies . Yet while . The claim fails: balance of total inflow at each state is weaker than balance across each pair, and the theorem gives a sufficient condition only.
Worked example 3.1.13
(Balance in a two-state model)
Take the transition matrix with rows and . Pairwise balance requires , hence . Together with this gives . Both off-diagonal flows equal . The diagonal balance equations hold automatically; substituting the result into independently checks the answer.
First-step analysis as a boundary-value method
The recurrence for hitting probability is not special to a line. If is a target set and a disjoint failure set in a finite chain, define as the probability of reaching before . Set on and on . At a state outside both sets, the first-step rule gives . When the chain reaches almost surely from every remaining state, these equations have a unique solution. If another solution differs by , repeated substitution expresses as the expected value of at time before reaching the boundary. Since is bounded on the finite state space and the probability of still avoiding the boundary tends to zero, this expectation tends to zero; hence .
The almost-sure boundary condition matters. If an outside state is absorbing, the equation there is merely and does not determine its value. The probability of reaching the target before failure is still a well-defined event, but boundary equations alone need further information. Checking reachability and termination is therefore part of setting up the calculation, not an optional algebraic detail.
State choice and prediction
A transition matrix is useful only after the state has been specified. Suppose a device has an unobserved mode that persists for several steps, and its chance of producing a warning depends on that mode. The warning alone need not be Markov: earlier warnings can give information about the current mode, and hence change the predicted next warning even after the current warning is known. Enlarging the state to include the mode may restore the Markov property if the model's transitions actually depend only on that enlarged state.
Even a correct transition matrix does not specify a complete process without an initial distribution. The same matrix can produce different finite-time distributions from different starts, as makes explicit. A stationary initial distribution is one possible choice, not a default assumption. Before computing a matrix power, record the state ordering and whether distributions are rows or columns; reversing those conventions changes the multiplication order.
Common mistake
(Multiplying the distribution on the wrong side)
With row-vector distributions the update is . Computing instead combines the entries of a column of . For rows and and , the correct result is , whereas , whose entries sum to ; it is not a distribution. Checking that the entries sum to one catches the error at once.
Summary
A transition matrix determines finite-time distributions by matrix powers. First-step equations answer boundary questions. A stationary distribution is preserved by the chain, while convergence from every initial distribution additionally requires appropriate hypotheses such as finite irreducibility and aperiodicity.
Exercises
Quick check
(A fair walk with absorbing endpoints and starts at . Find the chance of hitting before .)
Solution · Answer
The fair formula gives .
Quick check
(A chain has transition rows and . Find its stationary distribution.)
Solution · Answer
Write . The first coordinate of gives , hence , and .
Quick check
(For the chain in the previous question, starting in state , find the probability of being in state after two transitions.)
Solution · Answer
Sum the two routes and : .