Markov chain

Lore & Background

He was motivated by a disagreement with Pavel Nekrasov, who claimed independence was necessary for the weak law of large numbers. Markov showed that under certain conditions the average outcomes of a Markov chain would converge to a fixed vector, proving a weak law of large numbers without the independence assumption. He later used Markov chains to study the distribution of vowels in Alexander Pushkin's Eugene Onegin and proved a central limit theorem for such chains. Continuous-time Markov processes were discovered earlier in the form of the Poisson process. Andrey Kolmogorov developed a large part of the early theory of continuous-time Markov processes in a 1931 paper, partly inspired by Louis Bachelier's work on stock market fluctuations and Norbert Wiener's work on Brownian movement. Other contributors include William Feller starting in the 1930s and Eugene Dynkin starting in the 1950s.

Reader's Guide

Markov chains provide the basis for general stochastic simulation methods known as Markov chain Monte Carlo, used for simulating sampling from complex probability distributions. They have found application in areas including Bayesian statistics, biology, chemistry, economics, finance, information theory, physics, signal processing, and speech processing. The Markov property—that predictions based solely on the present state are as good as those using the full history—makes these models powerful for real-world processes where memory is limited. The changes of state are called transitions, and the probabilities associated with them are transition probabilities. A process is characterized by a state space, a transition matrix, and an initial state or distribution. While the time parameter is usually discrete, the state space may be finite, countably infinite, or continuous, though many applications employ finite or countably infinite state spaces for simpler statistical analysis.

Did You Know?

• Markov used Markov chains to study the distribution of vowels in Alexander Pushkin's Eugene Onegin.
• Continuous-time Markov processes were discovered long before Markov's work in the form of the Poisson process.

Etymology and the Birth of a Concept

The English word "stochastic" carries a surprisingly old pedigree. Its earliest recorded appearance dates to 1662, functioning as an adjective meaning "pertaining to conjecturing," rooted in a Greek term that conveyed the idea of aiming at a target or making a guess. The concept gained formal mathematical weight when Jakob Bernoulli, in his landmark 1713 Latin treatise Ars Conjectandi, paired the title with the phrase "sive Stochastice," effectively branding probability as the art of stochastics. Decades later, in 1917, the statistician Ladislaus Bortkiewicz revived the term in German as "Stochastik," explicitly linking it to randomness. The modern compound "stochastic process" entered English-language literature in 1934 through a paper by Joseph L. Doob, who credited Aleksandr Khinchin's German-language use of "stochastischer Prozeß" that same year, though Andrey Kolmogorov had employed the German form as early as 1931. This layered genealogy shows how a simple Greek notion of guessing evolved into a precise technical label over nearly three centuries.

The Heroic Decade and Mathematical Architecture

The 1930s stand as what Harald Cramér later called the "heroic period of mathematical probability theory." During those years, Aleksandr Khinchin delivered the first rigorous mathematical definition of a stochastic process, framing it as a family of random variables indexed along the real line. His work was joined by a remarkable constellation of contributors: Andrey Kolmogorov, Joseph Doob, William Feller, Maurice Fréchet, Paul Lévy, Wolfgang Doeblin, and Cramér himself all pushed the foundations forward. The theoretical edifice they built continues to generate active research in both pure theory and applied settings. Within this architecture, the term "stochastic" has spawned a rich vocabulary of related objects. A stochastic matrix, for instance, encodes the transition structure of a Markov process, while stochastic calculus extends the tools of differential equations and integration to processes such as the Wiener process, better known as Brownian motion. The breadth of these constructions underscores how a single modeling idea—describing systems through probability distributions rather than fixed outcomes—can branch into an entire subdiscipline.

Monte Carlo and the Physics Revolution

In physics, the most celebrated stochastic technique is the Monte Carlo method, named for the casino's association with chance. Stanisław Ulam, Enrico Fermi, John von Neumann, and Nicholas Metropolis brought the approach to prominence by exploiting randomness and repetitive sampling to tackle problems that resisted deterministic solution. Fermi's pioneering 1930s application, in which he estimated properties of the newly discovered neutron using a random method, is often cited as the earliest landmark. The method became indispensable to the Manhattan Project's simulations, yet the era's limited computing hardware constrained its depth. Only after electronic computers emerged from 1945 onward could researchers explore Monte Carlo techniques in earnest. By the 1950s, Los Alamos scientists were deploying them in early hydrogen-bomb research, and the RAND Corporation together with the U.S. Air Force helped disseminate the methods across physics, physical chemistry, and operations research. A practical byproduct of this demand was the rapid development of pseudorandom number generators, which replaced slow tables of random digits and made large-scale stochastic simulation feasible.

From Pollen Grains to Creative Sparks

Stochastic thinking reaches far beyond the mathematics classroom. In biology, the introduction of controlled random noise—known as stochastic resonance—has been shown to sharpen internal feedback loops governing balance and vestibular communication, offering tangible benefits to diabetic and stroke patients struggling with equilibrium. At the molecular level, gene expression itself carries a stochastic signature: the random collisions of RNA polymerase binding and unbinding at a promoter drive transcriptional bursts and cell-to-cell variability that follow super-Poissonian distributions, all riding on the Brownian motion of molecules in solution. In computer science, stochastic ray tracing applies Monte Carlo sampling to 3D graphics, while artificial intelligence harnesses probabilistic methods in simulated annealing, genetic algorithms, and stochastic neural networks. Even the creative act of scientific discovery, as David Simonton argued in 2003, may be a constrained stochastic process, with new theories emerging partly through random combinatorial steps. The unifying thread is that randomness, far from being mere noise, often structures the very mechanisms by which complex systems operate.