Markov Chains

Imagine you want to predict tomorrow's weather. You look out the window today — sunny, cloudy, or rainy — and use that single snapshot to make your guess. You don't need to recall every day this month. Just now is enough.

That intuition powers one of the most useful ideas in all of mathematics: the Markov chain, named after the Russian mathematician Andrey Markov, who introduced the concept in 1906.

A Markov chain is a random process that jumps between states according to fixed probabilities. Its defining feature is the memoryless property (also called the Markov property): the probability of the next state depends only on the current state, not on any of the states that came before. The chain lives entirely in the present.

Despite this radical forgetfulness, Markov chains are extraordinarily powerful. Leave one running long enough and — under mild conditions — it settles into a stationary distribution: a stable set of probabilities that never changes, no matter where the chain started. The randomness hasn't vanished; it has just become perfectly predictable on average.

From search engine rankings to drug dosing models, from text prediction to quantum physics, the Markov chain is the engine under the hood.

Below is a three-state Markov chain: Sunny, Cloudy, and Rainy. Each state has fixed transition probabilities to the next day's weather. Click Step to advance one day, or Run to watch the chain evolve automatically.

The bar chart tracks how often the chain has visited each state. Press Run and watch the bars stabilize — that convergence is the stationary distribution revealing itself.

<div class="layout">
  <div class="left-panel">
    <div class="state-label">{{current_state}}</div>
    <div id="current-state" class="state-display sunny">☀ {{sunny}}</div>
    <div class="transition-box" id="transition-box">
      <div class="trans-title">{{transition_probs}}</div>
      <div id="trans-rows"></div>
    </div>
    <div class="step-count">{{day}} <span id="day-count">0</span> &nbsp;|&nbsp; {{steps_label}} <span id="step-count">0</span></div>
  </div>
  <div class="right-panel">
    <div class="chart-title">{{longrun_freq}}</div>
    <div id="chart" class="chart"></div>
    <div class="target-row" id="target-row"></div>
    <div class="legend">{{legend}}</div>
  </div>
</div>
<div class="btns">
  <button id="btn-step">{{btn_step}}</button>
  <button id="btn-run" class="accent">{{btn_run}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>
<div class="hint" id="hint">{{hint_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; font-size: 14px; }
.layout { display: flex; gap: 16px; align-items: flex-start; }
.left-panel { flex: 0 0 160px; display: flex; flex-direction: column; gap: 10px; }
.right-panel { flex: 1; }
.state-label { font-size: 11px; text-transform: uppercase; letter-spacing: .06em; color: #666; }
.state-display { font-size: 18px; font-weight: 700; padding: 10px 14px; border-radius: 10px;
                 text-align: center; transition: background .3s, color .3s; }
.state-display.sunny  { background: #fff3b0; color: #7a5a00; }
.state-display.cloudy { background: #dce8f0; color: #2d4a5e; }
.state-display.rainy  { background: #d0d8f8; color: #1a2580; }
.transition-box { background: #f5f7fa; border: 1px solid #dde3ea; border-radius: 8px; padding: 10px; }
.trans-title { font-size: 11px; color: #666; text-transform: uppercase; letter-spacing: .05em; margin-bottom: 6px; }
.trans-row { display: flex; justify-content: space-between; font-size: 13px; padding: 2px 0; }
.trans-pct { font-weight: 600; color: #1d3557; }
.step-count { font-size: 12px; color: #888; text-align: center; }
.chart-title { font-size: 11px; text-transform: uppercase; letter-spacing: .06em; color: #666; margin-bottom: 8px; }
.chart { display: flex; align-items: flex-end; gap: 12px; height: 140px; position: relative; }
.bar-group { flex: 1; display: flex; flex-direction: column; align-items: center; gap: 4px; }
.bar-wrap { width: 100%; height: 120px; display: flex; align-items: flex-end; position: relative; }
.bar { width: 100%; border-radius: 5px 5px 0 0; transition: height .25s; }
.bar.sunny  { background: #f4c430; }
.bar.cloudy { background: #7eafc9; }
.bar.rainy  { background: #5b6bcc; }
.target-line { position: absolute; left: 0; right: 0; height: 2px; background: #e63946; opacity: .75; transition: bottom .25s; }
.bar-lbl { font-size: 11px; color: #555; text-align: center; }
.bar-pct { font-size: 12px; font-weight: 700; color: #333; min-height: 1.2em; text-align: center; }
.target-row { display: flex; gap: 12px; margin-top: 4px; }
.target-cell { flex: 1; text-align: center; font-size: 11px; color: #e63946; font-weight: 600; }
.legend { font-size: 11px; color: #e63946; margin-top: 2px; }
.btns { display: flex; gap: 8px; margin-top: 12px; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .9rem; border-radius: 8px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.accent { background: #2a9d8f; border-color: #2a9d8f; }
button.ghost  { background: #fff; color: #1d3557; }
.hint { font-size: 12px; color: #666; margin-top: 8px; line-height: 1.5; }

// Code not found

No matter which state you start in, the long-run visit frequencies always converge to the same values. That is the stationary distribution at work: the chain's inevitable destiny, baked into its transition probabilities from the very beginning.

The power of Markov chains rests on three clean mathematical facts.

1. Stationary distributions exist (and are unique). For any ergodic chain — one that is irreducible (every state can reach every other) and aperiodic (no rigid cycling) — there is exactly one probability vector $\pi$ such that

$$\pi = \pi P$$

where $P$ is the transition matrix. This is a solved result, not an open problem: it follows from the Perron–Frobenius theorem for stochastic matrices, fully established by the early 20th century.

2. The chain converges to it. Starting from any initial distribution, repeated multiplication by $P$ drives the distribution toward $\pi$ exponentially fast. How fast is captured by the mixing time — the number of steps until the chain is within a chosen distance of $\pi$. For some chains this is polynomial in the number of states; for others it can be exponential (think a random walk on a long cycle).

3. Time averages equal space averages. By the ergodic theorem, the fraction of time the chain spends in state i converges almost surely to $\pi(i)$. You don't need to know $\pi$ analytically — running the chain long enough measures it. This is the foundation of Markov Chain Monte Carlo (MCMC), which lets computers sample from distributions that are too complex to write down explicitly.

The computational complexity picture: computing $\pi$ for a chain with n states reduces to solving a linear system — $O(n^{3})$ by Gaussian elimination, or faster with sparse methods. Estimating $\pi$ by simulation is even simpler but slower to converge. Neither task sits in NP-hard territory; Markov chain analysis is largely a domain where the mathematical structure makes problems tractable.

Compare this to P vs NP: rather than asking whether a solution exists, Markov chain theory asks how a distribution evolves — and the answer, uniquely, is always yes and always computable.

Once you see Markov chains, you find them everywhere:

• PageRank: Google's original algorithm models a random web surfer jumping between pages. The stationary distribution of that chain is the page rank — the chain's long-run visit frequency directly ranks the web.
• MCMC and Bayesian inference: Markov Chain Monte Carlo methods build chains whose stationary distribution is the posterior distribution you want to sample from. This unlocks Bayesian models that would otherwise be analytically intractable.
• Hidden Markov Models (HMMs): speech recognition, part-of-speech tagging, and DNA sequence analysis all rely on HMMs, where an underlying Markov chain emits observable signals. The Viterbi and Baum–Welch algorithms decode and learn these models efficiently.
• Queueing theory: call centers, packet-switched networks, and hospital wait times are modeled as Markov chains where arrivals and departures are memoryless — leading to exact formulas for average waiting times.
• Genetics and evolution: population genetics uses Markov chains to model genetic drift; the stationary distribution predicts allele frequencies over evolutionary time.
• Text generation: before large language models, n-gram models were Markov chains over words. Each word depended only on the previous n−1 words — simple but surprisingly fluent.

The Bayesian inference and PageRank articles on this site both connect back to Markov chains as their mathematical backbone.

Markov chains teach a counterintuitive lesson: forgetting the past is not a weakness. By refusing to carry history, a Markov chain becomes mathematically tractable in ways that history-dependent processes are not. And that tractability is repaid with interest — the stationary distribution, the ergodic theorem, and MCMC are among the most practically powerful results in all of applied mathematics.

The weather model in the demo settles into the same long-run frequencies every time, regardless of whether it started sunny or rainy. That convergence is not a coincidence or an approximation: it is a theorem, proven by Andrey Markov over a century ago, and verified on every random walk, every web surfer, and every MCMC sampler that has run since.

The next time you ask your phone for directions, receive a spam-filtered email, or see a machine-learning model trained with Bayesian methods, you are quietly benefiting from a chain that only ever cares about right now.