The Ergodic Theorem for Markov Chains and Detailed Balance

Intuition Beginner

Run a Markov chain for a very long time and keep a tally: of all the steps so far, what fraction landed on each state? The ergodic theorem says this fraction settles down to the equilibrium weight of that state, no matter where you started. The chain's travel diary — the long-run share of time spent in each place — reproduces the equilibrium distribution exactly. More than that: if you attach a number to each state, say a payoff, then the average payoff per step over a long run converges to the payoff you would get by drawing a single state from equilibrium. Time-averages turn into equilibrium-averages.

Why care? Because it lets you compute hard equilibrium quantities by simply running the chain and averaging. You do not need to solve for the equilibrium weights by hand; you let the chain do the work and read the answer off the diary. This single idea powers a huge family of practical algorithms.

The second theme is reversibility. Some chains run the same backwards as forwards: if you filmed a long equilibrium run and played the film in reverse, you could not tell which way time was flowing. The precise condition for this is a balance rule — for every pair of states, the equilibrium traffic flowing from the first to the second equals the traffic flowing back. This rule is called detailed balance. It is a stronger, more local condition than mere equilibrium, and chains that obey it are especially well-behaved.

Detailed balance is also a design tool. Suppose you have a target distribution you want to sample from — maybe the shape of some complicated probability law you can only evaluate up to an overall constant. You can build a chain, by hand, whose equilibrium is exactly that target, by arranging its moves to satisfy detailed balance. Then you run the chain, average along the way, and the ergodic theorem hands you estimates of the target. This recipe is called the Metropolis-Hastings algorithm, and it is one of the most-used computational ideas in all of science.

The takeaway: the ergodic theorem says long-run time-averages of a chain equal equilibrium-averages; detailed balance is the local balance rule for chains that look the same run backwards; and together they let you design a chain to sample any target distribution you like.

Visual Beginner

Picture a long run of a chain, the tally of time spent in each state, and the backwards-run symmetry of detailed balance.

Top: one long run of the chain. Counting the fraction of steps spent in each state and comparing to the equilibrium bars on the right shows them matching — this is the ergodic theorem. Bottom: the detailed-balance picture. The flow of equilibrium probability from state $i$ to state $j$ in one step is the height ${\pi }_i$ times the move-chance $p_{ij}$; detailed balance says this equals the reverse flow ${\pi }_j$ times $p_{ji}$, so every individual pair of states is in balance, not just the totals.

Worked example Beginner

Take a chain on three states $\{1,2,3\}$ where from any state you stay put with probability $\frac{1}{2}$, and otherwise move to one of the other two states, each with probability $\frac{1}{4}$. By symmetry the equilibrium gives each state weight $\frac{1}{3}$. We will see two things: that the long-run time-share is $\frac{1}{3}$ for each state, and that the chain satisfies detailed balance.

Step 1. Check detailed balance against the equal-weight equilibrium. Pick states $1$ and $2$. The forward flow is the equilibrium weight of state $1$ times the chance of moving $1\to 2$, which is $\frac{1}{3}\times \frac{1}{4}=\frac{1}{12}$. The backward flow is the weight of state $2$ times the chance of moving $2\to 1$, which is $\frac{1}{3}\times \frac{1}{4}=\frac{1}{12}$. They are equal. The same holds for every pair, so detailed balance holds and the equal-weight distribution is the equilibrium.

Step 2. Predict the long-run time-share. The ergodic theorem says the fraction of steps spent in each state converges to its equilibrium weight $\frac{1}{3}$.

Step 3. Average a payoff. Suppose state $1$ pays $6$ dollars, state $2$ pays $0$, and state $3$ pays $3$. The equilibrium average payoff is $\frac{1}{3}\times 6+\frac{1}{3}\times 0+\frac{1}{3}\times 3=2+0+1=3$ dollars.

Step 4. Read the ergodic conclusion. Over a long run, the average payoff per step converges to $3$ dollars — the same number you would get by drawing one state from equilibrium and collecting its payoff. You did not need to know the equilibrium in advance to estimate this: a long enough run, averaged, would have revealed it.

What this tells us: detailed balance is a quick local check that a guessed distribution is the equilibrium, and once you have the equilibrium, the long-run average of any per-state payoff equals the equilibrium average of that payoff. Running and averaging replaces solving.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $(X_n{)}_{n\ge 0}$ is a time-homogeneous Markov chain on a countable state space $I$ with stochastic transition matrix $P=(p_{ij})$, as in 37.05.01. Communication, irreducibility, and period are as in 37.05.02; the strong Markov property, the first-return time $T_i:=\inf \{n\ge 1:X_n=i\}$, and recurrence are as in 37.05.04. The invariant distribution theory — existence of a nonzero invariant measure for an irreducible recurrent chain, positive recurrence as finiteness of the mean return time $m_i:={\mathbb{E}}_i[T_i]$, and the Kac identity ${\pi }_i=1/m_i$ — is 37.05.05, whose results are used freely. We write ${\mathbb{E}}_{\pi }[f]:={\sum }_i{\pi }_{i}f(i)$ for a function $f:I\to \mathbb{R}$ and an invariant distribution $\pi$.

Definition (additive functional and time-average). Given $f:I\to \mathbb{R}$, the additive functional of $f$ along the chain is $S_n(f):={\sum }_{k=0}^{n-1}f(X_k)$, and the time-average (or empirical average) is $\frac{1}{n}{S}_n(f)=\frac{1}{n}{\sum }_{k=0}^{n-1}f(X_k)$. The special case $f=1_{\{i\}}$ gives $\frac{1}{n}{S}_n(1_{\{i\}})=V_i(n)/n$, the fraction of the first $n$ steps spent at state $i$, where $V_i(n):={\sum }_{k=0}^{n-1}{1}_{\{X_k=i\}}$ is the occupation count.

Definition (reversibility and detailed balance). A measure $\nu =({\nu }_i{)}_{i\in I}$ with ${\nu }_i\ge 0$ is in detailed balance with $P$ if $${\nu }_i{p}_{ij}={\nu }_j{p}_{ji}\text{for all }i,j\in I.$$ A chain is reversible with respect to $\nu$ if $\nu$ is in detailed balance with $P$. When $\nu =\pi$ is a probability distribution, reversibility is equivalent to the statement that the stationary chain run backwards is again a Markov chain with the same law: for $X_0\sim \pi$, the reversed sequence $(X_n,X_{n-1},\dots ,X_0)$ has the same distribution as $(X_0,X_1,\dots ,X_n)$. The reversed transition matrix is ${\hat{p}}_{ij}:={\pi }_j{p}_{ji}/{\pi }_i$ (for ${\pi }_i>0$); reversibility is exactly $\hat{P}=P$.

Definition (Metropolis-Hastings chain). Fix a target distribution $\pi$ on $I$ with ${\pi }_i>0$, known possibly only up to a normalising constant, and a proposal matrix $Q=(q_{ij})$ that is irreducible. The Metropolis-Hastings chain proposes a move $i\to j$ with probability $q_{ij}$ and accepts it with probability $${\alpha }_{ij}:=\min \left(1,\frac{{\pi }_j{q}_{ji}}{{\pi }_i{q}_{ij}}\right),$$ otherwise staying at $i$. Its transition matrix is $p_{ij}=q_{ij}{\alpha }_{ij}$ for $j\ne i$ and $p_{ii}=1-{\sum }_{j\ne i}{q}_{ij}{\alpha }_{ij}$. Only the ratios ${\pi }_j/{\pi }_i$ enter ${\alpha }_{ij}$, so the normalising constant of $\pi$ is never needed.

The chain on $\{1,2,3\}$ with stay-probability $\frac{1}{2}$ and equal $\frac{1}{4}$ moves to the other two states is reversible with respect to $\pi =(\frac{1}{3},\frac{1}{3},\frac{1}{3})$, since ${\pi }_i{p}_{ij}=\frac{1}{3}\cdot \frac{1}{4}={\pi }_j{p}_{ji}$ for $i\ne j$. The simple symmetric random walk on $\mathbb{Z}$ is reversible with respect to the counting measure ${\nu }_i\equiv 1$, exhibiting a reversible measure without a reversible distribution (the chain is null recurrent, 37.05.05).

Counterexamples to common slips Intermediate+

• Detailed balance is sufficient for invariance but not necessary. Summing ${\nu }_i{p}_{ij}={\nu }_j{p}_{ji}$ over $i$ gives ${\sum }_i{\nu }_i{p}_{ij}={\nu }_j{\sum }_i{p}_{ji}={\nu }_j$, so $\nu =\nu P$. The converse fails: a directed three-cycle $1\to 2\to 3\to 1$ has $\pi =(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ invariant, yet ${\pi }_1{p}_{12}=\frac{1}{3}\ne 0={\pi }_2{p}_{21}$, so it is stationary but not reversible.

• The ergodic theorem needs positive recurrence, not merely recurrence. On a null recurrent chain the mean return time is infinite, the denominator in the renewal-reward ratio diverges, and the time-average of a $\pi$-integrable $f$ tends to $0$, not to ${\mathbb{E}}_{\pi }[f]$ (which is undefined, as no invariant distribution exists).

• The ergodic theorem does not require aperiodicity. Unlike convergence to equilibrium 37.05.06, the law of large numbers for time-averages holds for periodic chains too: averaging over time washes out the cyclic rotation. Aperiodicity governs convergence of the marginal law $p_{ij}^{(n)}$, a separate question.

• The Metropolis acceptance ratio carries the proposal asymmetry. Omitting the $q_{ji}/q_{ij}$ factor (the Hastings correction) gives a chain reversible for the wrong distribution when the proposal is asymmetric. With a symmetric proposal $q_{ij}=q_{ji}$ the ratio collapses to $\min (1,{\pi }_j/{\pi }_i)$, the original Metropolis rule.

Key theorem with proof Intermediate+

Theorem (ergodic theorem for Markov chains). Let $P$ be irreducible and positive recurrent with invariant distribution $\pi$, and let $f:I\to \mathbb{R}$ satisfy ${\sum }_i{\pi }_i|f(i)|<\infty$. Then for every initial distribution, almost surely $$\frac{1}{n}\sum _{k=0}^{n-1}f(X_k)⟶\sum _i{\pi }_{i}f(i)={\mathbb{E}}_{\pi }[f](n\to \infty ).$$ In particular, taking $f=1_{\{i\}}$, the long-run fraction of time at state $i$ satisfies $V_i(n)/n\to {\pi }_i=1/m_i$ almost surely.

Proof. Fix a reference state $k$. By irreducibility and recurrence (37.05.04) the chain visits $k$ infinitely often, so the successive visit times $0\le {\tau }_0<{\tau }_1<{\tau }_2<\cdots$ to $k$ are almost surely finite; here ${\tau }_0:=\inf \{n\ge 0:X_n=k\}$ and ${\tau }_r:=\inf \{n>{\tau }_{r-1}:X_n=k\}$. Define the excursion sums and excursion lengths for $r\ge 1$, $$W_r:=\sum _{n={\tau }_{r-1}}^{{\tau }_r-1}f(X_n),L_r:={\tau }_r-{\tau }_{r-1}.$$ By the strong Markov property at the stopping times ${\tau }_{r-1}$ (37.05.04), the blocks $(W_r,L_r)$ for $r\ge 1$ are independent and identically distributed, each distributed as a single excursion from $k$ back to $k$ started afresh at $k$.

Compute their means. The length has $\mathbb{E}[L_1]={\mathbb{E}}_k[T_k]=m_k$, finite by positive recurrence. For the sum, using the excursion measure ${\gamma }_i^k={\mathbb{E}}_k[{\sum }_{n=0}^{T_k-1}{1}_{\{X_n=i\}}]$ of 37.05.05, which satisfies ${\gamma }^k=m_k\pi$ (since $\pi ={\gamma }^k/m_k$), $$\mathbb{E}[W_1]={\mathbb{E}}_k\left[\sum _{n=0}^{T_k-1}f(X_n)\right]=\sum _{i}f(i){\gamma }_i^k=m_k\sum _i{\pi }_{i}f(i)=m_k{\mathbb{E}}_{\pi }[f],$$ the interchange of sum and expectation justified by ${\sum }_i|f(i)|{\gamma }_i^k=m_k{\sum }_i{\pi }_i|f(i)|<\infty$ ($\pi$-integrability) and absolute convergence. So $\mathbb{E}[|W_1|]<\infty$ and $\mathbb{E}[L_1]<\infty$.

Now squeeze. For $n\ge {\tau }_0$, let $R=R(n):=\max \{r:{\tau }_r\le n\}$ be the number of completed excursions by time $n$; since the ${\tau }_r$ are finite, $R(n)\to \infty$ a.s. Writing $S_n(f)={\sum }_{k=0}^{n-1}f(X_k)$ and isolating the initial segment before ${\tau }_0$ and the incomplete final excursion, $$S_n(f)=\underset{\text{fixed, finite}}{\underbrace{\sum _{n^{\prime }<{\tau }_0}f(X_{n^{\prime }})}}+\sum _{r=1}^R{W}_r+\underset{\text{partial block}}{\underbrace{\sum _{n^{\prime }={\tau }_R}^{n-1}f(X_{n^{\prime }})}}.$$ Apply the strong law of large numbers 37.02.02 to the i.i.d. sequences $(W_r)$ and $(L_r)$: $$\frac{1}{R}\sum _{r=1}^R{W}_r\to \mathbb{E}[W_1]=m_k{\mathbb{E}}_{\pi }[f],\frac{1}{R}\sum _{r=1}^R{L}_r=\frac{{\tau }_R-{\tau }_0}{R}\to \mathbb{E}[L_1]=m_k\text{a.s.}$$ Because ${\tau }_R\le n<{\tau }_{R+1}$, we have ${\tau }_R/R\to m_k$ and ${\tau }_{R+1}/R\to m_k$, hence $n/R\to m_k$ as well. The fixed initial segment contributes $o(n)$, and the partial final block is bounded in expectation per excursion and contributes $o(n)$ along the recurrence times by the standard renewal-reward estimate (its length $n-{\tau }_R\le L_{R+1}$ satisfies $L_{R+1}/R\to 0$, and the SLLN for $\sum |f(X_n)|$ over a block controls the partial sum). Therefore $$\frac{S_n(f)}{n}=\frac{\frac{1}{R}{\sum }_{r\le R}{W}_r+o(1)}{\frac{1}{R}n}⟶\frac{m_k{\mathbb{E}}_{\pi }[f]}{m_k}={\mathbb{E}}_{\pi }[f]\text{a.s.}$$ Setting $f=1_{\{i\}}$ gives $V_i(n)/n\to {\pi }_i=1/m_i$. $\square$

Bridge. This theorem builds toward the entire computational and ergodic-theoretic life of the chapter and appears again in every Monte Carlo estimate, because it certifies that running one long path and averaging recovers an equilibrium expectation. The foundational reason it holds is the strong Markov restart of 37.05.04: each visit to $k$ launches an independent excursion, so the path decomposes into i.i.d. blocks and the SLLN of 37.02.02 applies to the block sums and block lengths separately. The ratio $\mathbb{E}[W_1]/\mathbb{E}[L_1]={\mathbb{E}}_{\pi }[f]$ is exactly the renewal-reward identity, and this is dual to the Kac formula ${\pi }_i=1/m_i$ of 37.05.05, which is the case $f=1_{\{i\}}$ read as a reward of one unit per visit. Putting these together, the time-average is the reward rate of a renewal-reward process whose cycles are excursions, and the central insight is that positive recurrence — finiteness of $m_k$ — is exactly what makes the denominator finite and the rate well defined. The bridge is that this pathwise law of large numbers generalises the marginal convergence $p_{ij}^{(n)}\to {\pi }_j$ of 37.05.06 from one expectation to almost-sure path behaviour, and it is the statement that makes designing a chain by detailed balance into a sampling algorithm.

Exercises Intermediate+

Advanced results Master

The excursion decomposition that proves the ergodic theorem and the detailed-balance condition that defines reversibility meet in the Metropolis-Hastings construction: detailed balance fixes a prescribed stationary distribution, and the ergodic theorem turns one trajectory into a consistent estimator of every $\pi$-expectation. Reversibility additionally makes the transition operator self-adjoint, so the convergence rate becomes a spectral gap.

Theorem 1 (ergodic theorem; central limit refinement). Let $P$ be irreducible positive recurrent with stationary $\pi$ and $f$ $\pi$-integrable. Then $\frac{1}{n}{S}_n(f)\to {\mathbb{E}}_{\pi }[f]$ a.s. If moreover the excursion sums have finite variance, $\mathrm{Var}(W_1)<\infty$ and $\mathrm{Var}(L_1)<\infty$, then a central limit theorem holds: $\sqrt{n}(\frac{1}{n}{S}_n(f)-{\mathbb{E}}_{\pi }[f])\Rightarrow \mathcal{N}(0,{\sigma }_f^2)$ with asymptotic variance ${\sigma }_f^2={\mathrm{Var}}_{\pi }(f)+2{\sum }_{k\ge 1}{\mathrm{Cov}}_{\pi }(f(X_0),f(X_k))$, the sum of the stationary autocovariances. The renewal-reward variance formula ${\sigma }_f^2=\mathbb{E}[(W_1-{\mathbb{E}}_{\pi }[f]L_1{)}^2]/m_k$ exhibits ${\sigma }_f^2$ through the centred excursion reward, and its finiteness is the regeneration condition that makes Monte Carlo error bars meaningful.

Theorem 2 (reversibility, self-adjointness, and the spectral gap). If $P$ is irreducible and reversible with respect to $\pi$, then $P$ is self-adjoint on ${\ell }^2(\pi )$; its spectrum is real and contained in $[-1,1]$, with $1$ a simple eigenvalue (eigenvector the constants). On a finite state space order the eigenvalues $1={\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_{|I|}\ge -1$ and set ${\lambda }_{\star }=\max ({\lambda }_2,|{\lambda }_{|I|}|)$. Then $$\Vert p_{i\cdot }^{(n)}-\pi {\Vert }_{\mathrm{TV}}\le \frac{1}{2}\sqrt{\frac{1-{\pi }_i}{{\pi }_i}}{\lambda }_{\star }^n,$$ so the absolute spectral gap $1-{\lambda }_{\star }$ governs the geometric rate of convergence. Reversibility is what makes this spectral analysis available: a non-reversible chain has a generally non-normal transition matrix whose convergence is not read off real eigenvalues alone. The Dirichlet form $\mathcal{E}(f,f)=\frac{1}{2}{\sum }_{i,j}{\pi }_i{p}_{ij}(f(i)-f(j){)}^2$ and the variational characterisation $1-{\lambda }_2=\min \{\mathcal{E}(f,f)/{\mathrm{Var}}_{\pi }(f)\}$ make the gap estimable by test functions.

Theorem 3 (Metropolis-Hastings: reversibility for an arbitrary target). Given a target $\pi$ with ${\pi }_i>0$ and an irreducible proposal $Q$, the Metropolis-Hastings chain with acceptance ${\alpha }_{ij}=\min (1,{\pi }_j{q}_{ji}/({\pi }_i{q}_{ij}))$ is reversible with respect to $\pi$, hence has $\pi$ as its unique stationary distribution; if additionally it is aperiodic (for instance whenever some proposal is rejected with positive probability), it converges to $\pi$ in total variation, and the ergodic theorem yields $\frac{1}{n}{\sum }_{k<n}f(X_k)\to {\mathbb{E}}_{\pi }[f]$ for $\pi$-integrable $f$. The acceptance rule depends on $\pi$ only through ratios ${\pi }_j/{\pi }_i$, so an unnormalised target ${\pi }_i\propto w_i$ is sampled with no knowledge of the partition function $Z={\sum }_i{w}_i$. Special cases: the original Metropolis rule ${\alpha }_{ij}=\min (1,{\pi }_j/{\pi }_i)$ for symmetric proposals; the Gibbs sampler, where coordinate-wise conditional proposals are accepted with probability one; and Glauber dynamics for spin systems.

Theorem 4 (Birkhoff's pointwise ergodic theorem as the measure-theoretic parent). The Markov-chain ergodic theorem is the special case, for the shift on path space, of Birkhoff's theorem: for a measure-preserving transformation $\Theta$ on a probability space $(\Omega ,\mathcal{F},\mathbb{P})$ and $h\in L^1$, the averages $\frac{1}{n}{\sum }_{k<n}h({\Theta }^k\omega )$ converge a.s. to the conditional expectation of $h$ given the invariant $\sigma$-field, which equals $\mathbb{E}[h]$ when $\Theta$ is ergodic. Taking $\Omega =I^{\mathbb{N}}$ with the stationary law ${\mathbb{P}}_{\pi }$, $\Theta$ the shift, and $h(\omega )=f({\omega }_0)$, the shift is ergodic precisely when $P$ is irreducible (positive recurrent), recovering $\frac{1}{n}{\sum }_{k<n}f(X_k)\to {\mathbb{E}}_{\pi }[f]$. The Markov excursion proof is the constructive, regeneration-based route to the same limit, and it additionally delivers the rate-and-variance information that the abstract theorem suppresses.

Synthesis. The foundational reason one trajectory suffices to compute every equilibrium expectation is the strong Markov restart of 37.05.04: each return to a fixed state regenerates the chain, so the path is a renewal-reward process whose i.i.d. cycles are excursions, and the SLLN of 37.02.02 on the cycle sums and cycle lengths gives the ratio ${\mathbb{E}}_{\pi }[f]$. This is exactly the Kac formula ${\pi }_i=1/m_i$ of 37.05.05 read for the reward $f=1_{\{i\}}$, and it is dual to the marginal convergence $p_{ij}^{(n)}\to {\pi }_j$ of 37.05.06: the ergodic theorem is the pathwise (almost-sure) twin of that distributional limit, the two together asserting that both the time-average and the ensemble-average collapse onto $\pi$. Putting these together with detailed balance, reversibility makes $P$ self-adjoint, so the same positive-recurrence equilibrium is now equipped with a real spectrum whose gap quantifies the rate; the central insight is that designing ${\alpha }_{ij}$ to symmetrise the edge flow forces $\pi$ to be the reversible stationary law of a chain we can simulate, after which the ergodic theorem converts simulation into estimation. The bridge is that the abstract Birkhoff theorem and the concrete excursion argument generalise the elementary ${\pi }_i=1/m_i$ to arbitrary observables, and the Metropolis-Hastings construction is the engineering inverse: prescribe $\pi$, build the reversible chain, and let the ergodic theorem read ${\mathbb{E}}_{\pi }[f]$ off a single run.

Full proof set Master

Proposition 1 (detailed balance implies stationarity). If $\nu \ge 0$ satisfies ${\nu }_i{p}_{ij}={\nu }_j{p}_{ji}$ for all $i,j$, then $\nu =\nu P$.

Proof. Fix $j$. Summing the detailed-balance identity over $i$, ${\sum }_i{\nu }_i{p}_{ij}={\sum }_i{\nu }_j{p}_{ji}={\nu }_j{\sum }_i{p}_{ji}={\nu }_j$, the last step by row-stochasticity ${\sum }_i{p}_{ji}=1$. Thus $(\nu P{)}_j={\nu }_j$ for every $j$, i.e. $\nu =\nu P$. $\square$

Proposition 2 (reversal characterisation). Let $\pi$ be a stationary distribution with ${\pi }_i>0$ and set ${\hat{p}}_{ij}:={\pi }_j{p}_{ji}/{\pi }_i$. Then $\hat{P}$ is stochastic and is the transition matrix of the time-reversed stationary chain; $P$ is reversible with respect to $\pi$ iff $\hat{P}=P$, equivalently iff for $X_0\sim \pi$ the vector $(X_0,\dots ,X_n)$ has the same law as its reversal $(X_n,\dots ,X_0)$ for every $n$.

Proof. Stochasticity: ${\sum }_j{\hat{p}}_{ij}={\sum }_j{\pi }_j{p}_{ji}/{\pi }_i=(\pi P{)}_i/{\pi }_i={\pi }_i/{\pi }_i=1$ by stationarity. For the reversal, under ${\mathbb{P}}_{\pi }$ the finite-dimensional law is ${\mathbb{P}}_{\pi }(X_0=i_0,\dots ,X_n=i_n)={\pi }_{i_0}{p}_{i_0{i}_1}\cdots p_{i_{n-1}{i}_n}$. Reading the same path backwards and inserting ${\pi }_{i_m}{p}_{i_m{i}_{m+1}}={\pi }_{i_{m+1}}{\hat{p}}_{i_{m+1}{i}_m}$ repeatedly gives ${\pi }_{i_n}{\hat{p}}_{i_n{i}_{n-1}}\cdots {\hat{p}}_{i_1{i}_0}$, the law of the $\hat{P}$-chain started from $\pi$ run over the reversed indices. Hence the reversed process is Markov with matrix $\hat{P}$, and equality of forward and reversed laws is $\hat{P}=P$, i.e. ${\pi }_j{p}_{ji}={\pi }_i{p}_{ij}$ for all $i,j$ — detailed balance. $\square$

Proposition 3 (Metropolis-Hastings satisfies detailed balance). For a target $\pi$ with ${\pi }_i>0$ and irreducible proposal $Q$, the chain $p_{ij}=q_{ij}\min (1,{\pi }_j{q}_{ji}/({\pi }_i{q}_{ij}))$ ($j\ne i$) is reversible with respect to $\pi$.

Proof. For $i\ne j$, using $a\min (1,b/a)=\min (a,b)$ with $a={\pi }_i{q}_{ij}>0$ and $b={\pi }_j{q}_{ji}$, $${\pi }_i{p}_{ij}={\pi }_i{q}_{ij}\min \left(1,\frac{{\pi }_j{q}_{ji}}{{\pi }_i{q}_{ij}}\right)=\min ({\pi }_i{q}_{ij},{\pi }_j{q}_{ji}).$$ The right-hand expression is symmetric in $(i,j)$, so it equals $\min ({\pi }_j{q}_{ji},{\pi }_i{q}_{ij})={\pi }_j{p}_{ji}$. The case $i=j$ is an identity (both sides equal ${\pi }_i{p}_{ii}$). Thus ${\pi }_i{p}_{ij}={\pi }_j{p}_{ji}$ for all $i,j$, which is detailed balance; by Proposition 1, $\pi =\pi P$. Irreducibility of the resulting $P$ on the support of $\pi$ follows from irreducibility of $Q$ and positivity of the acceptance on at least the proposed edges, giving uniqueness of $\pi$ as the stationary distribution. $\square$

Proposition 4 (self-adjointness on ${\ell }^2(\pi )$). If $P$ is reversible with respect to $\pi$ (${\pi }_i>0$), then $⟨Pf,g{⟩}_{\pi }=⟨f,Pg{⟩}_{\pi }$ for all $f,g\in {\ell }^2(\pi )$, where $⟨f,g{⟩}_{\pi }={\sum }_i{\pi }_{i}f(i)g(i)$.

Proof. $⟨Pf,g{⟩}_{\pi }={\sum }_i{\pi }_i({\sum }_j{p}_{ij}f(j))g(i)={\sum }_{i,j}{\pi }_i{p}_{ij}f(j)g(i)$. Detailed balance replaces ${\pi }_i{p}_{ij}$ by ${\pi }_j{p}_{ji}$, giving ${\sum }_{i,j}{\pi }_j{p}_{ji}f(j)g(i)$; relabelling the summation indices $i\leftrightarrow j$ yields ${\sum }_{i,j}{\pi }_i{p}_{ij}f(i)g(j)={\sum }_i{\pi }_{i}f(i)({\sum }_j{p}_{ij}g(j))=⟨f,Pg{⟩}_{\pi }$. Absolute convergence of the double sums for $f,g\in {\ell }^2(\pi )$ (Cauchy-Schwarz against the probability weights ${\pi }_i{p}_{ij}$) justifies the rearrangement. $\square$

Proposition 5 (ergodic theorem: occupation form). For irreducible positive-recurrent $P$ with stationary $\pi$, the occupation fraction satisfies $V_i(n)/n\to {\pi }_i$ a.s. for every $i$.

Proof. Apply the Key theorem with $f=1_{\{i\}}$, which is $\pi$-integrable (${\sum }_j{\pi }_j|f(j)|={\pi }_i\le 1$). The excursion sum $W_r={\sum }_{n={\tau }_{r-1}}^{{\tau }_r-1}{1}_{\{X_n=i\}}$ counts the visits to $i$ in one excursion from the reference $k$, with $\mathbb{E}[W_1]={\gamma }_i^k=m_k{\pi }_i$, while $\mathbb{E}[L_1]=m_k$. The SLLN-ratio gives $V_i(n)/n=\frac{1}{n}{S}_n(1_{\{i\}})\to \mathbb{E}[W_1]/\mathbb{E}[L_1]={\pi }_i$. Taking $k=i$ specialises to ${\pi }_i=1/m_i$, recovering the Kac identity of 37.05.05 as the long-run visit frequency. $\square$

Proposition 6 (the directed cycle is stationary but not reversible). The chain on $\{1,2,3\}$ with $p_{12}=p_{23}=p_{31}=1$ has stationary $\pi =(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ but admits no distribution in detailed balance with $P$.

Proof. Stationarity: $(\pi P{)}_1={\sum }_i{\pi }_i{p}_{i1}={\pi }_3{p}_{31}=\frac{1}{3}={\pi }_1$, and symmetrically for the other coordinates, so $\pi P=\pi$. For detailed balance, any $\nu$ would need ${\nu }_1{p}_{12}={\nu }_2{p}_{21}$; but $p_{12}=1$ and $p_{21}=0$, forcing ${\nu }_1=0$, and cyclically ${\nu }_2={\nu }_3=0$. The only solution is $\nu \equiv 0$, so no nonzero reversible measure exists; the chain runs strictly forward and its reversal is the opposite cycle, a different matrix. $\square$

Connections Master

• Invariant measures and positive/null recurrence 37.05.05 supplies the equilibrium $\pi$ and the mean return time $m_i$ that the ergodic theorem averages onto: the excursion measure ${\gamma }^k=m_k\pi$ constructed there is exactly the expected excursion reward in the renewal-reward decomposition here, and the Kac identity ${\pi }_i=1/m_i$ is the ergodic theorem evaluated at the indicator $f=1_{\{i\}}$, so that unit's static equilibrium becomes this unit's dynamic time-average.

• The strong law of large numbers 37.02.02 is the analytic engine: the i.i.d. excursion sums $W_r$ and lengths $L_r$ produced by the strong Markov restart are summed by the SLLN, and the ratio of the two limits is the whole content of the Markov ergodic theorem, so the classical law of large numbers for independent summands lifts, through regeneration, to dependent chains.

• Convergence to equilibrium via coupling 37.05.06 is the distributional twin: that unit proves $p_{ij}^{(n)}\to {\pi }_j$ (an ensemble statement requiring aperiodicity), while this unit proves the pathwise $\frac{1}{n}{\sum }_{k<n}{1}_{\{X_k=j\}}\to {\pi }_j$ (a time-average holding even with periodicity), and the spectral gap of a reversible chain bounds the coupling-time tail that controls the former.

• The strong Markov property and recurrence/transience dichotomy 37.05.04 licenses the excursion decomposition by restarting the chain at each visit to the reference state, the same stopping-time machinery that there established the visit-with-certainty of a recurrent class; without it the path could not be cut into independent identically distributed blocks.

Historical & philosophical context Master

The pointwise ergodic theorem in its general measure-preserving form is due to George Birkhoff in 1931, who proved that time-averages of an integrable observable along the orbits of a measure-preserving transformation converge almost everywhere; the mean-square version is John von Neumann's, proved slightly earlier in 1931 and published in 1932. For Markov chains the specialisation — that the long-run fraction of time in a state equals its stationary mass, and more generally that empirical averages converge to stationary expectations — was developed through the renewal-theoretic and excursion viewpoint codified in the textbook tradition, presented cleanly by Norris ^{[Norris 1997]} from the regeneration structure of returns to a fixed state. The general-state-space law of large numbers, run off a small set rather than a single recurrent point, is the Harris-chain theory of Meyn and Tweedie.

Reversibility and the detailed-balance condition entered probability from statistical physics, where microscopic reversibility — the time-symmetry of equilibrium fluctuations — is a foundational principle; Lars Onsager's reciprocal relations are its macroscopic shadow. The algorithmic exploitation of detailed balance is the Markov chain Monte Carlo method, initiated by Nicholas Metropolis and collaborators in 1953 ^{[Metropolis 1953]} for simulating equilibrium configurations of interacting particles, where the acceptance rule $\min (1,{\pi }_j/{\pi }_i)$ was introduced to drive a chain to a prescribed Boltzmann distribution. W. K. Hastings generalised the construction in 1970 ^{[Hastings 1970]} to arbitrary proposal kernels by inserting the correction ratio $q_{ji}/q_{ij}$, giving the Metropolis-Hastings algorithm now standard across Bayesian statistics and computational physics, with the systematic statistical development given by Robert and Casella ^{[Robert-Casella 2004]}.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{Birkhoff1931,
  author  = {Birkhoff, George D.},
  title   = {Proof of the ergodic theorem},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {17},
  number  = {12},
  year    = {1931},
  pages   = {656--660}
}

@article{Metropolis1953,
  author  = {Metropolis, Nicholas and Rosenbluth, Arianna W. and Rosenbluth, Marshall N. and Teller, Augusta H. and Teller, Edward},
  title   = {Equation of state calculations by fast computing machines},
  journal = {Journal of Chemical Physics},
  volume  = {21},
  number  = {6},
  year    = {1953},
  pages   = {1087--1092}
}

@article{Hastings1970,
  author  = {Hastings, W. Keith},
  title   = {Monte Carlo sampling methods using Markov chains and their applications},
  journal = {Biometrika},
  volume  = {57},
  number  = {1},
  year    = {1970},
  pages   = {97--109}
}

@book{RobertCasella2004,
  author    = {Robert, Christian P. and Casella, George},
  title     = {Monte Carlo Statistical Methods},
  edition   = {2},
  publisher = {Springer},
  year      = {2004}
}

@book{LevinPeres2017,
  author    = {Levin, David A. and Peres, Yuval},
  title     = {Markov Chains and Mixing Times},
  edition   = {2},
  publisher = {American Mathematical Society},
  year      = {2017}
}