RobotGuide
Math foundations/Markov Chains: When the Time Average Equals the Ensemble Average

Foundations T18 / 27 · Convergence and Fixed Points

Markov Chains: When the Time Average Equals the Ensemble Average

Why is it legitimate for the replay buffer to destroy temporal correlations, and what exactly is the on-policy distribution? The answers live in the stationary distribution and the ergodic theorem — provided the chain is irreducible and aperiodic. You need both; neither is optional.

about 55 min2 theorems6 proof steps4 self-test questions

One-line takeaway

A finite Markov chain that is irreducible and aperiodic has a unique stationary distribution π; from any initial distribution, π_k = π_0 P^k converges to it, and the time average converges to π (the ergodic theorem). Drop either premise and every conclusion can fail.

Estimating state-visitation probabilities by trajectory frequencies during policy evaluation, designing importance weights for off-policy correction, sampling old trajectories from a replay buffer — the legitimacy of each of these rests on this page's theorems. Going one level deeper: the stationary distribution of the Markov chain induced by policy π is the on-policy visitation distribution d^π — the very weight term in the policy gradient theorem.

Why this tool exists

Two practical questions first. One: you ran 100,000 steps in an environment and want to know how often some state occurs — is that «frequency» stable? Does it converge to a definite value? Two: the data in a replay buffer is highly correlated in time (adjacent steps are almost the same local scene); you sample from it randomly and treat samples as independent — on what grounds?

Both answers point to the same pair of concepts: the stationary distribution (the distribution of states after the system runs for a long time) and ergodicity (time average equals ensemble average). «Is it stable?» is answered by the former; «on what grounds?» by the latter.

Fix the objects first: finite state set {1,…,n}, transition matrix P (P_ij = probability of going from i to j in one step, row-stochastic: each row sums to 1). The chain being Markov means: the next-step distribution depends only on the current state, not on how the current state was reached.

Now the two premises. Irreducible: from any state you can (in some number of steps) reach any other state — the chain does not shatter into islands. Aperiodic: the return times to the same state are not all multiples of some d>1 — the chain does not march to a beat. The textbook periodic chain: deterministic alternation A→B→A→B; its distribution oscillates between the two states forever and never converges.

Definitions

Definition 6.1 Stationary distribution

A row vector π satisfying π = πP with Σπ_i = 1 and π_i ≥ 0 is called a stationary distribution. Meaning: if the current state distribution is π, then after one step it is still π — the system has reached statistical equilibrium.

Why define it this wayNote that this is a «fixed-point equation»: π is the left eigenvector of the transition operator for eigenvalue 1. This is a different beast from the fixed point in T5 — there it was pointwise iteration of the value-function vector, here it is matrix multiplication on distributions — but the idea «iterate to find the equilibrium» is the same lineage.

Definition 6.2 Time average and ensemble average

Time average: along one long trajectory, the frequency with which state i occurs, (1/T)Σ1s_t=i. Ensemble average: the probability of i in the state distribution at a fixed time, which after a long time is π_i. Ergodicity = the two are equal as T→∞.

Why define it this wayEvery «estimate from experience» in RL silently assumes ergodicity. This page's job is to say precisely when that assumption holds.

Theorems and proofs

Theorem 6.1 An irreducible finite chain has a unique stationary distribution

P irreducible (finite state space) ⇒ there exists a unique π=πP (a probability vector). If the chain is additionally aperiodic, every row of P^k converges to π.

Proof

Existence (constructive): take any initial distribution μ and consider the Cesàro average μ_k = (1/k)Σj=1k μP^j. On a finite-dimensional space the set of probability vectors is compact, so μ_k has a convergent subsequence; call its limit π.

π is a fixed point: πP = lim (1/k)Σ μPj+1 = lim (1/k)(Σj=2k+1 μP^j) = π + lim (μPk+1 − μP)/k = π (the last term is crushed by 1/k). Normalization and nonnegativity survive the limit. ∎ (existence)

Uniqueness (main step): let π and ν both be fixed points. Key fact: in an irreducible chain, for any states i, j there is an m with (P^m)_ij > 0 (i can reach j). Hence π_i = Σ_l π_l (P^m)_li ≥ π_j (P^m)_ji > 0 — every π_i > 0 (the stationary distribution is strictly positive).

Now take π = πP^m and ν = νP^m and compare the two on some «heaviest» state: set δ_i = π_i/ν_i and pick the state k minimizing δ; then for any i: π_i = Σ_l π_l (P^m)_li ≥ Σ_l δ_k·ν_l (P^m)_li = δ_k ν_i, i.e., δ_i ≥ δ_k for all i. Since Σπ=Σν=1, all δ_i are equal — so π=ν. ∎ (uniqueness)

Convergence (statement of the main step): in the aperiodic case, every eigenvalue of P other than modulus 1 has absolute value <1 (content of the Perron-Frobenius theorem), giving geometric decay ⇒ P^k → 1π (every row equal to π). The complete proof depends on eigenvalue theory and lies outside this page's scope.

NoteHonest labeling: the existence and uniqueness proofs are complete; the convergence rate relies on the Perron-Frobenius theorem and is only stated. The periodic counterexample (deterministic alternation) shows aperiodicity cannot be dropped for distribution convergence — but existence and uniqueness of the stationary distribution do not need it.

Theorem 6.2 Ergodic theorem (statement + intuitive argument)

On an irreducible positive-recurrent chain, the time average converges almost surely: limT→∞ (1/T)Σt=1T 1s_t=i = π_i.

Proof

The full proof (the Birkhoff ergodic theorem, or the Markov-chain-specific version) is out of scope. The intuitive argument chain: the stationary distribution is an «invariant» measure → the system's long-run behavior is governed by π → a single trajectory «sees» every state (guaranteed by irreducibility) and visits them in π's proportions (guaranteed by positive recurrence) → frequencies become probabilities.

NoteIn RL this is assumed to hold almost always. Know the failure cases: the chain splits into disconnected blocks (the time average depends on which block you started in), absorbing states (all frequency piles up in the absorber), periodic chains (frequencies still converge to π but the distribution sequence oscillates). When reward design creates an absorbing state (an episode getting stuck), «empirical frequency = expected frequency» quietly breaks.

Work it by hand

Two-state chain: P(0→0)=0.9, P(0→1)=0.1, P(1→0)=0.2, P(1→1)=0.8. Compute the stationary distribution by hand and estimate the mixing speed.

  1. Solve π=πP. First component: π_0 = 0.9π_0 + 0.2π_1 → 0.1π_0 = 0.2π_1 → π_0 = 2π_1.
  2. Add normalization: π_0 + π_1 = 1 → π = (2/3, 1/3).
  3. Verify flow balance (an independent check): the probability flow from 0 to 1 is π_0·0.1 = 1/15, and from 1 into 0 it is π_1·0.2 = 1/15 — equal ✓.
  4. [object Object]
  5. Distribution error ~ 0.7^k: at k=10, 0.7^10≈0.028; at k=20, 0.0008. Matches the measurement (after P^10, [0.7467, 0.2533], error 0.080 — on the order of π_0·0.7^10).
Answer

π=(2/3, 1/3), with a mixing timescale ~1/(1−λ₂)≈3.3 steps (error halves every 3 steps). The hand computation used three moves — «solve a linear system + verify flow balance + estimate via eigenvalues» — all resting only on this page's definitions.

Run the numbers

Where the numbers come from

Measurements on the same chain (eigenvector method + 400,000-step simulation):

  • Stationary distribution (eigenvector of P^T) = [0.666667, 0.333333], matching the hand computation digit for digit
  • Distribution convergence: after P^1 [0.900, 0.100] → P^5 [0.781, 0.219] → P^10 [0.747, 0.253] → P^20 [0.723, 0.277] → π
  • Time average (frequency of s0): first 1000 steps 0.714 (not yet mixed) → 10,000 steps 0.6706 → 100,000 steps 0.6686 → 0.6667
  • The convergence rate is governed by the subdominant eigenvalue 0.7: 0.7^20 ≈ 8e−4, same order as the residual deviation of 0.002 at 100,000 steps

Where this shows up

The object hereThe counterpart in RLUsed in
Stationary distribution πThe on-policy state visitation distribution d^π under policy π — the weight in the policy gradient theoremused in →
Ergodic theoremThe foundational legitimacy for replay buffer sampling ≈ i.i.d. samplingused in →
Periodicity failureWhen an episode gets stuck in a loop, empirical frequencies drift away from d^πused in →
Mixing timeWhen exploration is insufficient, the «effective sample size» of collected data shrinksused in →

Boundaries: where this article stops

Where this page stops: ergodic theory on general state spaces (Harris chains), quantitative bounds on mixing time, and reversible chains with detailed balance — none of these. The workhorse criterion: finite states + irreducible + aperiodic, and every theorem in this page applies; RL environments almost always satisfy it (exploration noise makes every state reachable).

Self-test: 4 questions

All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.

01What conditions are needed for existence and uniqueness of the stationary distribution? And what for convergence of the distributions?

Existence and uniqueness: irreducibility (finite chain). Distribution convergence (every row of P^k → π): add aperiodicity. Counterexample: the deterministic alternating chain A↔B has a unique stationary distribution (1/2,1/2), but P^k oscillates between two distributions forever — stationarity and convergence are two different things.

02The replay buffer treats correlated data as independent samples. Which part does the ergodic theorem guarantee, and what is still missing?

The ergodic theorem guarantees time average → π (long-run frequencies are legitimate). Missing is «variance analysis for finite samples» — correlated samples have a smaller effective sample size than independent ones (the longer the mixing time, the more it shrinks). In practice, a big enough buffer plus random sampling breaks correlations down to acceptable levels, but there is no free lunch.

03For the two-state chain P(0→0)=0.5, P(0→1)=0.5, P(1→0)=0.5, P(1→1)=0.5, what is the stationary distribution? And the mixing speed?

π=(1/2,1/2). The subdominant eigenvalue = trace − 1 = 0 — mixed in a single step (every row of P is already π). Compare with the 0.7 of the previous question: the more «forgetful» the chain, the faster it mixes. One more demonstration that mixing time is governed by the subdominant eigenvalue.

04During training, d^π changes whenever the policy updates. Does this conflict with this page's theorems?

No conflict, but separate the timescales: for each fixed policy π, the environment is a fixed Markov chain and d^π is its stationary distribution (this page's theorems apply); a policy update is «switching to a different chain». This is fundamentally a two-timescale problem — the subject of T10.

Up next

The full series · 27 articles

T1The Matrix Is a Ledger for Rotation≈ 25 minT2From Slope to Gradient: The First Line of Every Robot Learning Algorithm≈ 25 minT3Vectors and forces: the physical reading of the dot productAbout 20 minT4Two Rulers and a Better Rulerabout 25 minT5The Ledger of One Motor Revolution: Radians, Speed, and Powerabout 20 minT6Complex multiplication is rotation: the one-dimensional version of quaternionsAbout 20 minT7Bases and coordinates: why robots put everything in matrices45 minT8Matrix Multiplication: Chaining Transformations, Not a Table OperationAbout 40 minT9The Jacobian: Rotate a Joint One Degree — How Far Does the End Effector Move?About 45 minT10Eigenvectors: The Directions a Matrix Dare Not Touchabout 45 minT11SVD and the Pseudoinverse: When There Is No Exact Solution, Find the Nearest Oneabout 50 minT12Taylor expansion: putting a straight line to work in place of a curveAbout 40 minT13Probability spaces: why «random» needs axioms50 minT14Expectation: A Rigorous Construction of «Average»About 55 minT15Conditional Expectation: What the Vertical Bar Really Means≈ 60 minT16Four inequalities: the quantitative answer to «how many samples are enough»45 minT17Norms and fixed points: where «it always converges» comes from55 minT18Markov Chains: When the Time Average Equals the Ensemble Averageabout 55 minT19The Mathematical Construction of the MDP: What One Axiom Is Worthabout 50 minT20Dynamic Programming: The Accounting for Two Iterations≈ 50 minT21Optimization: why constraints cannot rely on penalties aloneAbout 55 minT22Stochastic Approximation: Every Term in the Learning-Rate Formulaabout 55 minT23The Mathematics of Contact: Hertz Theoryabout 45 minT24Friction and the Friction Cone: The Geometry of Constraintsabout 40 minT25Force Closure and Grasp Metrics: ε Is a Linear ProgramAbout 50 minT26Contact Kinematics: Why Rolling Is Not «Sliding Along»≈ 45 minT27Slip detection: from «I felt it» to «I computed it»About 50 min