Markov Processes

A Markov process is a random process whose future depends on its present state but not on how it got there.

12 frameworks, from 1906 to today · Probability Theory · Mathematics

still a working view ended · each leads to its entry below

Overview

A Markov process is a random process whose future depends on its present state but not on how it got there1. If you know where the system is now, the past adds nothing. That single idea—called the Markov property—turns out to describe an astonishing range of things: the shuffling of cards, the diffusion of heat, the wanderings of a pollen grain in water, the queue at a bank, the spread of an epidemic, the price of a stock, and the decisions of a robot navigating a room. The history of Markov processes is the story of how mathematicians learned to make that idea precise, how physicists and engineers put it to work, and how a theory of pure chance became one of the most widely used computational tools in science.

Markov's Chains and the Birth of the Memoryless Idea

The story begins with Andrey Markov, a Russian mathematician working in St. Petersburg at the turn of the twentieth century. Markov was a student of Pafnuty Chebyshev and a colleague of Aleksandr Lyapunov, and he was drawn into a fierce contemporary debate about whether the law of large numbers required independence. The classical results of Jacob Bernoulli and Siméon Denis Poisson assumed that successive trials were independent, or nearly so. Markov suspected independence was too strong an assumption and set out to find a weaker one under which the law of large numbers would still hold1.

His answer, published in 1906, was the chain: a sequence of random outcomes in which each depends on the previous one but on nothing earlier1. To demonstrate that such dependence could still yield stable long-run averages, Markov analyzed a real dataset—the sequence of vowels and consonants in the first 20,000 letters of Pushkin's verse novel Eugene Onegin. Counting transitions between vowels and consonants, he computed the long-run proportion of vowels and showed it agreed with the observed frequency. This was both a mathematical proof and an empirical demonstration, and it established the finite-state Markov chain as a working object1.

The key concept Markov isolated was what later became known as ergodicity: under suitable conditions, a chain forgets its starting point, and the proportion of time spent in each state converges to a fixed long-run distribution regardless of where the chain began. For a two-state chain—say, weather that is rainy or sunny—the transition probabilities form a small table, and repeated multiplication of that table drives the system toward a stable mix. Markov's insight was that this convergence is a theorem, not an accident.

Kolmogorov, Analytic Methods, and the Continuous-Time Problem

For two decades the theory stayed largely combinatorial, concerned with discrete steps. The next leap came from another Russian, Andrey Kolmogorov, in the 1930s1. Kolmogorov had already rebuilt probability on measure-theoretic foundations in his 1933 monograph Grundbegriffe der Wahrscheinlichkeitsrechnung, and he turned his attention to processes that evolve in continuous time.

The problem was this: if a system can change state at any instant, how do you specify its law? You cannot list transition probabilities step by step. Kolmogorov's answer, developed in papers of 1931 and 1936, was analytic. He introduced the transition function $P(t, x, A)$—the probability of being in a set $A$ at time $t$ given a start at $x$—and showed that under regularity conditions it satisfies a system of differential equations1. These are now called the forward and backward Kolmogorov equations1. The forward equation, later identified with the physicist Adriaan Fokker and Max Planck's earlier work, describes how a probability distribution spreads over time; the backward equation describes how the expected value of a function of the future state depends on the starting point.

Kolmogorov's framework made the continuous-time Markov process a rigorous object and connected it to partial differential equations1. It also raised a subtle question: does specifying the instantaneous rates of transition (the generator) determine the process uniquely? The answer is not always yes, and the gap between the two—the possibility of "explosion" or of multiple processes sharing the same generator—became a central technical concern for decades.

Semigroups, Generators, and the Strong Markov Property

Kolmogorov's transition functions have an algebraic structure: running the process for time $s$ and then for time $t$ is the same as running it for $s+t$. This is the semigroup property, and it invited the machinery of functional analysis. In the 1940s and 1950s, mathematicians including Einar Hille, Kōsaku Yosida, and William Feller developed the theory of semigroups of operators, giving the generator a precise meaning as the derivative of the semigroup at time zero. Feller's work in particular classified which generators correspond to honest Markov processes, and the resulting "Feller processes" became a standard class.

A parallel refinement concerned the Markov property itself. The basic property says the future is independent of the past given the present. The strong Markov property extends this to random times—stopping times—such as the first moment a process hits a boundary. This stronger property is what makes it legitimate to "restart" a process at a hitting time, and it is essential for the deeper theory. It was established for Brownian motion by Paul Lévy in the 1930s and 1940s and systematized for general processes in the postwar decades.

Brownian Motion and the Diffusion Tradition

The most important Markov process is Brownian motion, and its history runs alongside the abstract theory1. In 1827 the botanist Robert Brown observed pollen grains jittering in water2. In 1905 Albert Einstein, unaware of Brown's observations, derived the statistical law governing such motion from the kinetic theory of molecules, and in 1908 Paul Langevin gave a complementary dynamical account. The mathematical object—a continuous path with independent, stationary Gaussian increments—was constructed rigorously by Norbert Wiener in 1923, which is why it is also called the Wiener process.

Brownian motion is Markov: its future increments depend only on its current position1. It is also a diffusion, meaning its paths are continuous and its generator is a second-order differential operator3. The connection between Markov processes and diffusion equations—the heat equation in particular—was made explicit by Kolmogorov and became a template1. The physicist's picture of a particle buffeted by molecules and the probabilist's picture of a random path turned out to be two views of one object, and this duality between probability and partial differential equations became a recurring theme.

Martingales and the Modern Synthesis

The mid-twentieth century brought a unifying language: martingales. A martingale is a process whose expected future value, given everything observed so far, equals its present value—the mathematical model of a fair game4. The concept was introduced by Paul Lévy in the 1930s and developed into a powerful theory by Joseph Doob in the 1940s and 1950s. Doob's Stochastic Processes (1953) showed that martingale methods could prove convergence theorems, optional stopping results, and inequalities that applied across the whole field.

For Markov processes, martingales provided a new characterization. A function of a Markov process is a martingale precisely when it solves the appropriate differential equation associated with the generator—a fact that links the probabilistic and analytic pictures tightly. This "martingale problem" formulation, developed by Daniel Stroock and S. R. S. Varadhan in the 1960s and 1970s, gave a way to define and analyze Markov processes through their generators without constructing paths directly, and it became a standard modern approach.

Potential Theory and the Probabilistic–Analytic Dictionary

A separate strand connected Markov processes to classical potential theory, the nineteenth-century theory of harmonic functions and electrostatic potentials. The link is intuitive: the probability that a random walker starting at a point exits a region through a particular boundary piece is a harmonic function of the starting point. Kakutani's theorem in the 1940s made this precise for Brownian motion, and in the 1950s and 1960s G. A. Hunt systematized a general "probabilistic potential theory" for Markov processes. The resulting dictionary translates analytic notions—harmonic functions, Green's functions, equilibrium measures—into probabilistic ones—exit distributions, expected occupation times, hitting probabilities—and back. This correspondence remains one of the most elegant bridges in mathematics.

Stochastic Calculus and Stochastic Differential Equations

The pathwise calculus for Brownian motion, developed by Kiyosi Itô in the 1940s and 1950s, transformed the study of diffusions. Itô defined an integral against Brownian motion and derived a chain rule—Itô's formula—that differs from the ordinary calculus by an extra term reflecting the infinite variation of Brownian paths. With this tool, one can write stochastic differential equations (SDEs) that describe a diffusion as a drift plus a noise term, and solve them.

The payoff for Markov theory was large. An SDE of the form $dX = b(X)\,dt + \sigma(X)\,dB$ defines a Markov process whose generator is a second-order operator built from $b$ and $\sigma$. This gave a constructive, flexible way to build diffusions and to connect them to physical models—the Langevin equation of 1908 is a precursor—and to problems in filtering, control, and mathematical finance. Itô's calculus also made precise the sense in which a diffusion solves a partial differential equation, via the Feynman–Kac formula, which expresses solutions of parabolic PDEs as expectations over random paths.

Computation: Markov Chain Monte Carlo

The theoretical edifice might have remained the province of specialists, but a computational idea brought Markov processes into everyday scientific practice. Markov chain Monte Carlo (MCMC) uses a Markov chain designed to have a desired probability distribution as its long-run (stationary) distribution; running the chain and recording states produces samples from that distribution5. The idea traces to Metropolis and colleagues at Los Alamos in 1953, who used it for statistical physics calculations, and it was generalized by W. K. Hastings in 1970.

MCMC became a revolution in the 1990s with the spread of Bayesian statistics and cheap computing. The Gibbs sampler, popularized by Stuart and Donald Geman in 1984 and by Alan Gelfand and Adrian Smith in 1990, and the Metropolis–Hastings algorithm made it possible to sample from complex, high-dimensional distributions that resisted direct calculation. The theoretical guarantee is exactly Markov's ergodicity: the chain converges to the target distribution, and the samples, though dependent, can be averaged. MCMC is now a standard tool in statistics, physics, biology, and machine learning.

Hidden States and Decisions

Two further developments turned Markov processes into modeling frameworks. The hidden Markov model (HMM), developed in the 1960s and 1970s in speech recognition and control engineering, posits an unobserved Markov chain whose states generate observable outputs; the task is to infer the hidden states from the observations. The Baum–Welch algorithm for training such models and the Viterbi algorithm for decoding them made HMMs practical, and they became central to speech recognition and bioinformatics.

The Markov decision process (MDP), formalized by Ronald Howard in 1960 and rooted in earlier work on dynamic programming by Richard Bellman in the 1950s, adds actions and rewards to the Markov framework: an agent chooses actions that influence transitions, and seeks a policy maximizing expected reward. Bellman's principle of optimality yields the Bellman equation, and solution methods—value iteration, policy iteration—follow. MDPs became the mathematical foundation of reinforcement learning, and through that, of much of modern artificial intelligence.

The Present

Markov process theory today is a mature but active field with several living traditions. The analytic tradition—semigroups, generators, Dirichlet forms—continues to classify and construct processes, especially in infinite-dimensional and non-reversible settings. The martingale and stochastic-analysis tradition provides the tools for SDEs, filtering, and mathematical finance. The ergodic tradition, with its roots in Markov's original question, studies convergence rates, mixing times, and the behavior of large systems, and it connects to statistical mechanics and to the analysis of algorithms. The computational tradition, from MCMC to reinforcement learning, drives applications across science and engineering.

Open questions remain. The classification of Markov processes with given generators is still not complete in full generality. Mixing-time bounds for complex chains are often hard to establish. The theory of Markov processes in random environments and on large networks continues to develop. And the interaction between Markov models and modern machine learning—diffusion models for image generation are built on Markov processes—has opened new directions. The memoryless assumption, once a technical convenience, has proved to be one of the most fertile simplifications in all of probability.

References

  1. Markov chain (introduction, Definition, History, Examples), Wikipedia
  2. Brownian motion (introduction, History), Wikipedia
  3. Diffusion process, Wikipedia
  4. Martingale (probability theory), Wikipedia
  5. Markov chain Monte Carlo, Wikipedia

The frameworks of Markov Processes

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1906-Present

    Markov chain

    How can dependence without independence still give stable long-run averages?

    Fly to its tower in Nousfarer

  2. 1923-Present

    Brownian motion

    What is the law of a particle jittering under molecular bombardment?

    Fly to its tower in Nousfarer

  3. 1931-Present

    Kolmogorov Analytic Theory of Continuous-Time Processes

    How do you specify a process that changes state at any instant?

    Fly to its tower in Nousfarer

  4. 1935-Present
  5. 1940-Present

    Martingale Theory and the Martingale Problem

    What can be said about processes that are fair games?

    Fly to its tower in Nousfarer

  6. 1940-Present

    Semigroup and Generator Theory

    Which operators generate honest Markov processes?

    Fly to its tower in Nousfarer

  7. 1944-Present

    Itô calculus

    How do you integrate against a random path?

    Fly to its tower in Nousfarer

  8. 1944-Present

    Probabilistic Potential Theory

    What do exit and hitting probabilities have to do with harmonic functions?

    Fly to its tower in Nousfarer

  9. 1953-Present

    Markov Chain Monte Carlo

    How can a random chain be made to sample a target distribution?

    Fly to its tower in Nousfarer

  10. 1957-Present

    Markov decision process

    How should one act when the next state depends only on the present?

    Fly to its tower in Nousfarer

  11. 1960-Present

    Hidden Markov model

    How can hidden states be inferred from noisy observations?

    Fly to its tower in Nousfarer

  12. 1970-Present

    Ergodic Theory and Mixing Times

    How fast does a random system forget where it started?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Markov chainBrownian motionKolmogorov Analytic Theory of Continu…Strong Markov Property and Stopping-T…Martingale Theory and the Martingale …Semigroup and Generator TheoryItô calculusProbabilistic Potential TheoryMarkov Chain Monte CarloMarkov decision processHidden Markov modelErgodic Theory and Mixing Times

Beyond the field

Where Markov Processes's ideas came from in other fields, and what they led to there: the strongest 12 of 60 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Markov Processes is a planet in Nousfarer

Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.

Land on Markov Processes

Related fields

Fields its ideas are linked to

More in Probability Theory

See where Markov Processes sits on the Map of Human Knowledge