Probability Theory1906foundational10 min read

Extension of the Law of Large Numbers to Dependent Quantities

توسيع قانون الأعداد الكبيرة ليشمل الكمّيات المترابطة

Markov, A. A. — Bulletin of the Society of Physics‑Mathematics, Kazan

The problem

The classical law of large numbers, as proved by Bernoulli and refined by Chebyshev, required that the random variables be independent of one another. Yet most real-world sequences — weather, stock prices, letters in a text — are not independent: what happens next depends on what happened before. Without independence, no theorem guaranteed that long-run averages converge, leaving an enormous class of practical phenomena outside the reach of theory.

The contribution

Markov introduced sequences of random variables where each variable depends only on the one immediately before it — what we now call Markov chains. He proved that the law of large numbers still holds for these dependent sequences: long-run averages converge even when the variables are correlated, provided the chain is ergodic. The key idea is the , which encodes how the system jumps between states. Markov showed that powers of this matrix converge to a unique , making the chain's long-run behavior predictable.

The impact

Markov chains became a cornerstone of modern probability, statistics, and computer science. Hidden Markov Models power speech recognition and bioinformatics. (MCMC) methods enable Bayesian in high-dimensional spaces. PageRank — the algorithm behind Google Search — is a Markov chain on the web graph. ARIMA time-series models, reinforcement learning, queueing theory, and molecular simulation all rest on Markov's 1906 insight that dependence need not defeat the law of large numbers.

Imagine a cat that naps in one of three spots — the sofa, the windowsill, or the bed. Where she sleeps tonight depends only on where she slept last night, not on any earlier choices. The sofa cat usually stays on the sofa, but sometimes wanders to the windowsill; the windowsill cat often moves to the bed; the bed cat nearly always goes back to the sofa.

If you track her for a year, you'll find she spends roughly fixed percentages of nights in each spot — say 50% sofa, 30% windowsill, 20% bed — regardless of where she started. That stable pattern is the stationary , and Markov proved it always emerges when the chain of choices is well-connected.

The problem: independence was unrealistic

Before Markov, the law of large numbers applied only to independent trials — coin flips, dice rolls, measurements with no memory. Chebyshev and Bernoulli had shown that averaging many independent random variables produces a result close to the expected value, but their proofs broke down the moment one trial influenced the next.

Yet dependency is everywhere. In language, the letter "q" is almost always followed by "u". In weather, a storm today makes a storm tomorrow more likely. In finance, a volatile day tends to cluster with other volatile days. All of these are sequences where the future depends on the present — and nobody had proved that their averages behave predictably.

The key idea: memory of length one

Markov's breakthrough was a restriction that is both simple and surprisingly powerful. He considered sequences of random variables where the probability of the next value depends only on the current value — not on how the system arrived there. This single condition is called the Markov property, and a satisfying it is a Markov chain.

Think of it as a board game: your next move depends on which square you are standing on right now, not on the path that brought you there. The entire history is compressed into one piece of information — your current .

P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)

The Markov property — the future depends only on the present — The probability of moving to state j at the next step depends only on the current state i, not on any earlier states. This is the defining axiom of a Markov chain.

Open in Lab

Click any state to set the starting position. Notice the next-step probabilities depend only on where you are now, not on how you got there.

The demo wakes as you arrive…

The transition matrix: a map of all possibilities

A Markov chain with $n$ states is fully described by an $n \times n$ transition matrix $P$ , where entry $P_{ij}$ is the probability of jumping from state $i$ to state $j$ in one step. Every row sums to 1 because the system must go somewhere.

Think of the matrix as a spreadsheet: each row is a state you might be in, each column is a state you might go to, and the number in the cell is the probability of that specific move. The matrix encodes all the dynamics of the chain — once you know $P$ and your starting state, everything about the chain's future behavior is determined.

P = \begin{pmatrix} P_{11} & P_{12} & \cdots & P_{1n} \\ P_{21} & P_{22} & \cdots & P_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ P_{n1} & P_{n2} & \cdots & P_{nn} \end{pmatrix}, \quad \sum_{j=1}^{n} P_{ij} = 1 \;\;\forall\, i

Transition matrix — each row is a probability distribution over next states — P_ij is the probability of jumping from state i to state j. Each row sums to 1 because from any state the system must transition somewhere (possibly back to the same state).

Open in Lab

Edit any cell in the matrix and watch the state diagram update. Each row must sum to 1.

The demo wakes as you arrive…

Multi-step transitions and the Chapman–Kolmogorov equation

What is the probability of being in state $j$ after $m$ steps? The answer is beautifully simple: raise the transition matrix to the power $m$ . The entry $(P^m)_{ij}$ gives exactly the $m$ -step transition probability from $i$ to $j$ .

This works because of the Chapman–Kolmogorov equation: to go from $i$ to $j$ in $m + n$ steps, you can pass through any intermediate state $k$ at step $m$ , and the probabilities multiply and sum. In matrix language, this is just $P^{m+n} = P^m \cdot P^n$ — matrix multiplication naturally encodes the "sum over all intermediate paths" logic.

(P^{m+n})_{ij} = \sum_{k} (P^m)_{ik} \cdot (P^n)_{kj}

Chapman–Kolmogorov equation — multi-step probabilities decompose — The m+n step probability from i to j equals the sum over all intermediate states k of the m-step probability from i to k times the n-step probability from k to j.

Open in Lab

Step through matrix powers. Watch how the rows of P^m become increasingly similar — the chain is forgetting its starting state.

The demo wakes as you arrive…

The stationary distribution: where the chain settles

The most remarkable fact about ergodic Markov chains is that they converge. No matter what state you start in, the probability of being in each state after many steps approaches a fixed $\pi$ called the stationary distribution. This vector satisfies $\pi = \pi P$ — once you reach the stationary distribution, applying the transition matrix does not change it. It is a fixed point.

The physical intuition is like a river delta: water can enter from any tributary, but after flowing long enough, the fraction of water in each channel stabilizes. The stationary distribution tells you the long-run fraction of time the chain spends in each state.

\pi = \pi P, \quad \sum_{i} \pi_i = 1, \quad \pi_i \geq 0

Stationary distribution — the fixed point of the transition matrix — The row vector π multiplied by P gives π back. The components sum to 1 and are non-negative. π_i is the long-run fraction of time spent in state i.

Open in Lab

Pick any starting distribution and watch it converge to the unique stationary distribution as you increase the number of steps.

The demo wakes as you arrive…

Ergodicity: when does convergence happen?

Not every Markov chain converges to a stationary distribution. requires ergodicity, which needs two properties:

Irreducibility — every state can be reached from every other state. No part of the chain is isolated. Think of a road network: if every city is reachable from every other city (perhaps through intermediate stops), the network is irreducible.
Aperiodicity — the chain does not get trapped in cycles. If a state can only be revisited at intervals of exactly $d > 1$ steps, the chain is periodic and its probabilities oscillate instead of converging.

When both conditions hold, the chain is ergodic: it has a unique stationary distribution, and every initial distribution converges to it. This is the ergodic theorem for Markov chains, and it is what Markov proved in his 1906 paper.

Open in Lab

Toggle between an ergodic chain (converges) and a periodic chain (oscillates forever). Watch how the distribution behaves over time.

The demo wakes as you arrive…

Markov's proof strategy

Markov's proof elegantly combined Chebyshev's inequality with the structure of the transition matrix. The key steps were:

First, he showed that the $m$ -th power of the transition matrix converges as $m$ grows: every row approaches the same stationary distribution $\pi$ . This means the chain "forgets" its starting state.

Second, he used the convergence of $P^m$ to bound the of the time-average $\bar{X}_n = \frac{1}{n}\sum_{t=1}^{n} X_t$ . Even though consecutive terms are correlated, the correlations decay fast enough (because $P^m \to \pi$ ) that the variance of the average shrinks as $O(1/n)$ .

Finally, Chebyshev's inequality turns the shrinking variance into a convergence guarantee: $P(|\bar{X}_n - \mu| > \epsilon) \to 0$ as $n \to \infty$ . The law of large numbers holds for Markov chains.

The same idea in code

Simulating a Markov chain and verifying the law of large numberspython

Simplified to show the idea — not the real implementation.

import numpy as np

# Transition matrix: 3 states (Sunny, Cloudy, Rainy)
P = np.array([
    [0.7, 0.2, 0.1],   # Sunny  → next state
    [0.3, 0.4, 0.3],   # Cloudy → next state
    [0.2, 0.3, 0.5],   # Rainy  → next state
])

def simulate_chain(P, start, n_steps):
    """Run a Markov chain for n_steps from a given start state."""
    states = [start]
    for _ in range(n_steps):
        current = states[-1]
        next_state = np.random.choice(len(P), p=P[current])
        states.append(next_state)
    return states

# Simulate 100,000 steps starting from state 0 (Sunny)
chain = simulate_chain(P, start=0, n_steps=100_000)

# Empirical fraction of time in each state
counts = np.bincount(chain, minlength=3)
empirical = counts / len(chain)

# Stationary distribution: solve π = πP (left eigenvector for eigenvalue 1)
eigenvalues, eigenvectors = np.linalg.eig(P.T)
idx = np.argmin(np.abs(eigenvalues - 1.0))
pi = np.real(eigenvectors[:, idx])
pi = pi / pi.sum()  # normalize

print(f"Empirical:   {empirical}")      # ≈ [0.44, 0.28, 0.28]
print(f"Stationary:  {pi}")              # exact: [0.44, 0.28, 0.28]
# They match — the law of large numbers works for Markov chains!

Applications that shaped modern AI

Markov's seemingly abstract idea — chains of dependent random variables — turns out to be the backbone of an enormous range of technologies:

Hidden Markov Models (HMMs) extend Markov chains by assuming the states are hidden and only emit observable signals. Speech recognition systems (before ) modeled phoneme sequences as HMMs. Gene finding in bioinformatics uses HMMs to detect coding regions in DNA.

Markov Chain Monte Carlo (MCMC) methods construct a Markov chain whose stationary distribution is the target distribution you want to sample from. This made Bayesian inference tractable in high-dimensional spaces — arguably the most important computational advance in statistics.

ARIMA models for Time Series Forecasting embed autoregressive structure that is a direct descendant of Markov's framework, applied to economic and financial data.

PageRank models a web surfer as a Markov chain: at each page, the surfer clicks a random link. The stationary distribution ranks pages by importance — this is the algorithm that launched Google.

Open in Lab

Build your own Markov chain. Add states, draw transitions, and simulate random walks to see where the chain spends its time.

The demo wakes as you arrive…

Why it mattered

1713
Bernoulli's Law of Large Numbers
Jacob Bernoulli proved the first version of the law of large numbers for independent Bernoulli trials, showing sample proportions converge to true probabilities.
1867
Chebyshev's Inequality
Chebyshev provided a general proof of the weak law of large numbers using his inequality, but still required independence.
1906
Markov's Extension
Markov proved the law of large numbers for dependent variables — specifically for what we now call Markov chains. The independence barrier was broken.
1913
Markov's Text Analysis
Markov analyzed the alternation of vowels and consonants in Pushkin's Eugene Onegin — the first practical application of Markov chains, and an early example of computational linguistics.
1953
Metropolis Algorithm (MCMC)
Metropolis et al. introduced the first MCMC algorithm, using Markov chains to sample from complex distributions in physics simulations.
1966
Baum–Welch Algorithm for HMMs
The forward-backward algorithm enabled training Hidden Markov Models, which later powered speech recognition and bioinformatics.
1998
PageRank
Brin and Page modeled web surfing as a Markov chain, ranking pages by the stationary distribution. This algorithm founded Google.

From a twelve-page paper in a Kazan bulletin, Markov launched a mathematical framework that now underpins speech recognition, web search, Bayesian computation, financial modeling, and the training loops of modern AI. Every time a system reasons about sequential uncertainty — what word comes next, which page to rank higher, how to sample a posterior — Markov's chains are at work.

CitationMarkov, A. A.. Extension of the Law of Large Numbers to Dependent Quantities. Bulletin of the Society of Physics‑Mathematics, Kazan, 1906.

Terms in this paper

Markov Chainسلسلة ماركوف الاحتمالية
Transition Probabilityاحتمال الانتقال
Stateالحالة
Stationary Distributionالتوزيع المستقر
Convergenceالتقارب الحسابي
Probabilityالاحتمالية
Distributionالتوزيع الإحصائي
Stochastic Processesالعمليات التصادفية
Hidden Markov Modelنموذج ماركوف المخفي
Monte Carloأساليب محاكاة مونت كارلو