Markov Chain Steady State Calculator
Enter a transition matrix and get the long run distribution of the states, how many steps it takes to settle and the return time.
What it does
A Markov chain is a process that moves from state to state, and the rule is that the chance of the next state depends only on the state you are in now. That is the whole Markov assumption, and it is enough to make the long run behaviour of the chain completely predictable.
The lecture notes behind this page state the result precisely. A distribution pi is stationary for a chain with transition matrix P if pi times P equals pi, and if you start the chain with that distribution it stays there for ever. The same notes show the practical method, which is to write the system of linear equations that pi times P equals pi produces, solve it, and then add the condition that the shares add up to one.
The steady state matters because it tells you where a process spends its time. The CMU notes behind this page make the point that pi of a state is the average time the chain spends there, and that the stationary distribution is a left eigenvector of the matrix with eigenvalue one, with the caveat that not every such eigenvector is a probability distribution.
This page solves that system for you. Enter the transition matrix, one row per state, and it returns the steady distribution, the number of steps the chain needs to settle on it from the starting distribution you give, the state that holds the largest share, and the mean return time to that state, which is one over its share.
The limits are worth stating. The chain has to be finite, and for the steady state to be unique the chain has to be irreducible, so every state has to be reachable from every other state. A chain with a closed part that nothing leads into has more than one steady state, and the tool says so rather than picking one.
How to use
- Enter the transition matrix with one row per state, separated by semicolons, and the values separated by spaces or commas.
- Check that every row adds up to 1, which the tool verifies for you.
- Optionally give the starting distribution, as the share of the chain in each state at the start.
- Read the steady distribution, which is where the chain ends up however it started.
- Read the number of steps to settle, which tells you how long a simulation needs before its output means anything.
- Read the mean return time, which is the average gap between visits to the busiest state.
Formula
- P
- Transition matrix, where the entry in row i and column j is the chance of moving from state i to state j.
- pi
- Vector of shares, one per state, that adds up to 1 and satisfies pi times P equals pi.
- E return
- Mean number of steps between visits to a state, which is the reciprocal of its share.
The chain settles when the distribution stops changing from one step to the next, and the tool counts the steps until the change falls below one part in ten billion. The mean return time comes from the CMU notes, which give the reciprocal of the expected first return time as the share of the steady state that a state holds.
Worked example
Example: a two state chain that mostly stays where it is
Defaults: the transition matrix 0.9 0.1; 0.2 0.8 and no starting distribution, so the chain starts from an even spread.
- The matrix says that from the first state there is a 0.1 chance of moving to the second, and from the second a 0.2 chance of moving back to the first.
- Let the share in the first state be p, so the share in the second is 1 - p, and the steady state needs p = 0.9p + 0.2(1 - p).
- That gives 0.1p = 0.2 - 0.2p, so 0.3p = 0.2 and p = 0.6667.
- So the steady distribution is 66.67 percent in the first state and 33.33 percent in the second.
- Starting from an even spread, the chain needs 71 steps before the distribution stops changing, because the mismatch decays by a factor of 0.7 each step.
- The busiest state holds 66.67 percent of the time, so the mean return time is 1 / 0.6667 = 1.50 steps.
- The tool shows 66.67 percent and 33.33 percent, 71 steps, the first state at 66.67 percent, and a mean return of 1.50 steps.
Reference table
| Starting distribution | Steady state | Steps to settle |
|---|---|---|
| Even spread, 50 and 50 | 66.67 % and 33.33 % | 71 steps |
| All in the first state | 66.67 % and 33.33 % | 73 steps |
| All in the second state | 66.67 % and 33.33 % | 74 steps |
| Three state chain, 0.5 0.5 0; 0.2 0.5 0.3; 0 0.4 0.6 | 18.60 %, 46.51 % and 34.88 % | 42 steps |
Limits
- The chain has to be finite and irreducible for the steady state to exist and to be unique. A chain that cannot leave one group of states has more than one steady state.
- The steady state says where the chain spends its time in the long run, and nothing about how it gets there or how long the transient lasts.
- The steps to settle depend on the tolerance used and on how close the chain already is, so the number is a guide rather than a fixed time.
- A real process that looks Markovian usually is only approximately so, and the state you choose may not capture everything that matters.
Common mistakes
- Transposing the matrix. The rows are the state you are in and the columns are the state you move to, and getting that backwards swaps the answer for the transpose.
- Forgetting that the rows have to add up to 1, so the matrix is not a valid set of probabilities.
- Expecting the steady state to be uniform. It is uniform only when the chain is symmetric, and the example shows how lopsided a real one can be.
- Treating the steps to settle as the time to reach the answer exactly. It is the point at which the answer stops moving to the digits you care about.
- Using a chain with a state that nothing leads into, which has a whole family of steady states and no single answer.
Try it yourself
Quick checks. Answers sit tucked under each question.
Does the starting distribution change where the chain ends up?
No. Starting from all in the first state, from all in the second state or from an even spread, the steady state is the same 66.67 percent and 33.33 percent, because the steady state is a property of the matrix alone. What changes is the settling time, which is 73, 74 and 71 steps respectively.
How often does the chain visit the first state?
Every 1.50 steps on average, which is the reciprocal of its share of the steady state. The chain spends two thirds of its life in the first state and one third in the second, so a typical visit to the first state comes one step after the last one and the next visit comes two steps later.
What if the matrix were 0.5 0.5; 0.2 0.8?
The steady state moves, because the first row changed. With 0.5 0.5; 0.2 0.8 the chain settles on 28.57 percent in the first state and 71.43 percent in the second, and it gets there in 23 steps, because the mismatch now decays by a factor of 0.3 each step instead of 0.7.
Questions
What is a Markov chain?
A process with a finite or countable set of states where the chance of the next state depends only on the current state. The lecture notes behind this page write that as P of z at t given z at t minus 1, and call it the Markov assumption.
What is the stationary distribution?
A vector of shares that satisfies pi times P equals pi. Once the chain is in that distribution it stays there, which the Zitkovic notes prove by showing that the distribution after any number of steps is pi times P to the power n, and that equals pi.
How is the steady state worked out?
Write the linear equations that pi times P equals pi produces, replace one of them with the condition that the shares add up to one, and solve. The Zitkovic notes show exactly that method on a three state example of social mobility.
What is the mean return time?
The average number of steps between visits to a state. The CMU notes give it as the reciprocal of the share of the steady state that the state holds, and the UZH lecture notes make the same point in the language of transition probabilities.
What happens if the chain cannot reach every state?
The steady state is not unique. A chain with a closed group of states that nothing else leads into can sit in that group for ever, so there is a family of steady states rather than one answer, and the tool refuses to pick one.
Where is this used?
Everywhere a process depends on its present state and nothing else. Queueing, customer churn, disease progression, page views, quality control in factories and the spread of an epidemic are all modelled this way.
Sources
- Carnegie Mellon University course notes: the stationary distribution of a Markov chain and the mean return time
- Lecture notes for introduction to stochastic processes, chapter 8: stationary distributions