Two Different Limits
A Markov chain can be studied at a fixed late time or over a long stretch of one realized path. These questions sound similar but ask about different objects. The first concerns the distribution of \(X_n\) as \(n\) grows; the second concerns the average of values \(f(X_0),\ldots,f(X_{N-1})\) along a sample path. Confusing them can turn a correct statement about expected averages into an unjustified claim about almost every trajectory.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\) whose rows sum to \(1\). Write \(\mu_n\) for the row-vector distribution of \(X_n\); thus \(\mu_{n+1}=\mu_nP\). For a bounded function \(f:S\to\mathbb{R}\), define its empirical time average by
Convergence of the one-time distributions means that \(\mu_n\) converges to a probability distribution \(\pi\). On a finite state space, this is equivalent to convergence in total variation. Almost-sure convergence of the time averages means that \(A_N(f)\) converges for all paths except an event of probability zero. The first limit is a sequence of deterministic probability distributions; the second is a sequence of random variables and may have a random limit.
These distinctions give two useful checks. First, if a distributional limit exists for a finite-state chain with fixed transition matrix, it must be stationary. Second, convergence of the one-time distributions does imply convergence of expected time averages for bounded \(f\), but that expectation statement alone does not imply convergence of the random path averages.
What Marginal Convergence Does Imply
Proof. Put \(b_n=\mathbb{E}[f(X_n)]=\sum_{i\in S}\mu_n(i)f(i)\) and \(b=\sum_{i\in S}\pi(i)f(i)\). Since \(S\) is finite and each \(\mu_n(i)\to\pi(i)\), the finite sum gives \(b_n\to b\). Also, linearity of expectation gives \(\mathbb{E}[A_N(f)]=N^{-1}\sum_{n=0}^{N-1}b_n\). To show these averages tend to \(b\), fix \(\varepsilon>0\) and choose \(n_0\) so that \(|b_n-b|<\varepsilon\) for \(n\ge n_0\). The finite initial sum \(C=\sum_{n=0}^{n_0-1}|b_n-b|\) does not depend on \(N\). For \(N>n_0\), the difference between the average and \(b\) is at most \(C/N+\varepsilon(N-n_0)/N\), which is at most \(C/N+\varepsilon\). Taking \(N\to\infty\), then allowing \(\varepsilon\) to decrease to zero, proves the claimed limit. For stationarity, take coordinate \(j\) in \(\mu_{n+1}=\mu_nP\). The finite sum \(\mu_{n+1}(j)=\sum_{i\in S}\mu_n(i)p_{ij}\) converges to \(\sum_{i\in S}\pi(i)p_{ij}\). But \(\mu_{n+1}(j)\to\pi(j)\) as well. Thus \(\pi(j)=\sum_i\pi(i)p_{ij}\) for every \(j\), so \(\pi P=\pi\). \(\square\)
The proposition concerns an expectation, not an almost-sure limit. To see the difference, note that \(\mathbb{E}[A_N(f)]\to c\) does not, by itself, imply that \(A_N(f)\to c\) almost surely—or even in probability. The chain’s structure matters.
Worked Example: A Periodic Chain Whose Averages Converge
On \(S=\{0,1\}\), let \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), and start at \(X_0=0\). Each row sums to \(0+1=1\) or \(1+0=1\), so this is a transition matrix. The chain switches state at every step: \(X_n=0\) for even \(n\) and \(X_n=1\) for odd \(n\).
For \(f(i)=\mathbf{1}_{\{0\}}(i)\), the one-time law does not converge: at every even \(n\), \(\mathbb{P}(X_n=0)=1\), and at every odd \(n\), \(\mathbb{P}(X_n=0)=0\). Yet along the path, among the \(N\) indices \(0,\ldots,N-1\), the number of even indices is \(\lceil N/2\rceil\). Therefore \(A_N(f)=\lceil N/2\rceil/N\), which tends to \(1/2\).
Check: The candidate stationary distribution is \(\pi=(1/2,1/2)\), since \((1/2,1/2)P=(1/2,1/2)\). The path average tends to \(\sum_i\pi(i)f(i)=1/2\), even though the one-time laws oscillate instead of converging. Thus convergence of path averages does not require convergence of the one-time distributions.
The chain is periodic: its states alternate between two classes at successive times. Its stationary distribution describes balance across the two states, but from the specified initial state it does not describe the distribution at each late time. Averaging over many successive times removes the alternation in this example; it does not make the individual-time laws converge.
When Marginals Converge but Path Averages Stay Random
Worked Example: Convergence to a Random Absorbing Class
Let \(S=\{0,1,2\}\), with transition matrix
The row sums are \(0+\tfrac12+\tfrac12=1\), \(0+1+0=1\), and \(0+0+1=1\). Start from \(X_0=0\). After one step the chain enters state \(1\) or \(2\), each with probability \(1/2\), and then stays there forever. Hence, for every \(n\ge1\), \(\mu_n=(0,1/2,1/2)\). This is a limiting distribution and is stationary: multiplying it by \(P\) gives \((0,1/2,1/2)\).
Take \(f(i)=\mathbf{1}_{\{1\}}(i)\). If the first transition is to \(1\), then \(A_N(f)=(N-1)/N\), because the initial state contributes zero and each of the remaining \(N-1\) terms contributes one. If the first transition is to \(2\), then \(A_N(f)=0\). Thus the almost-sure limit is \(1\) with probability \(1/2\) and \(0\) with probability \(1/2\); it is not the constant \(\sum_i\pi(i)f(i)=1/2\).
Check: The expectation is \(\mathbb{E}[A_N(f)]=\tfrac12(N-1)/N+\tfrac12(0)=(N-1)/(2N)\), which tends to \(1/2\), as the proposition predicts. But for every \(N\ge5\), either possible value of \(A_N(f)\) is more than \(1/4\) from \(1/2\): the value \(0\) is \(1/2\) away, and \((N-1)/N\) is \(1/2-1/N>1/4\) away. Therefore \(\mathbb{P}(|A_N(f)-1/2|>1/4)=1\) for \(N\ge5\). The averages do not converge in probability to \(1/2\).
This is a reducible chain: once it enters either absorbing state, it cannot reach the other. The limiting distribution averages over which class is selected; a single path selects only one class. The finite-state Markov chain ergodic theorem, established in the earlier material on ergodic limits, gives almost-sure reward averages under its stated irreducibility and recurrence hypotheses. Those hypotheses cannot simply be omitted: this example has convergent marginals but a random path-average limit.
When Both Limits Agree
Worked Example: An Aperiodic Irreducible Chain
On \(S=\{0,1\}\), take
The row sums are \(\tfrac34+\tfrac14=1\) and \(\tfrac12+\tfrac12=1\). Every transition has positive probability, so the chain is irreducible; the positive self-transition probabilities also make its period \(1\). Solve for a stationary distribution \(\pi=(\pi_0,\pi_1)\). The equation for state \(0\) is \(\pi_0=\tfrac34\pi_0+\tfrac12\pi_1\), or \(\tfrac14\pi_0=\tfrac12\pi_1\), so \(\pi_0=2\pi_1\). Together with \(\pi_0+\pi_1=1\), this gives \(\pi=(2/3,1/3)\).
Check: The state-\(0\) coordinate of \(\pi P\) is \((2/3)(3/4)+(1/3)(1/2)=1/2+1/6=2/3\). The state-\(1\) coordinate is \((2/3)(1/4)+(1/3)(1/2)=1/6+1/6=1/3\). Thus \(\pi P=\pi\), and the entries sum to \(2/3+1/3=1\).
Starting at state \(0\), let \(x_n=\mathbb{P}(X_n=0)\). One transition gives \(x_{n+1}=\tfrac34x_n+\tfrac12(1-x_n)=\tfrac12+\tfrac14x_n\). Subtracting \(2/3\) from both sides yields \(x_{n+1}-2/3=\tfrac14(x_n-2/3)\). Since \(x_0=1\), iteration gives \(x_n=2/3+(1/3)(1/4)^n\), which tends to \(2/3\); the probability of state \(1\) therefore tends to \(1/3\).
For \(f(i)=\mathbf{1}_{\{0\}}(i)\), the same marginal calculation and the proposition show \(\mathbb{E}[A_N(f)]\to2/3\). Moreover, the standard finite-state Markov chain ergodic theorem applies: the chain is irreducible on a finite state space, hence positive recurrent, and the theorem gives \(A_N(f)\to\sum_i\pi(i)f(i)=2/3\) almost surely. Aperiodicity is needed for the marginal convergence conclusion in this comparison, not for the path-average conclusion of that ergodic theorem.
A Diagnostic Checklist
When a problem gives a limiting distribution or a long-run average, first identify which quantity is being discussed. A claim about \(\mathbb{P}(X_n=i)\) is a marginal statement; a claim about \(N^{-1}\sum_{n<N}f(X_n)\) is a path statement. Then check the chain’s structure. Periodicity may obstruct marginal convergence without obstructing time averages. Reducibility may allow marginals to converge to a mixture while different paths have different long-run averages. For a finite irreducible aperiodic chain, the two quantities are linked through the stationary distribution, but they remain different limits.
Common mistake. In the reducible example, one might say: “The distribution converges to \(\pi=(0,1/2,1/2)\), so the time average of \(\mathbf{1}_{\{1\}}\) converges almost surely to \(\pi(1)=1/2\).” This incorrectly replaces a random path average with its limiting expectation. The direct calculation shows that the path average tends to \(1\) or \(0\), each with probability \(1/2\). Its expectation tends to \(1/2\), but the path limit is not \(1/2\). In the periodic example, the reverse confusion is also possible: failure of marginal convergence does not rule out convergence of path averages.
| Question | Object | What the examples show |
|---|---|---|
| What is the law of \(X_n\) at a late time? | \(\mu_n\) | It can oscillate in a periodic chain or converge in an aperiodic one. |
| What is the average along one path? | \(A_N(f)\) | It can converge despite oscillating marginals, or converge to a random value in a reducible chain. |
| What does marginal convergence imply for bounded \(f\)? | \(\mathbb{E}[A_N(f)]\) | It converges to \(\sum_i\pi(i)f(i)\); this alone is not an almost-sure limit claim. |
Check Your Understanding
For each question, identify whether it concerns one-time distributions, expected averages, or pathwise averages.
- In the two-state alternating chain, what is the limiting value of \(A_N(\mathbf{1}_{\{1\}})\), and does the distribution of \(X_n\) converge?
- In the absorbing-class example, give the two possible almost-sure limits of \(A_N(\mathbf{1}_{\{1\}})\) and their probabilities.
- Why does convergence of \(\mathbb{E}[A_N(f)]\) not by itself establish convergence in probability of \(A_N(f)\)?
- If \(\mu_n\to\pi\) in a finite-state chain with fixed transition matrix, what equation must \(\pi\) satisfy? Give the coordinate argument.
- For the aperiodic two-state example, compute the limiting expected average of \(\mathbf{1}_{\{0\}}\) from the stationary distribution.