Linear Algebra · Markov chain

Markov chain

A Markov chain moves between states at random, and the chance of each next state depends only on the current one. With these chances in a transition matrix P, tomorrow’s distribution is today’s times P; repeated, it often settles on a steady state π with πP = π, an eigenvector for the eigenvalue 1.

Markov chain in this visualization

A Markov chain moves between states at random, and the chance of each next state depends only on the current one. Here the states are sun, cloud and rain. Row ii of the transition matrix PP lists tomorrow’s chances when today is in state ii, so every row is a probability vector. If today’s distribution is the row vector pp, tomorrow’s is pPpP, and after nn days it is pn=p0Pnp_n = p_0 P^n. With three states every distribution is a point of a triangle: each corner is one state for certain, and the three probabilities are the point’s weights on the corners. The ink points are the rows of PP, the blue point is the start and the red path joins p0,p1,p2,…p_0, p_1, p_2, \dots

What one step does

One step sends each corner to its row: a day that is certainly sunny is followed by the distribution in the first row. Any other distribution pp is a weighted average of the corners, so pPpP is the same weighted average of the rows. The whole triangle therefore lands inside the smaller triangle spanned by the rows, two steps land inside the triangle spanned by the rows of P2P^2, and so on. When some power of PP has every entry positive, these nested triangles close in on a single point: the steady state π\pi.

Why π is an eigenvector, and how fast p_n gets there

The point that stays put satisfies πP=π\pi P = \pi: π\pi is an eigenvector for the eigenvalue 1 (a left eigenvector; with columns, PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). The difference p0−πp_0 - \pi has entries adding to 0, and on such vectors PP acts through its other two eigenvalues λ2,λ3\lambda_2, \lambda_3: each eigenvector direction scales by its own eigenvalue in one step. So when both are smaller than 1 in size, pnp_n approaches π\pi, and the larger size ∣λ2∣|\lambda_2| sets the pace. For the weather chain ∣λ2∣≈0.462|\lambda_2| \approx 0.462, so once nn is large each step leaves a little under half of the distance (for starts with a part along λ2\lambda_2); when the two eigenvalues are complex, the path also turns as it shrinks.

When it does not settle

In the cycle, sun always turns to cloud, cloud to rain and rain to sun. The other two eigenvalues have size 1, and pnp_n goes round for ever unless it starts at π\pi. With two traps, sun and rain each hold the chain for ever: the eigenvalue 1 appears twice and every mixture of sun and rain stays put, so pnp_n still settles, but where depends on where it starts. For a chain with finitely many states, pnp_n tends to the same π\pi from every start exactly when there is a single closed class (a set of states that reach one another and never leave) and that class is not periodic. A common way to be sure is that some power PmP^m has every entry positive.

Things to notice

  • For the weather chain, the steady state gives the chances for a day far in the future, whatever the start; the weather itself keeps changing from day to day.
  • With more than three states the distributions fill a higher-dimensional version of the triangle (a simplex), and the same argument works.

Controls

  • Drag an ink point to change a row of the transition matrix, or the blue point to change the start; arrow keys move a focused point by one hundredth.

Related