Counting Visits Along a Sample Path
A transition matrix describes probabilities of moving between states, but a recorded trajectory gives counts: how often did the chain visit each state during the observation period? Dividing those counts by the number of observations produces empirical state frequencies. The ergodic theorem explains why, under suitable conditions, these random quantities settle to fixed long-run proportions. It does not say that a short record must closely match those proportions: initial conditions and dependence between successive states can matter substantially at finite observation lengths.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge 0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), with transition matrix \(P=(p_{ij})\). The natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). For a state \(i\in S\) and an integer \(N\ge 1\), define the empirical frequency of \(i\) in the first \(N\) observations by
The observation convention here includes \(X_0\) and excludes \(X_N\), so the window contains exactly \(N\) states. The indicator is \(1\) when the chain is at \(i\) and \(0\) otherwise. Thus \(N\widehat{\pi}_N(i)\) is an integer between \(0\) and \(N\). For any finite set of states \(S\), the frequencies add to one, because exactly one state is occupied at each observation time.
For a finite irreducible chain, positive recurrence and the existence of a unique stationary distribution are automatic. The theorem concerns time averages along a path, not convergence of the one-time distribution of \(X_n\). Aperiodicity is needed for the usual convergence of one-time distributions from arbitrary initial states, but not for empirical state frequencies. Keeping those conclusions separate is essential.
Finite-Window Identities
Before taking a long-run limit, it helps to know what a finite observation window measures on average. Write \(\mu\) for the initial distribution as a row vector, so the distribution of \(X_n\) is \(\mu P^n\). The following identity is useful both for calculation and for seeing the effect of the starting distribution.
Proof. By the definition of the indicator, \(\mathbb{E}[\mathbf{1}_{\{X_n=i\}}]=\mathbb{P}(X_n=i)=(\mu P^n)_i\). Linearity of expectation applied to the finite sum gives the stated formula after division by \(N\). If \(\mu=\pi\) and \(\pi P=\pi\), repeated multiplication gives \(\pi P^n=\pi\) for every \(n\ge0\). Each summand is then \(\pi_i\), so their average is \(\pi_i\). \(\square\)
Unbiasedness under a stationary start says nothing by itself about the size of the random error in one realized window. Successive indicators can be correlated. The next identity makes that dependence explicit when the chain starts in stationarity.
Proof. Expand the variance of the sum: \(\operatorname{Var}(\sum_{n=0}^{N-1}Y_n)=\sum_{r=0}^{N-1}\sum_{s=0}^{N-1}\operatorname{Cov}(Y_r,Y_s)\). Stationarity implies that for \(s\ge r\), \(\operatorname{Cov}(Y_r,Y_s)=\gamma_{s-r}\). Covariance is symmetric, so the terms with \(r>s\) match those with \(s>r\). There are \(N\) diagonal terms, each equal to \(\gamma_0\). For each lag \(k\) with \(1\le k\le N-1\), exactly \(N-k\) pairs satisfy \(s-r=k\), and there are equally many in the reverse order. The variance of the sum is therefore \(N\gamma_0+2\sum_{k=1}^{N-1}(N-k)\gamma_k\). Dividing by \(N^2\) proves the identity. \(\square\)
Worked Frequencies and Finite-Window Effects
Worked Example: Counting States in a Recorded Path
Consider a chain on \(S=\{A,B\}\) with transition matrix \(P=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac12&\tfrac12\end{bmatrix}\), in the state order \(A,B\). The first row sums to \(\tfrac34+\tfrac14=1\), and the second to \(\tfrac12+\tfrac12=1\), so this is a transition matrix. Suppose the seven observed states are \(A,B,A,A,B,A,B\). Compute the empirical frequencies.
There are four occurrences of \(A\), at observation indices \(0,2,3,5\), and three occurrences of \(B\), at indices \(1,4,6\). With \(N=7\), the frequencies are
The path is possible: starting at \(A\), its six transitions have probabilities \(\tfrac14,\tfrac12,\tfrac34,\tfrac14,\tfrac12,\tfrac14\). Their product is \(\tfrac{3}{1024}>0\). As a basic check, the observed counts add to \(4+3=7\), and the empirical frequencies add to \(\tfrac47+\tfrac37=1\).
For comparison, the stationary distribution solves \(\pi P=\pi\) and \(\pi_A+\pi_B=1\). The balance equation for \(A\) is \(\pi_A=\tfrac34\pi_A+\tfrac12\pi_B\), so \(\tfrac14\pi_A=\tfrac12\pi_B\), or \(\pi_A=2\pi_B\). Normalization gives \(\pi_A=\tfrac23\) and \(\pi_B=\tfrac13\). Substitution checks both coordinates: \(\tfrac23\cdot\tfrac34+\tfrac13\cdot\tfrac12=\tfrac23\), and \(\tfrac23\cdot\tfrac14+\tfrac13\cdot\tfrac12=\tfrac13\). The observed \(\tfrac47\) is not \(\tfrac23\); the theorem describes the limit as the observation window grows, not an exact rule for each finite path.
Worked Example: Expected Frequency from a Nonstationary Start
Use the same chain, now with \(X_0=A\) with probability \(1\). Calculate the expected frequency of \(A\) over the first three observations, \(X_0,X_1,X_2\). The transition matrix has already been checked to have row sums one.
Starting at \(A\), the probability of being at \(A\) after \(n\) steps is \(\mathbb{P}_A(X_n=A)=\tfrac23+\tfrac13(\tfrac14)^n\). To verify this expression without relying on an uncomputed constant, it equals \(1\) at \(n=0\). If \(a_n=\mathbb{P}_A(X_n=A)\), then \(a_{n+1}=\tfrac34a_n+\tfrac12(1-a_n)=\tfrac12+\tfrac14a_n\). Substituting the proposed expression gives \(a_{n+1}=\tfrac23+\tfrac1{12}(\tfrac14)^n=\tfrac23+\tfrac13(\tfrac14)^{n+1}\), as required.
The three probabilities are \(1\), \(\tfrac34\), and \(\tfrac23+\tfrac1{48}=\tfrac{11}{16}\). Therefore
This is above the stationary value \(\tfrac23\), reflecting the initial state \(A\). Directly, \(\tfrac{13}{16}-\tfrac23=\tfrac7{48}>0\). This expectation is an average over possible paths; it is not the frequency on every three-observation path.
Worked Example: Variability with a Stationary Start
For the same chain, start with \(\pi=(\tfrac23,\tfrac13)\), and find the variance of the empirical frequency of \(A\) for \(N=3\). The rows of \(P\) sum to one as checked above, and \(\pi\) is stationary by the coordinate checks in the first example.
Let \(Y_n=\mathbf{1}_{\{X_n=A\}}\). Then \(\mathbb{E}Y_n=\tfrac23\) and \(\gamma_0=\operatorname{Var}(Y_n)=\tfrac23(1-\tfrac23)=\tfrac29\). Given \(X_0=A\), the probability of \(A\) after \(k\) steps is \(\tfrac23+\tfrac13(\tfrac14)^k\), as verified in the previous calculation. Consequently, \(\mathbb{E}[Y_0Y_k]=\mathbb{P}(X_0=A,X_k=A)=\tfrac23(\tfrac23+\tfrac13(\tfrac14)^k)\). Subtracting \((\mathbb{E}Y_0)(\mathbb{E}Y_k)=\tfrac49\) gives \(\gamma_k=\tfrac29(\tfrac14)^k\). Thus \(\gamma_1=\tfrac1{18}\) and \(\gamma_2=\tfrac1{72}\).
Using the variance identity,
Check the arithmetic inside the parentheses: \(2\cdot\tfrac1{18}+\tfrac1{72}=\tfrac19+\tfrac1{72}=\tfrac9{72}=\tfrac18\), and twice this is \(\tfrac14\). Hence the variance is \(\tfrac{11}{12}\cdot\tfrac19=\tfrac{11}{108}\). The positive lag covariances contribute to the variance; treating the three visits as independent would omit those terms.
Periodicity and Long-Run Frequencies
Worked Example: An Alternating Chain
Let \(S=\{0,1\}\) and \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Each row sums to \(1\). The chain alternates deterministically between the two states, so it is irreducible and has period \(2\). Its stationary distribution is \(\pi=(\tfrac12,\tfrac12)\), since \((\tfrac12,\tfrac12)P=(\tfrac12,\tfrac12)\).
Starting at \(0\), among the first \(N\) observations the number of visits to \(0\) is \(\lceil N/2\rceil\), and the number of visits to \(1\) is \(\lfloor N/2\rfloor\). For even \(N=2m\), both frequencies equal \(\tfrac{m}{2m}=\tfrac12\). For odd \(N=2m+1\), the frequency of \(0\) is \(\tfrac{m+1}{2m+1}\), and its difference from \(\tfrac12\) is \(\tfrac{1}{2(2m+1)}\), which tends to zero; the frequency of \(1\) differs from \(\tfrac12\) by the same amount. The empirical frequencies therefore converge to \(\pi\).
Yet the one-time distribution from \(0\) alternates between probability one on \(0\) and probability one on \(1\), and does not converge. The example shows why aperiodicity is unnecessary for empirical frequencies, while also showing that a finite window can retain a small imbalance when its length is odd.
What the Limit Does—and Does Not—Say
The empirical frequency of state \(i\) is a sample-path quantity. The stationary probability \(\pi_i\) is its almost-sure long-run limit under irreducibility and positive recurrence. By contrast, \(\mathbb{P}(X_n=i)\) is a one-time marginal probability that can oscillate in a periodic chain. The alternating example makes the distinction concrete: its marginal distribution fails to settle, while its time average does.
Finite observation windows can differ from their long-run targets for two reasons. First, a nonstationary starting distribution can shift the expected frequency, as the three-observation calculation showed. Second, even a stationary start does not remove random fluctuation: visits are dependent, and positive covariances can increase the variance of the observed proportion. The ergodic theorem guarantees eventual almost-sure convergence under its hypotheses, but by itself it supplies no numerical error bound for a chosen finite \(N\).
Common mistake. It is incorrect to conclude that a state frequency equals its stationary probability just because the chain has a stationary distribution. For the three-observation nonstationary example, the stationary probability of \(A\) is \(\tfrac23\), while the expected empirical frequency is \(\tfrac{13}{16}\); the calculation gives \(\tfrac{13}{16}-\tfrac23=\tfrac7{48}\), not zero. The correction is to distinguish the finite-window expectation from the almost-sure limit, and to check whether the initial distribution is stationary before asserting finite-window unbiasedness.
Check Your Understanding
Use the convention that a window of length \(N\) observes \(X_0,\ldots,X_{N-1}\).
- A path on \(\{a,b\}\) is \(a,b,b,a,a\). Compute both empirical frequencies and check that they sum to one.
- Why does the empirical-frequency theorem apply to an irreducible positive recurrent periodic chain?
- For a stationary start, why does the expected empirical frequency of state \(i\) equal \(\pi_i\) for every finite \(N\)?
- In the alternating-chain example started at \(0\), compute the frequency of \(0\) when \(N=5\), and compare it with \(\pi_0\).
- In the variance identity, explain why each lag-\(k\) covariance appears \(2(N-k)\) times in the variance of the sum.