STATE 04 · DYNAMICS

Markov chains and transition matrices

Dependence that remembers only the present state.

The Markov property

A Markov chain is a series whose future depends on its past only through its present. Once the current state is known, the earlier history adds nothing to the prediction of the next state. This amnesia is the Markov property, and it is the source of the extraordinary tractability of the family. The chain moves through a set of states, and at each step it selects the following state according to a rule that may depend on the current state but on nothing earlier.

The states may be finitely many, countably many or continuously many. The finite chain is the simplest and by far the most instructive, and it is the case treated here. The chain may be pictured as a small chart of circles joined by arrows, where each circle is a state and each arrow records a possible move with its probability.

The transition matrix

The moves of a finite chain are gathered into a square table called the transition matrix. The entry in row i and column j is the probability of moving from state i to state j in a single step. Each row therefore contains non-negative numbers that sum to one, since from any state the chain must go somewhere. Such a table is called stochastic, in the sense of having unit row sums, and it is the complete specification of a finite chain.

Multiplying the transition matrix by itself gives the two-step table; the entry in row i and column j of the product is the probability of moving from i to j in exactly two steps, summed over the intermediate state. Higher powers give longer horizons, and the whole short-term behaviour of the chain is read from the successive powers of one matrix.

Stationary distributions

A stationary distribution is a probability row that the transition matrix leaves unchanged. If the chain is started with that row of probabilities over the states, then after one step, and after every step, the distribution remains the same. The stationary row is therefore a fixed point of the transition, and it describes the long-run proportion of time the chain spends in each state.

For an irreducible chain, one whose chart allows passage from any state to any other, and for an aperiodic chain, whose returns are not locked to a fixed rhythm, the successive powers of the transition matrix approach a table in which every row equals the stationary distribution. The chain forgets its starting state, and its position after many steps is nearly independent of where it began. The rate of this merging is governed by the second-largest magnitude among the eigenvalues of the transition matrix.

Absorbing states

A state is absorbing when once entered it cannot be left, so that its entire row of the transition matrix consists of a single one on the diagonal. Absorbing states model an ending: a game that concludes, a process that reaches a boundary and stays. In a chain with absorbing states the remaining states are often classified by the probability of eventual absorption in each of the absorbing states, and by the expected number of steps before absorption occurs.

These quantities satisfy linear equations obtained by conditioning on the first step, a technique that reduces a question about a whole trajectory to a short system of equations. The reduction is the clearest illustration of the power of the Markov property. From discrete states the reference turns to continuous time in Brownian motion.