Motivation
A finite irreducible chain cannot continually discover new states. On an infinite space it can, and the familiar finite-state equilibrium theorem needs a replacement. Even a chain that returns almost surely may spend so long on excursions that no probability distribution can describe its equilibrium. The distinction is between returning eventually and returning with a finite mean.
The right unit of analysis is a complete excursion away from one reference state. During an excursion we count visits to every state. Dividing the expected visit counts by the expected excursion length should produce a probability distribution. The word “should” hides two issues: the length might have infinite expectation, and an infinite sum must be justified. We resolve both rather than formally normalizing an infinite measure.
It uses the strong law for independent integrable random variables as a prerequisite, not as a theorem proved here. All other ingredients needed for the stated countable-chain conclusions are developed below. Distributions are row vectors, and time is discrete.
Definitions
Definition 2.2.1
(Return time, positive recurrence and cycle occupation)
Let be a stochastic matrix on a countable space , and assume irreducibility. Fix and write
Recurrence means . Positive recurrence additionally requires ; recurrence with infinite mean is null recurrence.
In a recurrent irreducible chain, every initial state hits every other state almost surely. Indeed, a recurrent state has infinitely many returns; at each return there is a fixed positive chance of following a finite path to the target. Repeated failure has probability tending to zero. The Markov property at a hitting time follows by splitting according to its possible integer values.
The vector counts one cycle including its starting visit to but excluding the terminal return, so . Its total mass is by Tonelli's theorem, which exchanges nonnegative sums and expectations even when the result is infinite. Each individual is finite in the recurrent case: from a fixed simple path reaches before another visit to with positive probability, bounding the number of visits to before hitting by a geometric tail.
Definition 2.2.2
(Total variation distance and aperiodicity)
For probability vectors , total variation distance is
Aperiodicity means that the positive return lengths at a state have greatest common divisor one; irreducibility makes the period common to all states. A stationary probability satisfies .
Concept lensStructural
Total variation as the best possible coupling
Total variation is also the smallest disagreement probability among all couplings: over pairs with and . For any coupling, . Conversely, put mass on each diagonal point ; the remaining mass is , and the two normalized excesses have disjoint supports, so their product puts it off the diagonal. The meeting argument below is one coupling, giving an upper bound.
Theorem/proposition
Theorem 2.2.3
(Countable stationary criterion and Kac's formula)
An irreducible countable chain has a stationary probability distribution exactly when it is positive recurrent. That distribution is unique, all entries are positive, and
The reference state can be any state, so every state has mean return time .
Theorem 2.2.4
(Occupation averages and ordinary convergence)
For an irreducible positive recurrent countable chain, from any initial state and for every ,
If the chain is also aperiodic, then for every . No rate of convergence is asserted.
Proof sketch or proof idea
Constructing and identifying the stationary law
Proof
(Return cycles give the stationary law, and conversely)
Suppose first that . Counting expected departures from before the return and using conditional expectation gives
The initial state and terminal state are both , so replacing indices by changes no net count. Every exchange of sums is nonnegative. Dividing by the finite total gives a stationary probability.
Conversely, suppose a stationary probability exists. Irreducibility implies for every : a state with positive mass can reach any other state in finitely many steps, and . Start the process in . The events “time is the last visit ever to ” are disjoint and all have probability . Their sum cannot exceed one, so this common probability is zero. Thus is recurrent. Applying the argument at each state and irreducibility gives almost-sure hitting of from every start.
To identify , decompose according to the last visit to among times zero through . If that visit is at time , its contribution is . The remaining contribution comes from paths avoiding altogether. Its total mass over is at most , where includes time zero. This tends to zero by dominated convergence and almost-sure hitting. Letting increase therefore gives
Summing over yields . Hence is finite, Kac's formula holds, and every stationary probability must equal the cycle construction. Repeating at another reference state proves the corresponding formula there.
From cycles to time averages
Proof
(Regeneration and the strong law)
Successive return cycles from are independent and identically distributed by the hitting-time Markov property. Their lengths have finite mean , and their visit rewards to have mean and are bounded by their lengths. Apply the strong law to these two sequences. The number of complete cycles by time , divided by , tends to , and the reward per complete cycle tends to .
The unfinished cycle causes no asymptotic error. If the successive return times are , the strong law gives , so by subtracting two adjacent normalized sums. The unfinished reward is no larger than that cycle's length, hence is negligible compared with . From another initial state, the first hit of is almost surely finite and contributes only a finite prefix. This proves the pathwise occupation limit. Taking expectations is legitimate because the proportions lie between zero and one, proving the averaged transition limit.
A coupling proof of aperiodic convergence
Proof
(Meeting a stationary copy)
First note an elementary path fact. In an irreducible aperiodic chain, for each pair , for all sufficiently large . At a reference state, finitely many positive return lengths already have greatest common divisor one. Their nonnegative integer combinations contain every sufficiently large integer: choose one length , represent each residue modulo by a nonnegative combination of the finitely many lengths, then add copies of . Such residue representatives exist because the residues generated in the finite cyclic group form the whole group, and in a finite group every inverse is a positive multiple of its element, so nonnegative combinations suffice. Appending fixed paths to and from the reference state proves the fact for .
Now run two independent copies, one starting at and the other in stationarity. Their product chain has transition probabilities and invariant probability . The path fact makes this product chain irreducible: both coordinates can reach prescribed targets in the same sufficiently large number of steps. The stationary criterion just proved makes the product chain recurrent. It therefore hits a fixed diagonal state almost surely.
At that meeting time, use the same future transitions for both copies. Each marginal still follows the original chain, by the hitting-time Markov property, but the copies now agree forever. For any set , the difference of their probabilities of belonging to is bounded by the probability that meeting has not yet occurred. That probability tends to zero. Taking the supremum over proves total-variation convergence. The stationary second copy can have any initial state under its stationary mixture, since recurrence holds from every product state.
Proof X-ray
Where each hypothesis enters
Finite mean return length allows cycle normalization and the strong law for rewards. Irreducibility spreads recurrence and forces a unique law. Aperiodicity is used only to make the independent product chain irreducible in the convergence proof. Removing it does not invalidate the cycle averages or Kac's identity.
There is a useful detail behind the irreducibility step. Starting at recurrent , repeated attempts along a fixed path force eventual hitting of . If, starting from that , the chance of never hitting were positive, following a simple positive-probability path from to before any return, and then avoiding would give a positive chance of no return to , a contradiction. Thus every state hits almost surely. Repeating this argument with another target gives the full recurrence class property used by both the cycle and coupling arguments.
Worked examples
Worked example 2.2.5
(A chain that resets after a countdown)
From zero choose a nonnegative integer with probabilities , jump to , and thereafter count down deterministically to zero. Assume for every and . A return cycle has length . State is visited exactly when , so
For , and , including . The positive self-loop at zero makes the chain aperiodic, hence convergence holds in total variation. If instead the reset law has infinite mean but finite values almost surely, every excursion still returns, yet no stationary probability exists.
Worked example 2.2.6
(A null-recurrent integer walk)
For simple symmetric random walk on all integers, . The divergent expected-visit series proves recurrence. A candidate invariant probability vector would satisfy , so its successive differences are constant. The only nonnegative affine sequences on the entire integer line are nonnegative constants, and no nonzero such sequence is summable. Kac's criterion therefore identifies the chain as null recurrent. It also has period two; recurrence and aperiodicity are separate questions.
Worked example 2.2.7
(Finite mean does not remove periodicity)
A deterministic two-state alternation has mean return time two at each state and stationary law . Each sample path spends an asymptotic half of its steps in each state. Starting at a fixed state, however, the one-time law alternates forever, so total-variation convergence fails. The independent product chain splits into the diagonal and off-diagonal classes; this pinpoints the failed hypothesis in the coupling argument.
Common mistakes
Common mistake
(Normalizing an infinite invariant vector)
An invariant vector with infinite total mass is not a probability law. Conversely, a finite sum of proposed weights is not enough unless invariance is proved for the actual chain. The return-cycle argument supplies both properties under exact hypotheses. Averages along one dependent trajectory are justified here by regeneration, not by pretending that successive states are independent.
Counterexample mode
Convergence from each start is not uniform over starts
A tempting strengthening of the convergence theorem is . The countdown chain with refutes it, although that chain is irreducible, aperiodic and positive recurrent with . Started at , the chain is at at every time , so and
Since is arbitrary, the supremum over starting states is at least at every fixed time. The theorem asserts convergence for each fixed start. On a finite space the maximum over finitely many starts does tend to zero, but on a countable space uniformity needs separate control.
Nor does total-variation convergence require the mean time of the particular coupling constructed above to be finite; almost-sure finite meeting suffices.
Summary
Return cycles turn recurrence into a normalization problem. A finite mean cycle is equivalent to a unique stationary probability, and its reciprocal gives the mass of the reference state. Regenerative rewards prove occupation averages. Aperiodicity then permits a product-chain coupling that upgrades averages to convergence of the one-time law.
Exercises
Quick check
(In the countdown model, let with . Find the stationary law and all mean return times.)
Use and Kac's formula.
Solution · Answer
The geometric tail is and . Thus for all , and . The zero self-loop gives aperiodicity.
Quick check
(Suppose , , where normalizes the probabilities. Classify the countdown chain and justify your answer without evaluating .)
Compare with the harmonic series.
Solution
The probabilities sum because the square-reciprocal series converges, but by comparison with the harmonic series. Each selected is finite almost surely, so every return occurs, with infinite mean. The chain is irreducible and null recurrent; no stationary probability exists.
Quick check
(A stationary irreducible chain has . Find the mean return time to and the long-run visit proportion. Does this information alone prove ordinary convergence?)
Separate time averages from one-time laws.
Solution · Answer
Kac gives five steps. The occupation proportion tends almost surely to . Ordinary convergence also requires aperiodicity in the theorem being used; the value of alone does not verify it.
Quick check
(Explain exactly why the product-chain coupling fails for deterministic alternation started in opposite states, even though each individual chain is positive recurrent.)
Track the difference of the two coordinates modulo two.
Solution
Independent deterministic coordinates started oppositely remain opposite at every step. The product chain cannot reach a diagonal state and is reducible. A stationary probability on the whole product space therefore cannot be used to infer irreducible recurrence from an off-diagonal start. The missing aperiodicity condition is exactly what allowed the earlier product irreducibility proof.