Mathematics
Markov Chains and Their Application to Random Processes
Quick fact
Markov chains were invented by Russian mathematician Andrey Markov in 1906 to analyze the distribution of vowels and consonants in Pushkin's poem 'Eugene Onegin'—a purely literary puzzle that gave birth to a tool now used across science and engineering.
Why this is interesting
Have you ever wondered how a simple rule—like 'the next step depends only on where you are now'—can explain the behavior of a drunkard's walk, the spread of a rumor, or even how search engines rank web pages? This is the startling power of a Markov chain.
Read the full explanation
Understanding Markov Chains and Their Application to Random Processes
Imagine a frog hopping between lily pads in a pond. At each hop, the frog chooses its next pad based only on its current pad—it doesn't remember which pads it visited before. This is a Markov chain: a sequence of states (the pads) where the probability of moving to the next state depends only on the current state, not on the history of previous states. This memoryless property is known as the Markov property. To model such a system, you need a list of states and a set of transition probabilities: for every pair of states, the chance of moving from one to the other. You can visualize this as a directed graph with states as nodes and arrows labeled with probabilities. For example, a simple two-state model for weather: if it's sunny today, there's a 90% chance it's sunny tomorrow and 10% chance it rains; if it rains, there's a 50% chance of rain tomorrow and 50% chance of sun. The chain then evolves by repeatedly applying these probabilities. The beauty is the simplicity: you don't need to track the whole path; just the current state and the probability table.
A deeper explanation
The mechanism underlying a Markov chain is the concept of a stochastic process with the Markov property. Mathematically, a Markov chain is defined by a state space S, an initial distribution, and a transition probability matrix P where P(i,j) = Pr(X{n+1}=j | Xn=i). The evolution of the chain is governed by the Chapman–Kolmogorov equation, which allows computing the n-step transition probabilities as P^n. This matrix structure makes the chain tractable: the probability of being in each state after n steps is the initial vector multiplied by P^n. The key insight is that the long-term behavior of many Markov chains converges to a stationary distribution, a probability vector π that satisfies π = πP. This convergence occurs because the chain has the property of 'mixing'—it gradually forgets its starting point. This steady-state distribution reveals the long-run proportion of time spent in each state. It also makes Markov chains a foundational tool in simulations: you can generate a sequence of states whose long-run frequencies match a desired distribution, which is the core idea behind Markov Chain Monte Carlo (MCMC) methods. Thus, from a simple local rule, we derive global predictions and a mechanism for sampling complex distributions.