Ergodic Limits in Chains with Multiple Closed Classes

Why Multiple Closed Classes Change the Limit

In a finite Markov chain with one irreducible class, long-run averages are governed by that class's stationary distribution. With several closed classes, the chain does not move between them. Its initial state can therefore affect which stationary average eventually applies. If the initial state is transient, the chain first spends a finite random amount of time outside the closed classes, then enters one of them and stays there. The class selected is random, so a long-run average can have a random limit.

Throughout, let $(X_n)_{n\ge0}$ be a Markov chain on a finite state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with row-stochastic transition matrix $P=(p_{ij})$. Use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. States $i$ and $j$ communicate if each is reachable from the other along transitions of positive probability. A communicating class $C$ is closed if $p_{ij}=0$ whenever $i\in C$ and $j\notin C$. In a finite chain, every state outside the closed communicating classes is transient; denote their set by $T$.

Definition: Label the closed communicating classes $C_1,\ldots,C_m$. The class-selection event $H_r$ is the event that the chain eventually enters $C_r$. Since $C_r$ is closed, after entering it the chain stays there. For an initial state $i$, write $\alpha_{ir}=\mathbb{P}_i(H_r)$. These probabilities describe which class is selected, not the distribution of $X_n$ at a particular time.

For a real-valued state reward $g:S\to\mathbb{R}$, the empirical reward through time $n-1$ is $A_n(g)=\frac1n\sum_{k=0}^{n-1}g(X_k)$. Each finite irreducible class $C_r$ has a unique stationary distribution $\pi^{(r)}$, supported on $C_r$. The finite irreducible Markov chain ergodic theorem, established in the earlier material on the Markov chain ergodic theorem, says that for any starting state in $C_r$, $A_n(g)$ converges almost surely to $\sum_{j\in C_r}\pi^{(r)}_j g(j)$. This time-average result requires irreducibility and positive recurrence; finite irreducible chains are positive recurrent. It does not require aperiodicity.

Class Selection and Long-Run Averages

Theorem: For a finite Markov chain, the chain enters one of its closed communicating classes in finite time almost surely. For every bounded reward $g:S\to\mathbb{R}$, under $\mathbb{P}_i$, $$ A_n(g)\longrightarrow \sum_{j\in C_r}\pi^{(r)}_j g(j) \quad\text{almost surely on }H_r,\qquad r=1,\ldots,m. $$ In particular, every transient state has limiting empirical frequency zero. The limit is the stationary mean of the class selected by the path, and need not be the same for different classes.

Proof. First show that entry into the union $C_1\cup\cdots\cup C_m$ occurs almost surely. In the finite directed graph of positive-probability transitions, every state can reach a closed communicating class: collapse each communicating class to a vertex; the resulting finite directed graph has no directed cycles, and following outgoing edges must eventually reach a vertex with no outgoing edge. Such a vertex represents a closed class. Thus, from each $i\in T$, there is a finite path to the union of closed classes whose probability is positive. Because $T$ is finite, there are an integer $N\ge1$ and a number $\delta>0$ such that, from every transient state, the probability of entering the union within $N$ steps is at least $\delta$. (If $T$ is empty, entry has already occurred.) Conditional on still being in $T$ after $kN$ steps, the Markov property gives probability at most $1-\delta$ of avoiding the union for the next $N$ steps. Hence the probability of still avoiding it after $kN$ steps is at most $(1-\delta)^k$, which tends to zero. Entry therefore occurs at a finite time almost surely.

Let $\tau=\inf\{n\ge0:X_n\in C_1\cup\cdots\cup C_m\}$. On the event $H_r$, $X_\tau\in C_r$, and all later states remain in $C_r$. By the Markov property at the finite stopping time $\tau$, conditional on the history through $\tau$, the future chain has the transition law of a chain started at $X_\tau$. The finite irreducible chain ergodic theorem therefore gives the asserted almost-sure limit for the average from time $\tau$ onward. To include the initial segment, set $M=\max_{i\in S}|g(i)|<\infty$. For $n>\tau$, its contribution has absolute value at most $M\tau/n$, which tends to zero. Also, replacing the denominator $n-\tau$ of the post-$\tau$ average by $n$ does not change its limit, since $\tau$ is finite. This proves the reward limit on each $H_r$. Taking $g=\mathbf{1}_{\{i\}}$ for a transient state $i$, its stationary mean in every closed class is zero, proving the frequency statement. $\square$

The selection probabilities can be computed separately from the class-specific stationary averages. For a fixed $r$, the function $i\mapsto\alpha_{ir}$ equals $1$ on $C_r$, equals $0$ on every other closed class, and satisfies the first-step equations $$ \alpha_{ir}=\sum_{j\in S}p_{ij}\alpha_{jr},\qquad i\in T. $$ The equation follows by conditioning on $X_1$: after the first step to $j$, the probability of eventual entry into $C_r$ is $\alpha_{jr}$. These equations have at most one solution with the stated boundary values. Indeed, the difference $d_i$ of two solutions is zero on closed classes and satisfies $d_i=\sum_jp_{ij}d_j$ on $T$. Iterating $N$ steps gives $|d_i|\le (1-\delta)\max_{j\in T}|d_j|$, using the uniform probability $\delta$ of leaving $T$ within $N$ steps. Taking the maximum over $i\in T$ forces that maximum to be zero. The actual probabilities $\alpha_{ir}$ provide a solution, so the equations identify them uniquely.

Worked Example: One Transient State and Two Closed Classes

Consider $S=\{0,1,2,3\}$ and $$ P= \begin{bmatrix} 0&\tfrac13&\tfrac23&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{bmatrix}. $$ Every row sums to $1$: the row sums are $\tfrac13+\tfrac23=1$, $1$, $1$, and $1$. The closed classes are $C_1=\{1\}$ and $C_2=\{2,3\}$; state $0$ is transient.

Starting from $0$, the first step enters $C_1$ with probability $\tfrac13$ and $C_2$ with probability $\tfrac23$. The stationary distribution on $C_1$ assigns mass $1$ to state $1$. On $C_2$, the chain alternates between states $2$ and $3$; solving $\pi_2=\pi_3$ and $\pi_2+\pi_3=1$ gives $\pi^{(2)}=(\tfrac12,\tfrac12)$.

Take $g(1)=6$, $g(2)=2$, $g(3)=0$, and $g(0)=0$. The stationary reward means are $6$ in $C_1$ and $\tfrac12(2)+\tfrac12(0)=1$ in $C_2$. Thus the time average converges almost surely to $6$ with probability $\tfrac13$, and to $1$ with probability $\tfrac23$. The expected limiting value is $\tfrac13(6)+\tfrac23(1)=\tfrac83$; that expectation is not the pathwise limit on either event.

Check: The class-selection probabilities sum to $\tfrac13+\tfrac23=1$. The class-specific stationary distributions each sum to $1$, and direct multiplication gives $(\tfrac12,\tfrac12)\begin{bmatrix}0&1\\1&0\end{bmatrix}=(\tfrac12,\tfrac12)$.

Worked Example: Solving Selection Probabilities from Two Transient States

Let $S=\{1,2,3,4\}$, where $3$ and $4$ are absorbing, and let $$ P= \begin{bmatrix} 0&\tfrac12&\tfrac12&0\\ \tfrac14&0&\tfrac14&\tfrac12\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are respectively $\tfrac12+\tfrac12=1$, $\tfrac14+\tfrac14+\tfrac12=1$, $1$, and $1$. The closed classes are $\{3\}$ and $\{4\}$; states $1$ and $2$ are transient.

Let $h_i$ be the probability of eventual entry into $\{3\}$ from state $i$. The boundary values are $h_3=1$, $h_4=0$. Conditioning on the first step gives $$ h_1=\tfrac12h_2+\tfrac12,\qquad h_2=\tfrac14h_1+\tfrac14. $$ Substitute the second equation into the first: $h_1=\tfrac12(\tfrac14h_1+\tfrac14)+\tfrac12=\tfrac18h_1+\tfrac58$. Therefore $\tfrac78h_1=\tfrac58$, so $h_1=\tfrac57$. Then $h_2=\tfrac14(\tfrac57)+\tfrac14=\tfrac5{28}+\tfrac7{28}=\tfrac37$. The probabilities of entering $\{4\}$ are the complements, $\tfrac27$ from state $1$ and $\tfrac47$ from state $2$.

Check: Substitution gives $\tfrac12(\tfrac37)+\tfrac12=\tfrac3{14}+\tfrac7{14}=\tfrac57=h_1$, and $\tfrac14(\tfrac57)+\tfrac14=\tfrac5{28}+\tfrac7{28}=\tfrac37=h_2$. For each starting state, the two class-selection probabilities sum to $1$.

Worked Example: A Nontrivial Class-Specific Reward Average

Consider four states $0,1,2,3$. From state $0$, the chain moves to state $1$ or state $3$, each with probability $\tfrac12$. Within $\{1,2\}$, the transition rows are $(\tfrac34,\tfrac14)$ and $(\tfrac12,\tfrac12)$; state $3$ is absorbing. In the order $0,1,2,3$, the full matrix is $$ P= \begin{bmatrix} 0&\tfrac12&0&\tfrac12\\ 0&\tfrac34&\tfrac14&0\\ 0&\tfrac12&\tfrac12&0\\ 0&0&0&1 \end{bmatrix}. $$ Its row sums are $\tfrac12+\tfrac12=1$, $\tfrac34+\tfrac14=1$, $\tfrac12+\tfrac12=1$, and $1$. The closed classes are $\{1,2\}$ and $\{3\}$; state $0$ is transient.

For the stationary distribution $(\pi_1,\pi_2)$ on $\{1,2\}$, the first-coordinate equation is $\pi_1=\tfrac34\pi_1+\tfrac12\pi_2$, so $\tfrac14\pi_1=\tfrac12\pi_2$, or $\pi_1=2\pi_2$. Normalization gives $\pi_2=\tfrac13$, $\pi_1=\tfrac23$. With rewards $g(1)=2$, $g(2)=-1$, and $g(3)=7$, the class means are $\tfrac23(2)+\tfrac13(-1)=1$ and $7$. From state $0$, each class is selected with probability $\tfrac12$. Thus the average converges almost surely to $1$ or $7$, each with probability $\tfrac12$, and its expected limiting value is $\tfrac12(1)+\tfrac12(7)=4$.

Check: The stationary vector satisfies $(\tfrac23,\tfrac13)\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac12&\tfrac12\end{bmatrix}=(\tfrac23,\tfrac13)$, and its entries sum to $1$. The expected limit $4$ is the average of the two possible class means, not a value attained by either pathwise limit.

What the Limits Do—and Do Not—Say

For an initial distribution $\mu$, the probability of selecting class $C_r$ is $\sum_{i\in S}\mu_i\alpha_{ir}$. Consequently, for bounded $g$, the expectation of the limiting time average is $$ \sum_{r=1}^m\left(\sum_{i\in S}\mu_i\alpha_{ir}\right) \left(\sum_{j\in C_r}\pi^{(r)}_j g(j)\right). $$ Because the averages are bounded by $\max_i|g(i)|$, bounded convergence also shows that this is the limit of their expectations. The pathwise statement is stronger in a different direction: it identifies the random class-specific limit, rather than only its expectation.

Periodicity within a closed class does not invalidate the time-average conclusion. For example, the chain on $\{2,3\}$ in the first example has period $2$, so its one-time distribution can alternate, while its empirical state frequencies converge to $(\tfrac12,\tfrac12)$. The ergodic limit concerns averages along a path; aperiodicity is not needed for that result.

Common mistake. It is incorrect to report the weighted mean of the class-specific averages as the almost-sure limit. In the last example, calculating $\tfrac12(1)+\tfrac12(7)=4$ and declaring that the pathwise average converges to $4$ confuses an expectation with a random limit. The correction is to state the two outcomes: the average converges to $1$ on the event of entering $\{1,2\}$, and to $7$ on the event of entering $\{3\}$. Only after that may one take the expectation, which is $4$.

Check Your Understanding

Use the class-selection probabilities and class-specific averages separately when answering.

Why does a finite chain enter a closed communicating class almost surely?
In the first worked example, what is the probability, starting from $0$, that the limiting average of $g$ is $1$?
For the second example, verify from the first-step equations that the probability of entering $\{4\}$ from state $2$ is $\tfrac47$.
Why does a period-$2$ closed class still have convergent empirical state frequencies?
In the last example, what are the possible pathwise limits, and what is the expected limiting value from state $0$?

Ergodic Limits in Chains with Multiple Closed Classes

What You'll Learn