Markov Chains

Memoryless hops between states, and the distribution they settle into.

The idea

A Markov chain models a system that occupies one of a set of states — sunny or rainy, working or broken — and moves to a state at every tick of a clock. In general, where a random process goes next could depend on its entire history. The Markov chain is the case where it does not: the probability of the next state depends only on the current one, $\mathbb{P}(\text{next} = j \mid \text{now at } i \text{, and the entire past}) = \mathbb{P}(\text{next} = j \mid \text{now at } i).$ These numbers, one for each ordered pair of states, are the transition probabilities, and they stay fixed from step to step. Two histories that end in the same state therefore produce identical forecasts.

Two questions organize the subject. First, where is the chain likely to be several steps from now? We answer by conditioning on the state at each intervening tick. Second, is there a distribution over the states that one step leaves unchanged? Such a distribution is called stationary, and it is what the long-run fractions of time spent in each state settle down to.

Ways to work on it

• Walkthrough. Memorylessness, propagating probabilities, and the stationary balance equation.
• Practice. Two-step probabilities by conditioning.
• Hardest. Find a chain's stationary distribution.

Not sure where to start? Take the ten-question placement test.