Markov Chains from Scratch — The Process That Only Looks at Now

What happens next depends only on where you are now — that single act of forgetting is a Markov chain. From transition matrices and stationary distributions to why PageRank is an eigenvector and why MCMC gets to ignore the normalizing constant, built from nothing assumed.

A board game doesn't remember how you got there

You are on square 12 in Snakes and Ladders. Where you go next depends on the die and on square 12 — nothing else. Whether you slid down from 30 or walked up from 11 has no bearing whatsoever on the next move. That willingness to forget the road you took and look only at where you stand is a Markov chain.

For weather, it is a model that knows one rule: "if today is rainy, tomorrow is rain 0.6, cloudy 0.3, sunny 0.1." It looks crude. But the crudeness is exactly what makes the arithmetic astonishingly cheap, and that same cheap arithmetic runs underneath web search rankings, Bayesian statistics, and diffusion models.

The phrase people trip over is "memoryless." More precisely, the memory has been folded into the current state. You are not throwing the past away; you are declaring that everything about the past that still matters for the future can be read off the state you are in right now.

The Markov property: what you throw away, what you keep

Write the state at time $t$ as $X_t$. A state is one entry in the list of places the model is allowed to be — sunny, cloudy, rainy.

$P(A \mid B)$ reads "the probability of A given that B happened." The left side is tomorrow's probability computed with the entire history in hand; the right side uses today alone. Read in words, it says: forecasting tomorrow needs today's weather, and knowing last week's would not change the answer.

Real data usually violates this. A user's next click depends not only on the page they are on but on what they came looking for in the first place. The escape hatch is to fatten the state. If you think yesterday and today jointly decide things, make the state the pair "(yesterday, today)" and the story closes under "only look at now" again. Language-model n-grams are precisely this trick, and the price is a blow-up in the number of states — a 10,000-word vocabulary conditioned on the previous two words is 100 million combinations.

So the real work in a Markov modeling job is not solving equations. It is deciding what to call a state.

The transition matrix: put it in a table and prediction becomes multiplication

With three states, the transition probabilities fit in a 3×3 table.

Two conventions and that is all. Rows are "today," columns are "tomorrow." And every row sums to 1, because tomorrow you are certainly somewhere. This table is the transition matrix $P$. Columns do not sum to 1 — popular states collect arrows from many rows at once.

Hold today's weather as a distribution — "sunny 50%, cloudy 30%, rainy 20%" — written as a row of numbers $\pi_t = (0.5,\ 0.3,\ 0.2)$, and tomorrow's distribution falls out of a single multiplication.

Said in words: take "what fraction is where now," multiply by "from there, what fraction goes where," and out comes "what fraction is where tomorrow." Underneath it is nothing but sums of products — the sunny share times the sunny→cloudy probability, plus the cloudy share times cloudy→cloudy, and so on. Repeat it and $n$ days out is one shot too.

Which is to say: prediction with a Markov chain is raising a matrix to a power. Everything from here narrows to a single question — what happens when you keep multiplying by the same matrix?

The stationary distribution: run it long enough and it forgets where it started

Take that matrix and multiply repeatedly from different starting points, and something interesting happens. Start from "definitely sunny" or from "definitely rainy," and after ten days or so both distributions settle onto nearly the same numbers. The information about the initial condition evaporates. Where it settles is the stationary distribution.

Here $\pi$ is the stationary distribution, and $\sum_i \pi_i = 1$ says it is a probability, so the entries add to one. Put in words: the distribution that steps forward one day and comes back unchanged.

At this point linear algebra walks in. Read $\pi P = 1 \cdot \pi$ and the stationary distribution is an eigenvector with eigenvalue 1 — a left eigenvector, to be exact. The idea that an eigenvector is "a direction the transformation refuses to rotate" is worked through in The Linear Algebra Under LoRA and RAG. Here it translates into "a set of proportions that tomorrow does not change."