Periodicity as an Obstruction to Convergence

Stationarity Does Not Guarantee Convergence

A Markov chain can have a stationary distribution and still fail to approach it at each successive time. The obstruction is periodicity: transitions move the chain through a sequence of classes in a fixed cyclic order. At any given time, a chain started at one state is confined to just one of those classes, while a stationary distribution spreads its mass across all of them. This difference remains visible in total variation, no matter how many steps have elapsed.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The matrix is row-stochastic: \(\sum_{j\in S}p_{ij}=1\) for every \(i\). The chain is irreducible if each state can be reached from each other state with positive probability in some finite number of steps. Its period is the greatest common divisor of the positive return times \(n\) for which \(p_{ii}^{(n)}>0\); for an irreducible chain this value is the same for every state. A chain is periodic when this period \(d\) exceeds \(1\).

The last property is not a convergence statement. It says what happens when the chain is already started in equilibrium. The question here is whether a chain started at a particular state approaches equilibrium in total variation. For an irreducible periodic chain, the answer is no.

Cyclic Classes

Fix a reference state \(o\). A path of length \(m\) from \(o\) to \(j\) means a sequence of \(m\) transitions, each having positive probability. Assign \(j\) the residue modulo \(d\) of the length of any such path. This assignment is well-defined: if two paths from \(o\) to \(j\) have lengths \(m\) and \(n\), append the same path from \(j\) back to \(o\). The resulting lengths are return times to \(o\), so both are divisible by \(d\), and therefore \(m-n\) is divisible by \(d\). For \(j=o\), assign residue \(0\), since every positive return time to \(o\) is divisible by \(d\).

Write \(C_r\) for the set of states assigned residue \(r\), where residues are taken modulo \(d\). These sets are the cyclic classes. An edge of positive probability from \(i\) to \(j\) increases path length by one, so it moves from \(C_r\) to \(C_{r+1}\). All \(d\) classes are nonempty: take any positive-probability return path from \(o\) to itself, of length \(L\). Since \(L\) is a positive multiple of \(d\), its first \(d\) vertices have path lengths \(0,\ldots,d-1\) and belong to the corresponding classes.

Proof. The path construction above gives the partition into nonempty classes and shows that transitions from \(C_r\) go only to \(C_{r+1}\). Write \(\pi(C_r)=\sum_{i\in C_r}\pi_i\). Stationarity and the transition property give \(\pi(C_{r+1})=\sum_{j\in C_{r+1}}\sum_{i\in S}\pi_i p_{ij}=\sum_{i\in C_r}\pi_i\sum_{j\in C_{r+1}}p_{ij}=\pi(C_r)\). The middle equality holds because states outside \(C_r\) have no transitions into \(C_{r+1}\), and for each \(i\in C_r\) the sum of probabilities into \(C_{r+1}\) is \(1\). Thus all class masses are equal. Since the classes partition \(S\) and \(\pi(S)=1\), each has mass \(1/d\).

Now fix any starting state \(j\in C_s\), not just the reference state. By induction on \(n\), the transition property implies \(\mathbb{P}_j(X_n\in C_{s+n\bmod d})=1\): it holds at \(n=0\), and one more transition moves the occupied class forward by one. Set \(A=C_{s+n\bmod d}\). The law at time \(n\) assigns mass \(1\) to \(A\), while \(\pi(A)=1/d\). The supremum definition of total variation therefore gives \(\|\mathbb{P}_j(X_n\in\cdot)-\pi\|_{\mathrm{TV}}\ge|1-1/d|=1-1/d\), for every \(j\) and \(n\). Finally, for a fixed start \(j\in C_s\), the probability of \(C_s\) equals \(1\) at times \(n=kd\) and \(0\) at times \(n=kd+1\), for integers \(k\ge0\). If the laws converged in total variation, their probabilities of the fixed set \(C_s\) would converge, which these alternating values do not. \(\square\)

The lower bound has an important scope: it compares the law from a fixed state with the stationary distribution. It does not say that every initial distribution fails to converge. If the initial distribution is already \(\pi\), stationarity gives \(\mu_n=\pi\) for all \(n\). The obstruction concerns the persistent phase information carried by a particular starting class.

Worked Examples

What the Obstruction Does—and Does Not—Say

The class argument explains why stationary probabilities and convergence answer different questions. Stationarity is the balance equation \(\pi P=\pi\); it says that one step preserves a distribution. Convergence asks whether repeated transitions from a specified initial law approach a particular distribution. A stationary distribution may exist even when the latter fails. In a periodic chain, each step shifts the class occupied by a point-started chain, so the phase does not disappear.

The result is specifically a total-variation obstruction. It gives a uniform positive lower bound at every time, and therefore rules out total-variation convergence to \(\pi\). It also rules out a total-variation limit of any kind for a fixed point start: probabilities of a cyclic class oscillate between \(1\) and \(0\) along two subsequences. This argument does not rule out convergence of time averages, which average over different phases; that is a distinct question.

Common pitfall. For the two-state chain, it is tempting to say that the laws “average out” to \((1/2,1/2)\), and therefore converge to \(\pi\). The arithmetic average of the first \(2m\) laws is indeed \((1/2,1/2)\), but the law at time \(n\) is still either \((1,0)\) or \((0,1)\). Its distance from \(\pi\) is \(\tfrac12\), not \(0\). Averaging a sequence of distributions is not the same operation as taking the limit of its individual terms.

When checking a proposed convergence claim for an irreducible chain, first identify the period. If \(d>1\), find its cyclic classes and track which class contains the chain at time \(n\). For a point start, that class has probability \(1\), while its stationary mass is \(1/d\); this single event already gives the lower bound \(1-1/d\). Aperiodicity removes this particular obstruction, but does not by itself establish convergence without the other hypotheses needed for a convergence theorem.