Stochastic Processes

In 1900, in Paris, Louis Bachelier modelled the price of a government bond as a random walk that, in the limit of many small steps, moves continuously. He derived the equation that governs the spread of its probability, the same diffusion equation that Einstein would derive for pollen grains in 1905. His examiner, Henri Poincaré, praised the work, but for half a century it was little read.

The mathematical object came from real analysis. In 1923 Norbert Wiener constructed a probability measure on the space of all continuous paths, proving that Brownian motion exists. Its paths are continuous but so jagged that they have no slope at any point. In 1931 Andrey Kolmogorov showed that the probabilities of any Markov process in continuous time obey two differential equations, joining random paths to the heat equation. Two years later he gave all of probability its axioms.

Calculus along a Brownian path still made no sense, because the path has no derivative. In 1944 Kiyosi Itô, who had developed his ideas at a government statistics office in Tokyo, defined the integral that makes it work. His chain rule has an extra term, because the square of a small Brownian step is not negligible: it is proportional to the time elapsed. In 2000 a sealed envelope that Wolfgang Doeblin had sent to the Paris Academy in 1940, shortly before he died as a soldier, was opened. It held a version of the same formula.

Markov's data from the first 20,000 letters of Eugene Onegin are simple enough to follow completely. He found 8,638 vowels and 11,362 consonants. A vowel was followed by another vowel 1,104 times, and a consonant by another consonant 3,827 times. So:

After a …	Next is a vowel	Next is a consonant
Vowel	$1104 / 8638 \approx 0.128$	0.872
Consonant	$7535 / 11362 \approx 0.663$	0.337

The letters are clearly not independent. If they were, a vowel would follow a vowel about 43% of the time, about 3,700 times in the text, not 1,104. Russian alternates. Treat the text as a two-state Markov chain with these transition probabilities. In the long run, the fraction $v$ of vowels must stay the same from one letter to the next: vowels arise from vowels at rate 0.128 and from consonants at rate 0.663, so

$$v = 0.128\,v + 0.663\,(1 - v) \quad\Longrightarrow\quad v = \frac{0.663}{1 - 0.128 + 0.663} \approx 0.432 .$$

This is the stationary distribution, and it matches the observed share of vowels, $8638 / 20000 = 0.432$. The chain, knowing only which letter class came last, reproduces the overall frequency exactly, as Markov's theorem says it should.

The same calculation ranks the web. Take three pages: A links to B and C, B links to C, and C links back to A. A surfer clicking links at random settles into spending 40% of the time on A, 20% on B and 40% on C. With PageRank's rule that the surfer jumps to a random page 15% of the time, the shares become about 38.8%, 21.5% and 39.7%. C, with two incoming links, edges ahead of A.

After 1950 the theory spread in every direction. Economists rediscovered Bachelier, and in 1973 Fischer Black and Myron Scholes, with Robert Merton, used Itô's calculus to price options, founding modern financial mathematics. In 1998 Sergey Brin and Larry Page ranked the web by the stationary distribution of a random surfer. Markov chains also power the samplers of Bayesian statistics, and physicists use random walks to model molecules, as in kinetic theory.

The theory is least complete where a process remembers its whole past. A walk that is forbidden to revisit its own path, the simplest model of a polymer, has resisted proof for more than seventy years in the dimensions where polymers live.