A system that forgets everything except where it is now. Start it anywhere and it settles in the same place.
Overview
The property
A process is Markov when the next state depends only on the current state, not on the path that led there. The present screens off the past.
That is a strong assumption and a liberating one. Instead of a history of any length you carry one thing — where you're — and all about the future follows from it.
Markov Chains
This module needs JavaScript: the
numbers are computed in the page rather than recorded.
Worth knowing
The Markov property: the next state depends only on the current one, not on how you arrived.
A transition matrix holds the probabilities. Each row sums to 1, because you must go somewhere.
Iterating it converges to a stationary distribution — the eigenvector of P' with eigenvalue 1.
Change the starting state and the curves start in different places and arrive at the same one. That is the point.
Markov Chains
Memoryless processes, the spread they settle into, and why so many methods are one.
The transition matrix
Collect the chances into a mat P. Here P[i][j] is the chance of moving from state i to state j. each row sums to 1, because from any state you go a place, possibly back to where you were.
If the current spread over states is a row vector d, then after one step it's d P. After k steps, d P^k. That is all the math there's, and the visualisation is doing just it, forty steps at a time.
Convergence
Watch the three curves. They start apart. All the chance on one state — and within a few steps they flatten out and stop moving. The readout shows the last step changing things by around 10⁻¹⁰.
Now change the starting state. The curves begin a place fully different and arrive at the same values.
That limit is the stationary spread: the pi with pi P = pi. Read as an eigenvector problem, it's the left eigenvector of P with eigenval 1, and the eigenval module is the same mathematics in another costume.
The settling isn't auto. It needs the chain to be irreducible — each state reachable from every other. And aperiodic, not trapped in a fixed cycle. Drag a transition chance to its min and settling slows visibly. A chain that couldn't leave a state at all would never mix.
The speed is governed by the second-largest eigenval: the closer it's to 1, the slower the mixing. That number has a name, the *spectral gap*, and it's what people mean by a chain mixing slowly.
The whole thing on two states
All above fits on a chain with two states, small enough to do on paper and still large enough to show all three claims.
Weather, where a sunny day is often followed by another and rain clears half the time:
from \ to
sunny
rainy
sunny
0.9
0.1
rainy
0.5
0.5
The stationary spread, solved just. πP = π on two states is just πs = 0.9πs + 0.5πr, which rearranges to 0.1πs = 0.5πr, so πs = 5πr. With the two summing to 1 that gives π = (5/6, 1/6), or (0.8333, 0.1667). No iteration, no eigenval routine — two lines of algebra.
The same answer by iterating. Start with certainty and times by P again and again:
step
from sunny
from rainy
0
(1.000, 0.000)
(0.000, 1.000)
1
(0.900, 0.100)
(0.500, 0.500)
2
(0.860, 0.140)
(0.700, 0.300)
3
(0.844, 0.156)
(0.780, 0.220)
4
(0.838, 0.162)
(0.812, 0.188)
5
(0.835, 0.165)
(0.825, 0.175)
Two starting points that couldn't be further apart, settling on the same (0.8333, 0.1667). The chain forgets where it began. This Is the whole content of the claim that the limit doesn't depend on the start.
And the mixing speed. This Isn't a metaphor. The eigenvals of a 2×2 stochastic mat are 1 and (trace − 1). So Here the second eigenval is 0.9 + 0.5 − 1 = 0.4. Now measure how far the sunny column is from 0.8333 at each step:
0.1667, 0.0667, 0.0267, 0.0107, 0.0043, 0.0017
Each is just 0.4 times the one before it. The second eigenval isn't merely *related* to the mixing rate. It is the factor by which the left error shrinks per step. A chain with a second eigenval of 0.99 needs 365 steps to shrink the error as far as this one does in four. This Is why the spectral gap is the number MCMC practitioners worry about.
One more reading falls out of π for free. It's the one that makes the numbers concrete. The expected time to return to a state is 1 / πi, so rain recurs each 1 / (1/6) = 6 days on average and sun each 1 / (5/6) = 1.2 days. The stationary spread isn't only the long-run share of time spent in each state. It's the reciprocal of how long you wait to come back to it.
Where they appear
PageRank is the stationary distribution of a random surfer following links. The damping factor exists to make the chain irreducible. So A page with no outbound links can't swallow all the chance.
MCMC — Metropolis-Hastings, Gibbs sampling, Hamiltonian Monte Carlo — runs the idea backwards: make a chain whose stationary spread *is* the posterior you want, run it, and treat the states it visits as samples. Nearly all Bayesian work is this.
Hidden Markov models put a Markov chain behind readings you can see, and were the backbone of speech spotting for decades.
Reinforcement learning. A Markov choice process is a Markov chain with actions and rewards attached. The "Markov" in MDP is this property, and it's what makes value functions of the state alone enough.
n-gram language models are Markov chains over words — and their limitation is just the property: a bigram model can't note any of it beyond the previous word. This Is why long-range coherence needed a thing else.
Where it goes wrong with Markov Chains
given the property holds. Most real processes have memory. Widening the state to include recent history restores the property at the cost of a much larger state space.
given settling. Check irreducibility and aperiodicity.
Stopping an MCMC run too early. Samples before the chain has mixed reflect where you started, which is what burn-in discards and why settling diagnostics exist.
Confusing the stationary spread with the most likely state. It's the long-run fraction of time spent in each state, not a guess of where the chain is now.
Questions people ask about Markov Chains
What is the Markov property? The next state depends only on the current state, not on how you got there. History is summarised entirely by where you are now.
What is a transition matrix? A matrix whose entry (i, j) is the probability of moving from state i to state j. Each row sums to one.
What is a stationary distribution? A distribution pi with pi times P equal to pi. If you start in it, you stay in it as the chain runs.
When does a chain converge to a steady state? When it is irreducible and aperiodic: every state can reach every other, and it does not cycle with a fixed period.
How do I compute the n-step probabilities? Raise the transition matrix to the n-th power. Entry (i, j) of P to the n is the chance of being in j after n steps from i.
Where are Markov chains used? In PageRank, MCMC sampling, language modelling, queues and reinforcement learning, where states form a Markov decision process.
Walk the chain to its steady state
A three-state weather chain, stepped forward until the spread stops moving, then checked against the eigenvector that predicts it.
example_01.pyNumPy
import numpy as np
states = ["sunny", "cloudy", "rainy"]
# rows: from to: sunny cloudy rainy
P = np.array([[0.80, 0.15, 0.05], # from sunny
[0.30, 0.45, 0.25], # from cloudy
[0.20, 0.35, 0.45]]) # from rainy
print("each row sums to 1:", P.sum(axis=1))
print()
p = np.array([1.0, 0.0, 0.0]) # start certain it is sunny
print("%5s %8s %8s %8s" % ("step", *states))
for step in range(9):
print("%5d %8.4f %8.4f %8.4f" % (step, *p))
p = p @ P
print()
print("keep going and it stops moving:")
for _ in range(200):
p = p @ P
print(" steady state %s" % np.round(p, 6))
print()
print("the chain forgets where it started:")
q = np.array([0.0, 0.0, 1.0]) # start certain it is rainy
for _ in range(200):
q = q @ P
print(" from rainy %s" % np.round(q, 6))
print()
vals, vecs = np.linalg.eig(P.T)
v = np.real(vecs[:, np.argmin(np.abs(vals - 1))])
print(" left eigenvector for eigenvalue 1: %s" % np.round(v / v.sum(), 6))
Output
Check yourself
0 of 3
Answer without scrolling back up.
What does the Markov property say?
The present screens off the past, so you carry one thing - where you are - instead of a history of arbitrary length.
What is the stationary distribution?
It is where the chain settles regardless of where it started, provided the chain is irreducible and aperiodic.
What does MCMC do with this idea?
Nearly all Bayesian computation is this, which is also why burn-in and convergence diagnostics matter: early samples reflect the starting point, not the target.
Cheat sheet
Markov Chains
Step through a Markov chain and watch the state distribution converge to steady state. See why MCMC sampling and PageRank are both examples.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.