explainer
Markov chains: transitions and stationary distributions
Learn Markov chains with a robot example. Explore transition matrices, stationary distributions, periodic chains, and absorbing states with an interactive model.
What you will learn
- Read a transition matrix and propagate a row probability vector.
- Distinguish a robot's state from a distribution over possible states.
- Explain when a stationary distribution exists, is unique, or attracts other distributions.
Before you start
- Conditional probability and the law of total probability
- Multiplication and addition of probabilities
A robot may be working now and paused a minute later. A Markov chain describes the probabilities of those transitions. Repeated updates show how uncertainty about its state changes with time.
Some chains approach one steady distribution. Others alternate forever or retain their starting probabilities. We will calculate each case with two states.
Separate a state from its probability
Let Xₜ be the robot's state at minute t. In this model, it takes one of two values: Working or Paused.
A probability distribution lists our probabilities for those possible states. We use the fixed order (Working, Paused):
- p = (1, 0) means the robot is working with certainty.
- p = (0, 1) means it is paused with certainty.
- p = (0.8, 0.2) assigns an 80% chance to Working and 20% to Paused.
The robot occupies one state at a time. The two numbers describe uncertainty about that state. They are nonnegative and sum to 1.
The NLP lesson applies a related limited-history idea to word sequences: a bigram model predicts the next token from the previous one. Its counts also show what happens when a context has never appeared.
A sampled trajectory would list states such as Working, Working, Paused. Our experiment updates the whole distribution deterministically. Running the same calculation twice gives the same probabilities.
State the two modeling assumptions
The Markov property says that, given the current state, earlier states add no information about the next state's distribution:
P(Xₜ₊₁ = j | Xₜ = i, earlier history)
= P(Xₜ₊₁ = j | Xₜ = i)
This condition applies to histories with positive probability. It does not make successive states independent: a paused robot may have different next-state probabilities from a working robot. Hossein Pishro-Nik's probability textbook defines the Markov property through this conditioning.
We also assume the chain is time-homogeneous: its transition probabilities stay the same at every step. This is a separate assumption. A process can satisfy the Markov property while its transitions change with the time of day.
Our state set is finite, and time advances in discrete one-minute steps. The numbers below are teaching examples, not measurements from a deployed robot.
Read the transition matrix by rows
Entry Pᵢⱼ means the probability of state j next, conditional on state i now. For the “Robot operation” example:
| Current state ↓ / Next state → | Working | Paused |
|---|---|---|
| Working | 0.8 | 0.2 |
| Paused | 0.4 | 0.6 |
A working robot stays working with probability 0.8 and pauses with probability 0.2. A paused robot resumes with probability 0.4.
Every entry must fall between 0 and 1, and each row must sum to 1. This is a row-stochastic matrix. Its columns need not sum to 1; here they sum to 1.2 and 0.8. The textbook's transition-matrix section explains why the row sums equal 1.
Some sources transpose this convention. Here, distributions are row vectors and always multiply P on the left.
Calculate the next distribution
To find the probability of a destination, add the contribution from each possible current state. This uses the law of total probability:
pₜ₊₁ = pₜ P
pₜ₊₁(j) = Σᵢ pₜ(i) Pᵢⱼ
Start at p₀ = (1, 0). The first update gives p₁ = (0.8, 0.2). On the second update:
P(Working at step 2) = 0.8 × 0.8 + 0.2 × 0.4 = 0.72
P(Paused at step 2) = 0.8 × 0.2 + 0.2 × 0.6 = 0.28
The two routes to Paused are Working → Working → Paused, with probability 0.16, and Working → Paused → Paused, with probability 0.12. Adding them gives 0.28.
After n steps, pₙ = p₀Pⁿ. A matrix power includes every possible intermediate route. It does not require sampling one route.
Step the probabilities forward
Press Step twice to reproduce (0.72, 0.28). Choose Step 10 to see the later behavior. The dashed markers show a unique stationary distribution when the selected matrix has one.
Change the starting distribution to Paused with certainty. The “Robot operation” probabilities approach the same markers from a different starting point.
Choosing a new model or starting distribution returns to step 0. Reset keeps those choices. The display stops after 60 steps; this limit is part of the experiment, not a property of the chain.
Find a distribution that stays unchanged
A stationary distribution π satisfies πP = π. One update leaves its probabilities unchanged. Individual robots may still switch states.
For our example, let π = (w, q), where w + q = 1. The Working equation gives:
w = 0.8w + 0.4q
0.2w = 0.4q, so w = 2q
π = (2/3, 1/3)
At those probabilities, the flow from Working to Paused is (2/3) × 0.2. The reverse flow is (1/3) × 0.4. They match, keeping the distribution fixed.
With our row convention, π is a left eigenvector of P with eigenvalue 1. Transposing gives Pᵀπᵀ = πᵀ, matching the column-vector form in the eigenvalues lesson.
Every finite Markov chain has at least one stationary distribution. Stationarity alone does not establish convergence from another starting distribution. Robert Gallager's MIT notes separate the fixed-distribution equation from convergence.
Check whether other distributions approach it
A finite chain is irreducible when every state can reach every other state in some number of steps with positive probability. Such a chain has a unique stationary distribution.
It is aperiodic when possible return times have greatest common divisor 1. In an irreducible chain, a positive chance of staying in any one state is enough. Our robot example has positive chances of staying in both states.
For a finite, irreducible, aperiodic chain, every starting distribution approaches the unique stationary distribution. Pishro-Nik's stationary and limiting distribution section states this convergence result.
The other presets show why each conclusion needs care:
- Alternating states uses P = [0, 1; 1, 0]. Starting from (1, 0), distributions alternate between (1, 0) and (0, 1). The chain has period 2. Its unique stationary distribution is (0.5, 0.5), and starting there keeps it fixed.
- Stay where started uses P = [1, 0; 0, 1]. Both states are absorbing: once entered, they cannot be left. Every distribution is stationary, so the starting probabilities determine the result.
- Pause is absorbing uses P = [0.8, 0.2; 0, 1]. This chain is reducible, yet its stationary distribution is unique: (0, 1). Starting entirely in Working gives Working probability 0.8ⁿ, which approaches zero.
Irreducibility guarantees uniqueness for a finite chain, but the absorbing example shows it is not necessary. Also, a rounded match to the markers does not prove exact stationarity.
Use the model for a robot
The state must contain enough information for the Markov assumption to make sense. “Working” may hide battery charge, motor temperature, or time since maintenance. If those change transition chances, two robots with the same label can need different predictions.
You could expand the state to include a battery category or recent operating history. Then check whether observed transitions support the new model. More states require more data to estimate their probabilities.
Probability propagation also fits into state estimation. Multiplying by P predicts the next state distribution before receiving a new sensor reading. A Bayesian update can then combine that prediction with the reading's likelihood under each state.
Reproduce the updates in Python
This example uses only the standard library. It prints five distributions and verifies the stationary result. The update sums across current states for each destination column.
from math import isclose
P = [[0.8, 0.2], [0.4, 0.6]]
assert all(isclose(sum(row), 1.0) for row in P)
def advance(p, matrix):
return [sum(p[i] * matrix[i][j] for i in range(len(p)))
for j in range(len(p))]
p = [1.0, 0.0]
for step in range(5):
print(f"{step}: ({p[0]:.4f}, {p[1]:.4f})")
p = advance(p, P)
stationary = [2 / 3, 1 / 3]
assert all(isclose(a, b) for a, b in
zip(advance(stationary, P), stationary))
print(f"stationary: ({stationary[0]:.4f}, {stationary[1]:.4f})")
flip = [[0, 1], [1, 0]]
assert advance(advance([1, 0], flip), flip) == [1, 0]
Expected output:
0: (1.0000, 0.0000)
1: (0.8000, 0.2000)
2: (0.7200, 0.2800)
3: (0.6880, 0.3120)
4: (0.6752, 0.3248)
stationary: (0.6667, 0.3333)
Try it yourself
Exercise 1. For “Robot operation,” start with (0.5, 0.5). Calculate the distributions after one and two steps. Check that each still sums to 1.
Show solution: weight both possible starting states
After one step, Working has probability 0.5 × 0.8 + 0.5 × 0.4 = 0.6. Paused has probability 0.4.
After two steps, Working has probability 0.6 × 0.8 + 0.4 × 0.4 = 0.64. Paused has probability 0.36. Both pairs sum to 1. Select the 50/50 start to check the calculation.
Exercise 2. Use “Alternating states.” Starting from (1, 0), find the next two distributions. Repeat from (0.5, 0.5). Explain how a stationary distribution can coexist with an alternating one.
Show solution: separate stationarity from convergence
From (1, 0), the next distributions are (0, 1) and (1, 0). Repeating these updates never approaches (0.5, 0.5).
From (0.5, 0.5), both updates give (0.5, 0.5). That distribution satisfies πP = π, so it is stationary. Its existence does not force other starting distributions to approach it.
Sources and further study
- Hossein Pishro-Nik: Introduction to Markov Chains, for the Markov property and time-homogeneous transitions.
- Pishro-Nik: State Transition Matrix and Diagram, for the row-stochastic convention.
- Pishro-Nik: Stationary and Limiting Distributions, for the two-state calculation and finite-chain convergence conditions.
- Robert Gallager, MIT: Finite-State Markov Chains, the Matrix Approach, for matrix powers, stationary distributions, and reducible chains.