Motivation
A Markov chain records a state that changes one step at a time. The state might be the number of tasks remaining in a short queue, a location in a graph, or the mode of a finite-state controller. The useful feature is a conditional independence statement: once the present state is known, the recorded past supplies no further information about the next state. This requires choosing a sufficiently informative state. A controller with a hidden timer may cease to be Markov if we record only its visible mode and omit that timer.
Two long-run questions deserve separate names. Will the chain return to a state it has left? If it does return, how long is the average wait? A further question asks whether there is a probability distribution preserved by one transition. Recurrence, positive recurrence and stationarity connect these questions, but they are not interchangeable. Even a finite chain can have a stationary distribution while its distributions from a fixed starting state oscillate forever.
This unit begins with transition matrices and first-step conditioning. It then develops return probabilities and finite-state equilibrium, with a countable-state warning that explains why finiteness matters. Row vectors represent distributions throughout.
Definitions
Definition 2.1.1
(Time-homogeneous Markov chain)
On a finite or countable state space , a process is a time-homogeneous Markov chain with transition matrix if
for every conditioning history with positive probability. Each and . Its -step transition matrix is , so an initial distribution evolves to .
The matrix power follows by conditioning on the intermediate state: . On a countable space all terms are nonnegative, so these sums need no conditional cancellation. Any stochastic matrix and initial distribution specify a chain by successively sampling its next state, or equivalently by the consistent finite-history probabilities .
Definition 2.1.2
(Hitting, return and communication)
For , let . For a single state , define the first return and set the infimum of an empty set to . State is recurrent when , and transient otherwise. A recurrent state is positive recurrent if ; otherwise it is null recurrent.
State is accessible from if for some . States communicate if each is accessible from the other. A chain is irreducible when all states communicate. A communicating class is closed if it cannot be left in one transition. For a state that has a positive probability of returning at some time, the period of is the greatest common divisor of . No period is assigned here if this return-time set is empty. In an irreducible chain with possible returns all states have the same period; period one is called aperiodicity.
Definition 2.1.3
(Stationary distribution)
A probability row vector is stationary when . Starting with then gives the same one-time law at every step. A limiting distribution from state means convergence of for every to a specified probability vector; its existence requires a further argument.
Theorem/proposition
Theorem 2.1.4
(Recurrence through expected visits)
For a state , let . Then
Thus recurrence is equivalent to divergence of the return-probability series, not to divergence of the mean return time.
Theorem 2.1.5
(Finite irreducible equilibrium and convergence)
A finite irreducible chain has a unique stationary probability vector , every , and all states are positive recurrent with . If the chain is also aperiodic, then for every . Without aperiodicity, the averaged transition probabilities still satisfy
Irreducibility is sufficient for uniqueness here, not necessary: a reducible chain can have exactly one closed irreducible class and a unique stationary distribution concentrated there. In a countably infinite irreducible chain, a stationary probability distribution exists exactly when the chain is positive recurrent. Recurrence alone is insufficient. We explain the finite theorem below; the countable extension requires the corresponding integrability argument and is not proved in full here.
Concept lensStructural
Stationarity as balance across every cut
For a probability vector , the equations are equivalent to balance of probability flow across every cut: for every ,
Summing over and canceling the flow that stays inside gives this identity; taking recovers the th equation. Choosing cuts well shortens calculations: for a chain moving only between neighboring integers, the cut between and the rest gives directly.
Proof sketch or proof idea
Both theorems rest on one device: a visit to a fixed state restarts the chain, so the path splits into independent excursions.
Proof
(Counting visits by restarting at returns)
Each return to restarts the chain from . The Markov property at a hitting time follows by splitting on the events that this time equals each integer and applying the ordinary Markov property there. Consequently the probability of at least visits to , including time zero, is . Summing these tails gives , which is when and when . On the other hand, monotone convergence permits interchanging the nonnegative visit sum and expectation, giving the return-probability series in the first theorem.
Proof
(Return cycles, a maximum principle and a contraction)
Positive recurrence. For finite irreducible chains, fix a target state . From every state there is a path to with positive probability. Finitely many states allow a common bound on the chosen path lengths and a positive lower bound on their probabilities. Conditional on not yet reaching , the chance of reaching it within the next steps is at least . Hence the hitting-time tail is bounded by a geometric sequence in blocks of length . The same argument after the first step makes finite. Finiteness is used precisely when taking a common positive lower bound.
Existence. Between consecutive visits to , count the expected visits to each state , and divide those numbers by . The resulting vector is a probability distribution. Counting transitions within a return cycle shows that expected arrivals at each state equal expected departures: the cycle's initial and final states are both . Therefore . There is exactly one visit to before the terminal return, so .
Uniqueness and positivity. If , a state where attains its maximum can transition only to states with the same maximum. Irreducibility propagates this value to every state, so the right nullspace of consists only of constants. Finite-dimensional rank equality gives a one-dimensional left nullspace, and normalization determines the stationary vector uniquely. Its entries are positive because a positive entry can reach every other state along a positive-probability path. Repeating the cycle construction from any other state gives a stationary vector with -th entry ; by uniqueness it is , so for every .
Convergence. In a finite irreducible aperiodic chain, some power has every entry positive. This follows by concatenating return paths: their lengths have greatest common divisor one, so sufficiently large lengths can be formed, then joined to paths between states. Put and let . Each row contains a common mass times the uniform distribution. Removing that common mass shows that multiplication by contracts differences of probability distributions in total variation by at most . Repetition gives convergence to ; intervening powers preserve the bound. In the periodic case, the finite stochastic matrix has bounded powers; its Cesàro averages eliminate eigenvalues on the unit circle other than , while the simple eigenvalue supplies the same stationary limit. This proves the averaged assertion without claiming ordinary convergence.
Proof X-ray
Where finiteness, irreducibility and aperiodicity enter
The equilibrium proof has four parts, and each hypothesis is used at an identifiable step.
- Finiteness is used for the common bounds and , which give . Without it, every state may still reach , yet the waiting time can have infinite mean, as the symmetric walk in the common mistakes shows. It is used again for rank equality and for with finite.
- Irreducibility is used three times: to reach from every state, to spread the maximum of a harmonic , and to make every entry of positive.
- Aperiodicity is used only in the last part, to find a strictly positive power . Without it only the Cesàro statement survives.
The key move is the cycle construction. A cycle from back to begins and ends at the same state, so expected arrivals at each state balance expected departures, and follows by counting rather than by solving equations. Dividing by requires , which is why positive recurrence is proved first. The argument closes with uniqueness: building the cycle vector from every state yields the same , which is what turns for one state into for all.
Why hitting probabilities select the smallest solution
First-step equations can be constructed without assuming eventual hitting, and the construction itself identifies which solution is the hitting probability.
Proposition 2.1.6
(Hitting probabilities are minimal solutions)
Let and . Then for and for . If satisfies the same equations, then for every .
Proof
(Finite horizons increase to the hitting probability)
Let be the probability of reaching by time , including time zero. Set . At states in the value remains one; outside , the next update is
The events increase with the horizon, so these values increase to the eventual hitting probability. Taking the limit in the nonnegative sum proves its harmonic equation. If is any other nonnegative solution with boundary value one, induction gives at every horizon, hence . This proves minimality, rather than treating it as an arbitrary rule imposed on an algebraic system.
Minimality is not a technicality: on an infinite space the equations alone can have many solutions.
Counterexample mode
Boundary values alone do not determine hitting probabilities
Claim: the hitting probability is the unique solution of the first-step equations with value one on and values in . Consider the deterministic chain on nonnegative integers that moves from to , and take . Starting from a positive integer, zero is never reached, so the hitting probability there is zero. Yet for every constant , the sequence with and for satisfies for , which is the first-step equation. So the bounded system has infinitely many solutions. The repaired statement is the proposition: the hitting probability is the minimal nonnegative solution, here , and the finite-horizon construction selects it.
Expected hitting times have a related safe construction: sum the finite-horizon survival probabilities. This yields , allowing the value infinity. Therefore an algebraic candidate for a mean should be checked against a tail estimate or another finiteness argument. This is especially important when leaving finite-state examples for an infinite state space, where a path to the target from every state supplies no uniform bound on the waiting time.
Worked examples
Worked example 2.1.7
(Two modes with a genuine limiting law)
Take
Stationarity gives , so . Both states communicate and each has a self-loop, hence the chain is aperiodic. If , then , whence . This explicitly proves convergence from every starting law. The mean return time to state is steps; a mean below two is possible because an immediate self-loop counts as a return.
Worked example 2.1.8
(Stationarity without convergence)
The deterministic alternating chain has and stationary distribution . Starting at state , the probability of state is at even times and at odd times. Its period is , and no ordinary limit exists. The time-averaged probability tends to . Starting in the stationary law gives marginal probability at every time, although successive states are maximally dependent.
Worked example 2.1.9
(First-step equations and a unique reducible equilibrium)
On take absorbing, and from or move to with probability and to the other nonzero state with probability . For , first-step conditioning gives
so . The tail is for , independently verifying finiteness. Stationarity at nonzero states gives and , forcing both to zero. Thus is the unique stationary distribution even though the chain is reducible. The nonzero states are transient; the absorbing state is positive recurrent with return time one.
Common mistakes
Common mistake
(Treating a mean equation as proof that the mean is finite)
Writing outside does not establish that is finite: if the mean is infinite, the equation holds in the empty form . A tail bound supplies the missing justification, as does in the third worked example.
Common mistake
(Reading a stationary distribution as a limiting distribution)
Existence of with says nothing about convergence from a fixed start. The alternating chain has , while alternates between and . Ordinary convergence needs aperiodicity in addition to finite irreducibility.
On a countably infinite space a second hypothesis of the finite theorem fails silently, and the following example shows what is lost.
Counterexample mode
Recurrence alone does not give a stationary probability
Claim: an irreducible recurrent chain has a stationary probability distribution. Take simple symmetric random walk on all integers. It is recurrent: , whose sum diverges, so the first theorem gives . It preserves counting measure, an invariant measure of infinite total mass. But stationarity would require , so is affine in ; no nonnegative nonzero affine sequence on all integers is summable. Hence there is no stationary probability, and the walk is null recurrent. The repaired statement requires positive recurrence: in an irreducible chain a stationary probability exists exactly when the chain is positive recurrent, which finiteness guarantees.
Summary
Transition powers describe finite-time laws, first-step equations describe hitting, and return cycles explain equilibrium. Finite irreducibility guarantees positive recurrence and a unique positive stationary law. Aperiodicity adds convergence from each starting state. For infinite chains, summability and finite return means are genuine extra requirements, and harmonic equations must be interpreted with their minimal-solution condition.
Exercises
Quick check
(Find the stationary distribution and mean return times for . Does convergence hold from each state?)
Use the balance equation between the two states.
Solution · Answer
Balance gives , so and mean returns are and . Positive cross-transitions give irreducibility and positive diagonal entries give aperiodicity, so convergence holds.
Quick check
(A chain has absorbing states and . From and , it moves to either neighboring integer with probability . Find the probability of hitting before and the expected absorption time from each interior state.)
Write the first-step equations, then check finiteness.
Solution
Put . Equations and give . For means, , and give . Finiteness follows because from either interior state the probability of absorption on the next step is , so the survival tail is .
Quick check
(Give a reducible chain with more than one stationary distribution, and describe all of them. Explain why this does not contradict the irreducible theorem.)
Two absorbing states suffice.
Solution · Answer
Take on two states. Every probability vector , , is stationary because both states are absorbing. They do not communicate, so the theorem's irreducibility hypothesis is absent.
Quick check
(A state has first-return probability . Find the expected total visits, including time zero, and the probability of at least three visits.)
Each return is a fresh trial with success probability .
Solution
The expected total is . At least three visits require two successful returns, with probability . The state remains transient: finite expected total visits is compatible with a substantial probability of returning several times.