Markov Chains
In 1913, Andrey Markov counted 20,000 letters from Pushkin's Eugene Onegin to prove a rude point: randomness can have memory. He did not need the whole poem. He only needed the previous symbol class, vowel or consonant, to show that the next one was not independent.
A Markov chain is a machine for this kind of local memory. The next state depends on the current state, not the full path that got there. That small cut in history turns messy sequences into matrices.
The rule
The Markov property is the whole trick:
P(X_{t+1}=j | X_t=i, X_{t-1}, ..., X_0) = P(X_{t+1}=j | X_t=i)
The left side says: "given everything that happened." The right side says: "given only now." A chain becomes useful when that simplification is wrong enough to be visible, but right enough to calculate with.
The chain is stored as a transition matrix. If state A goes to B with probability 0.3, that number sits in row A, column B. Multiply the current distribution by the matrix once, and you get the next distribution. Multiply it 100 times, and you can watch the chain forget where it started.
For some chains, repeated steps settle into a stationary distribution:
pi = pi P
Here P is the transition matrix and pi is the long-run mix of states. The equation says the distribution does not move after one more step. That is why Markov chains show up in queues, genetics, language models, board games, search engines, and thermodynamics.
Where it shows up
| System | State | Transition | What the chain buys |
|---|---|---|---|
| Markov's Pushkin study, 1913 | vowel/consonant | next symbol class | evidence against independent letters |
| PageRank, 1998 | web page | random link click | page importance from link structure |
| Monopoly board analysis | square | dice roll plus rules | long-run landing rates |
| Hidden Markov speech models, 1970s-1990s | hidden phoneme state | acoustic sequence | speech from noisy sound |
| MCMC simulation | sample value | proposal step | hard integrals by wandering |
A clean example is a random walk. A particle at position x moves left or right with fixed probabilities. If the probabilities match, the expected position stays still, but the variance grows with time. This is the bridge from school-level probability to diffusion, Brownian motion, and concept entropy.
Google's original PageRank paper by Brin and Page in 1998 used a related idea: a web surfer moves from page to page by following links, with a small chance of jumping elsewhere. The stationary distribution becomes a ranking signal. The web became a matrix problem.
What is contested
The Markov assumption is often a lie. Human language cares about grammar, topic, rhythm, and memory longer than one symbol. A stock price cares about liquidity, news, market structure, and reflexive behavior. A biological cell carries history in gene expression and epigenetic state.
The live question is not "is the process Markov?" The sharper question is: "what state description makes the Markov approximation useful?" If the state is too small, the model forgets causes. If the state is too large, the matrix explodes.
Why this crosses realms
Markov chains sit under concept information theory because they turn surprise into conditional surprise. Shannon's 1948 paper uses Markov processes to model English text at different orders, moving from nonsense letters toward recognizable language as more local structure enters the model.
They also touch concept fermi paradox. A civilization spread model can be written as states and transitions: origin world, nearby star, colonized system, dead branch. The math will not answer whether anyone is out there, but it forces the question into rates, distances, and stopping probabilities.
Abhishek's take
What grabs me is that Markov's proof began as a fight about free will and independence, then became a tool for ranking the web. The move is very operator-like: throw away history, keep the part that changes the next action, and see whether the forecast improves. I trust Markov chains when the state definition is argued like a product spec, not treated like a math formality.
Key sources
- Andrey A. Markov, "An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains" (1913) - the Pushkin letter-count study that gave the concept its canonical origin.
- Claude E. Shannon, "A Mathematical Theory of Communication" (1948), Bell System Technical Journal - uses Markov processes to model information sources and English text.
- Sergey Brin and Lawrence Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine" (1998) - the PageRank random-surfer model.
- J. R. Norris, Markov Chains (1997) - compact mathematical treatment of finite and countable chains.
- Sheldon M. Ross, Introduction to Probability Models (first edition 1972) - applied entry point for queues, random walks, and stochastic models.
Tags: #markov-chains #probability #stochastic-processes #information-theory #matrices