Markov Chains
A Markov chain is a random process whose next state depends only on the current state, not the full history.
The Markov property
A Markov chain is a sequence of random states in which the probability of the next state depends only on the present state: P(X_{t+1} | X_t, X_{t−1}, …) = P(X_{t+1} | X_t). The present screens off the past. This memorylessness makes the process both tractable and widely applicable.
The transition matrix
For a finite state space, a chain is fully described by a transition matrix P, where P[i][j] is the probability of moving from state i to state j. Each row is a probability distribution, summing to 1. The distribution after t steps is the initial distribution multiplied by Pᵗ.
Classifying states
- Recurrent states are revisited with probability one; transient states may be left forever.
- A chain is irreducible if every state is reachable from every other.
- A state is periodic if returns occur only at multiples of some period.
Long-run behavior
An irreducible, aperiodic finite chain converges to a unique stationary distribution π satisfying π = πP, regardless of where it starts. The chain forgets its initial state, and long-run time averages equal averages over π.
Where they appear
Markov chains model queues, reliability state transitions, language as sequences of tokens, and page-ranking on the web. They are also the engine of Markov chain Monte Carlo, where a chain is engineered to have a target distribution as its stationary distribution.