Markov Chain Steady State (2 States)

Two-state Markov chain — stationary distribution

In a Markov chain, where you go next depends only on where you are now, not on the path that got you there. That is the memoryless property. Take two states with the transition matrix P = [[1−a, a], [b, 1−b]]. The stationary distribution π is the one that stays put under the dynamics, so πP = π, with π₁ + π₂ = 1. Solve that little linear system and you get π = (b/(a+b), a/(a+b)). With a = 0.3 and b = 0.2, for instance, π comes out to (0.4, 0.6). Whatever distribution you start from, the chain settles toward π in O(log) iterations, and the second eigenvalue of P sets how quickly.

Applications

Google's PageRank treats web pages as states. You also see two-state and larger chains in population modeling (urban versus rural migration), queueing theory (M/M/1 systems), chemical state transitions, NLP for word generation and text models, allele frequencies in population genetics, reliability engineering with working and failed states, and the classic sunny/rainy weather forecast.

FAQ

Does a stationary distribution always exist? When the chain is irreducible and aperiodic (a + b > 0 and not (a = b = 1)), yes, and there's exactly one. A degenerate case like a = b = 0 gives an absorbing chain that never mixes.

What does the stationary distribution mean? Over the long run, it's the share of time the chain spends in each state, and it doesn't depend on where you began.

How fast does it converge? That comes down to |1 − a − b|, the second eigenvalue. The nearer it sits to 0, the quicker the chain converges.