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 of the transition matrix lists tomorrow’s chances when today is in state , so every row is a probability vector. If today’s distribution is the row vector , tomorrow’s is , and after days it is . 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 , the blue point is the start and the red path joins
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 is a weighted average of the corners, so 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 , and so on. When some power of has every entry positive, these nested triangles close in on a single point: the steady state .
Why π is an eigenvector, and how fast p_n gets there
The point that stays put satisfies : is an eigenvector for the eigenvalue 1 (a left eigenvector; with columns, ). The difference has entries adding to 0, and on such vectors acts through its other two eigenvalues : each eigenvector direction scales by its own eigenvalue in one step. So when both are smaller than 1 in size, approaches , and the larger size sets the pace. For the weather chain , so once is large each step leaves a little under half of the distance (for starts with a part along ); 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 goes round for ever unless it starts at . 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 still settles, but where depends on where it starts. For a chain with finitely many states, tends to the same 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 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.