Discrete-Time Markov Chains

Will it rain tomorrow? A crude but surprisingly useful forecaster looks only at today: if it is sunny now, there is some chance of sun tomorrow; if it is raining, a different chance. It never consults last week, last month, or the season — just the present. That deliberate forgetfulness is the heart of a Markov chain, the workhorse model for systems that rattle randomly between a handful of states: machines that break and get repaired, customers who churn or stay, web-surfers hopping between pages, molecules flipping shape. Master this one model and a huge swathe of stochastic operations research opens up.

States and the Markov property

A Markov chain lives on a finite set of states and moves in discrete time steps. Its defining feature is the Markov (memoryless) property:

the probability of the next state depends only on the current state, not on the history of how we got there;
formally, P(X_{t+1} = j \mid X_t = i,\, X_{t-1}, \dots) = P(X_{t+1} = j \mid X_t = i) — the past is irrelevant given the present.

This is not an assumption that nothing before matters — it is an assumption that everything that matters has been packed into the state. It is the same conditional-probability idea that powers dynamic programming, now driving a random process forward in time.

The transition matrix

Collect the one-step probabilities p_{ij} = P(\text{go to } j \mid \text{in } i) into a square transition matrix P. Every entry is a probability, and — since from any state you must go somewhere — each row sums to 1. A matrix with non-negative entries and rows summing to 1 is called stochastic.

The magic is that matrix multiplication does the probability bookkeeping for us. The chance of moving from i to j in exactly n steps is the (i,j) entry of P^{n}:

P(X_{t+n} = j \mid X_t = i) = \bigl(P^{n}\bigr)_{ij}.

And if \pi^{(t)} is the row vector of state probabilities today, then tomorrow's is \pi^{(t+1)} = \pi^{(t)} P. Multiply by P to step the whole distribution forward.

A weather chain

Two states, Sunny and Rainy. Suppose a sunny day is followed by another sunny day with probability 0.8 (and rain with 0.2), while a rainy day is followed by sun with probability 0.6 (and more rain with 0.4). The transition matrix, ordering the states (S, R), is

P = \begin{pmatrix} 0.8 & 0.2 \\ 0.6 & 0.4 \end{pmatrix}.

Each row sums to 1, as it must. From this little diagram we can answer real questions: the chance that two sunny days follow a sunny one is (P^2)_{SS} = 0.8\cdot0.8 + 0.2\cdot0.6 = 0.76.

The stationary distribution

Run the chain for a long time and the probabilities settle down: they stop changing from step to step. That limiting row vector \pi is the stationary distribution, and it is the fixed point of the update rule — a distribution that P maps to itself:

\pi = \pi P, \qquad \sum_i \pi_i = 1.

For the weather chain, writing \pi = (\pi_S, \pi_R) gives \pi_S = 0.8\,\pi_S + 0.6\,\pi_R. With \pi_R = 1 - \pi_S this solves to \pi_S = 0.75, \pi_R = 0.25. So in the long run three-quarters of days are sunny and one-quarter rainy, no matter what today's weather is. A chain that is regular (some power of P has all-positive entries) always has a single such \pi that it converges to from any start.

Not every chain wanders forever. An absorbing state is one you can never leave — p_{ii} = 1 — like "graduated," "machine scrapped," or "gambler broke." A chain with absorbing states eventually lands in one and stops, so its interesting questions are different: which absorbing state will we end in, and how many steps until we do? These "expected time to absorption" calculations model everything from board games to reliability engineering, and they use the same matrix P, just carved into transient and absorbing blocks. Regular chains ask "what fraction of time?"; absorbing chains ask "where and when do we end?"

It is tempting to read \pi_R = 0.25 as "there is a 25% chance it rains tomorrow." That is wrong. The stationary distribution describes the long-run fraction of time the chain spends in each state — a time-average over many, many steps. Tomorrow's actual probability depends on today's state through a single row of P: if it is raining today, tomorrow's rain probability is 0.4, not 0.25. The chain only "forgets" today's state gradually; \pi is where it lands after that memory has fully washed out, not a prediction of the very next step.