Stochastic Processes 6: Long-Run Behavior of Markov Chains

Once you know a Markov chain’s one-step transition rule, the most natural question isn’t “where does it go next” but: if it keeps running indefinitely, what long-run pattern does the system eventually exhibit? This is one of the most important topics in Markov chain theory, and a natural extension of the transition matrix from Stochastic Processes 5: Markov Processes.

1. State Distributions and Stationary Distributions

1.1 How the state distribution evolves over time

Suppose the state space is finite with transition matrix $P$, and the state distribution at time $t$ is written as a row vector $\mu_t$; then the next step satisfies $\mu_{t+1}=\mu_tP$, and after $n$ steps, $\mu_n=\mu_0P^n$. The core question of long-run behavior therefore becomes studying what happens to $P^n$ as $n\to\infty$.

1.2 The stationary distribution: $\pi P=\pi$

If there exists a probability distribution $\pi$ satisfying $\pi P=\pi$, then $\pi$ is called this Markov chain’s stationary distribution: if the system is currently distributed according to $\pi$, then after one more step, the overall probability distribution is still $\pi$. It’s worth noting specifically that a stationary distribution means the probability distribution itself no longer changes — it does not mean every sample path stays put. The concrete state can still keep jumping between different states; it’s just that, viewed as an overall probability distribution, it stays unchanged. Having a stationary distribution doesn’t automatically mean the chain converges to it from any starting state either — that also depends on the state space’s connectivity structure and periodicity, which is exactly what Section 2 addresses.

2. The Structure of the State Space

2.1 Communicating classes and irreducibility

If, starting from state $i$, there’s a positive probability of reaching $j$ after some number of steps, then $i$ can reach $j$; if $i$ can reach $j$ and $j$ can also get back to $i$, the two communicate with each other, and a group of mutually communicating states forms a communicating class. If every state communicates with every other, the whole Markov chain is called irreducible: the state space is connected, with no isolated region that can never be entered or left. For a finite-state Markov chain, irreducibility is a necessary condition for many of the convergence results that follow.

2.2 Periodicity, recurrence, and absorbing states

Consider a deterministic two-state chain $A\to B\to A\to B\to\dots$: starting from A, you can only get back to A on even-numbered steps. This property of “only being able to return on a fixed rhythm” is called periodicity — if the greatest common divisor of all the possible numbers of steps needed to return to a state is greater than 1, that state is called periodic; if the GCD equals 1, it’s called aperiodic. Even if a chain is irreducible, if it oscillates with a strict period, the state distribution may keep swinging between several patterns forever, unable to smoothly converge to a single fixed distribution.

Another question is: once you leave a state, will you ever come back? If, starting from state $i$, the probability of eventually returning to $i$ is 1, $i$ is called recurrent; if there’s a positive probability of leaving and never returning, $i$ is called transient. One- and two-dimensional simple symmetric random walks are recurrent, while three or more dimensions show transience — this will be explained in detail in the later discussion of random walks. If some state satisfies $P(i\to i)=1$, meaning once you enter it you can never leave, it’s called an absorbing state — for example, a gambler’s wealth hitting zero in the Gambler’s Ruin problem is an absorbing state. When there are multiple absorbing states, the usual questions are which state the process ultimately gets absorbed into, the probability of being absorbed into each, and how long on average it takes to be absorbed — these questions naturally connect to hitting time and stopping time.

3. Worked Out: Reusing the Transition Matrix from Stochastic Processes 5

The transition matrix used in the previous article was:

$$P= \begin{bmatrix} 0.7 & 0.2 & 0.1\\ 0.1 & 0.8 & 0.1\\ 0.3 & 0.2 & 0.5 \end{bmatrix}$$

Every state in this chain can reach every other (irreducible), and it has no fixed-rhythm periodic oscillation (aperiodic). Finding the stationary distribution $\pi=(\pi_A,\pi_B,\pi_C)$ means solving the system of equations $\pi P=\pi$, together with $\pi_A+\pi_B+\pi_C=1$. From the first column, $0.3\pi_A=0.1\pi_B+0.3\pi_C$; from the third column, $\pi_C=0.2\pi_A+0.2\pi_B$. Substituting and simplifying these two gives $\pi_B=1.5\pi_A$ and $\pi_C=0.5\pi_A$, and applying the constraint that they sum to 1 gives:

$$\pi=\left(\frac13,\frac12,\frac16\right)\approx(0.333,\,0.5,\,0.167)$$

This can be verified directly: no matter which row you start from, computing $P^n$ for large enough $n$ makes all three rows converge to the same set of numbers. Actually computing $P^{20}$, all three rows come out very close to $(0.333,0.5,0.167)$, matching the solved $\pi$ — this is exactly what the next section explains, that “starting from any initial state, the chain converges to the unique stationary distribution,” with irreducibility and aperiodicity being the key conditions for this conclusion to hold.

4. Convergence and Mixing

4.1 When does it converge to a unique stationary distribution

For a finite-state Markov chain, if it’s both irreducible and aperiodic, there’s generally a unique stationary distribution $\pi$, and starting from any initial distribution $\mu_0$, $\mu_0P^n\to\pi$: as time stretches on, the system gradually “forgets” its initial state — the numerical example in Section 3 is a concrete demonstration of exactly this property.

4.2 Mixing: how many steps are enough to get close

Just knowing “it eventually converges” isn’t enough — in practice, what matters more is: exactly how many steps are needed to get close enough to the stationary distribution? This is the question studied by mixing and mixing time. Two chains might share the same stationary distribution, yet one gets close to stable within a few dozen steps while another might need millions. The stationary distribution answers “where it ends up eventually”; mixing time answers “how long it takes to get close to there.” Good mixing behavior means that $P(X_n\in\cdot\mid X_0=x)$ becomes increasingly independent of the specific initial state $x$ as $n$ grows — and this is precisely the theoretical foundation of MCMC methods: construct a Markov chain whose stationary distribution happens to be the target distribution, and after running it long enough, the samples gradually approach the target distribution, no longer influenced by the initial state.

5. Common Misconceptions and Model Limitations

“Long-run stability” is most often misunderstood as the system eventually settling into a fixed state; in fact, a stationary distribution is stability at the distribution level: a weather chain might maintain a long-run split of 60% sunny days and 40% rainy days, but any specific day is still constantly sunny or rainy — it doesn’t mean the weather settles into being one or the other. A second common misconception is conflating “a stationary distribution exists” with “the chain will necessarily converge to it”: a periodic chain can also have a stationary distribution, yet never smoothly converge to it from an arbitrary initial state — the two-state deterministic oscillation example above is exactly such a case. A third limitation is that every convergence result discussed here assumes a finite state space; when the state space is infinite, even an irreducible and aperiodic chain isn’t guaranteed to have a stationary distribution — some infinite-state chains have every state null recurrent or transient, which needs to be checked separately.

6. Summary

The core questions in long-run analysis of a Markov chain are: can states reach each other, will you come back after leaving, are there absorbing states, does a stationary distribution exist, does the chain converge to it from any initial state, and how long does convergence take? A stationary distribution satisfies $\pi P=\pi$; for the concrete example in Section 3, this was solved to give $\pi=(1/3,1/2,1/6)$. As long as the chain is irreducible and aperiodic, the long-run state distribution generally forgets its initial condition and converges to this unique $\pi$. These concepts aren’t merely abstract classification: Stochastic Processes 7: Random Walks ties the Markov property, increments, recurrence, transience, and the central limit theorem almost entirely together.