skip to content

Does every finite Markov chain converge to the same long-run distribution regardless of where it starts?

level: seniorimportance: should knowfreq 45%

answer

  1. reachability first, rhythm second
  2. two conditions, both required
  3. a strict alternation never settles
  4. one self-loop kills the period
  5. a dead-end page traps the walk

basics

~20 s

No. Convergence to one limiting distribution from any start requires the chain to be irreducible and aperiodic. A chain that strictly alternates between two states, or one that splits into groups that cannot reach each other, never settles.

solid answer

~50 s

Two conditions do the work. **Irreducible** means every state is reachable from every other, so the chain cannot get trapped in one region. **Aperiodic** means the return times to a state have greatest common divisor 1, so the chain does not march in lockstep. For a finite chain, irreducible plus aperiodic gives a unique `pi` with `P^n` rows converging to it from any start. Drop aperiodicity and you get the strict alternation `A -> B -> A -> B`: starting at `A` the distribution flips between `(1, 0)` and `(0, 1)` forever, even though `pi = (0.5, 0.5)` still exists and still describes the long-run fraction of time. Drop irreducibility and the limit depends on the start — a navigation chain with a dead-end page is the everyday version. The usual repair adds a small uniform jump probability from every state, making the chain irreducible and aperiodic at once.

code

python · 12 lines
python
def step(v, P):
    return [sum(v[i] * P[i][j] for i in range(len(v))) for j in range(len(v))]

weather = [[0.8, 0.2], [0.4, 0.6]]   # irreducible and aperiodic
flip = [[0.0, 1.0], [1.0, 0.0]]      # irreducible but period 2

for name, P in (("weather", weather), ("flip", flip)):
    v = [1.0, 0.0]
    print(name)
    for n in range(1, 9):
        v = step(v, P)
        print("  n =", n, [round(x, 3) for x in v])

go deeper

for a junior

Be ready to name the two conditions — irreducible and aperiodic — and to give the alternating two-state chain as the example that never settles.

for a middle

Define reachability and period precisely, and explain why a single self-loop in an irreducible chain forces aperiodicity.

for a senior

Show the diagnosis in real work: check the transition graph for strong connectivity and dead ends before quoting any long-run share, and know the uniform-jump repair.

for a principal

Own the modelling call behind the repair: how much distortion of the real transition structure you accept in exchange for a chain that provably converges and forgets its start quickly.

## Two structural properties Everything here is about the shape of the transition graph, before any arithmetic. **Reachability and irreducibility.** State `j` is reachable from `i` if some power of the transition matrix has a positive (i, j) entry — that is, there is a path of positive-probability steps. States that reach each other belong to the same **communicating class**. The chain is **irreducible** when there is exactly one class: every state reaches every other. In graph terms, the directed transition graph is strongly connected. **Period.** The period of state `i` is ``` d(i) = gcd { n >= 1 : P^n[i][i] > 0 } ``` the greatest common divisor of the lengths of all loops returning to `i`. If `d(i) = 1` the state is **aperiodic**. Within a communicating class all states share the same period, so for an irreducible chain 'aperiodic' is a property of the whole chain. A single self-loop anywhere in an irreducible chain forces period 1, because a return of length 1 is available and `gcd(1, anything) = 1`. ## The convergence theorem For a finite chain that is irreducible and aperiodic (often called **ergodic**): - a unique stationary distribution `pi` exists; - `P^n[i][j] -> pi_j` for every pair `(i, j)`, so the rows of `P^n` all converge to the same vector; - consequently the distribution after `n` steps converges to `pi` from *any* starting distribution. That last point is what people mean by 'the chain forgets its start'. The rate of forgetting is governed by how quickly the differences between rows shrink; some chains mix in a handful of steps, others take an impractically long time even though they converge in theory. ## Failure mode one: periodicity Take the two-state chain that always switches: ``` P = [ 0 1 ] [ 1 0 ] ``` Start at `A`, so `v_0 = (1, 0)`. Then `v_1 = (0, 1)`, `v_2 = (1, 0)`, and so on forever. The step-`n` distribution does not converge; it oscillates with period 2. Yet the chain is irreducible, and `pi = (0.5, 0.5)` does satisfy `pi = pi P`. What survives is the **time-average** statement: the fraction of the first `n` steps spent in `A` tends to 0.5. So a periodic chain has a perfectly meaningful long-run share of time, and no limiting distribution. If you started this chain from `pi` itself, the distribution would sit at `(0.5, 0.5)` forever — stationarity holds; only convergence from an arbitrary start fails. Diagnosing periodicity in a bigger chain: look for a partition of the states into `d` groups where every transition goes from group `k` to group `k+1` cyclically. Adding any self-loop with positive probability destroys it. ## Failure mode two: reducibility If the transition graph has two or more **closed** communicating classes — groups you can enter but never leave — the chain is reducible. Each closed class has its own stationary distribution, and every mixture of them is also stationary, so uniqueness fails. Where you start determines which class you end up in, and hence which limit you approach. An absorbing state is the extreme case: a class of size one that traps the chain forever. The everyday version in a web-navigation chain is a **dangling page** with no outgoing links. Strictly, its row cannot be made to sum to 1 by following links, so the chain is not even well defined; and if you patch it by adding a self-loop, that page becomes absorbing and the surfer is stuck there. Either way the long-run visit shares are meaningless. ## The standard repair Mix the link-following matrix with a small uniform jump: with probability `1 - a` follow a link as before, and with probability `a` jump to a page chosen uniformly at random. The resulting matrix has every entry strictly positive, which makes the chain irreducible (everything reachable in one step) and aperiodic (self-transitions have positive probability). A unique limiting distribution now exists, dead ends leak back into the rest of the graph, and the parameter `a` trades faithfulness to the real link structure against how fast the chain forgets its start. ## What to check in practice Before trusting any long-run number from a chain built out of real data: confirm the transition graph is strongly connected; look for states with no outgoing observed transitions, which are usually data artefacts rather than genuine absorbing states; look for deterministic cycles created by a coarse time grid; and confirm the rows sum to 1 after any patching you did. These structural checks cost minutes and prevent a confidently reported stationary vector that describes nothing.

  • For an irreducible but periodic chain, what still converges?
    The time-average does. The fraction of the first `n` steps spent in each state converges to the unique stationary distribution, even though the step-`n` distribution keeps oscillating. Starting the chain from `pi` itself also gives `pi` at every step, so stationarity holds; only convergence from an arbitrary start fails.
  • How does adding a small uniform jump probability fix a web-navigation chain?
    It makes every entry of the transition matrix strictly positive. That makes the chain irreducible, since any page is reachable from any page in one step, and aperiodic, since staying put has positive probability. A unique limiting distribution then exists and dead-end pages no longer trap the walk.
  • How can a chain have more than one stationary distribution?
    When it is reducible with two or more closed groups of states that cannot reach each other. Each group carries its own stationary distribution, and any weighted mixture of them is stationary too. Uniqueness fails, and the starting state decides which group the chain ends up in.
  • How would you spot periodicity in a chain with a dozen states?
    Look for a partition of the states into `d` groups where every positive-probability transition moves from group `k` to group `k+1` cyclically; equivalently, check whether all return loop lengths to some state share a common divisor above 1. Any state with a positive self-transition rules periodicity out immediately.

saying these in an interview costs you the question

  • Claims every Markov chain converges to a stationary distribution
  • Treats irreducible and aperiodic as the same condition
  • Says a periodic chain has no stationary distribution
  • Ignores dead-end states when building a navigation chain
  • Confuses slow mixing with outright non-convergence

context

resolving links…