A Question of Free Will

The St. Petersburg-Moscow Divide

In the early 20th century, Russian mathematics was split between two schools. St. Petersburg, led by Andrey Markov, championed rigor and proof. Moscow, which included Pavel Nekrasov, sometimes blended math with theology. This philosophical divide set the stage for a consequential feud.

The Feud

Nekrasov, a theologian by training, claimed that for the Law of Large Numbers (the principle that averages stabilize over time) to hold, the underlying events *must* be independent. He used this to argue that statistical regularities in society (like crime rates) were proof of individual free will. Markov, an atheist and mathematical purist, found this absurd. He saw it as a gross misuse of mathematics to prove a theological doctrine.

"Thus, independence of quantities does not constitute a necessary condition for the existence of the law of large numbers."
- Andrey Markov, 1906

The Spiteful Proof

Motivated by disdain, Markov set out to create an irrefutable counterexample. In 1906, he devised a system of *dependent* events, where the outcome of each event is linked to the one preceding it. This was the first formal description of a Markov chain. He proved the Law of Large Numbers still held, shattering Nekrasov's argument. The Markov chain wasn't discovered; it was invented as a polemical device, a weapon forged from intellectual animosity.

To further demonstrate the real-world applicability of his concept, in 1913 Markov conducted the first-ever statistical analysis of a literary text, painstakingly counting the sequence of vowels and consonants in the first 20,000 letters of Alexander Pushkin's classic novel *Eugene Onegin*. He showed that even though the letters were clearly dependent (a vowel is more likely to be followed by a consonant), their long-run frequencies converged to stable probabilities, just as his theory predicted.

The Mathematics of Memorylessness

At its core, a Markov chain is a process that is "memoryless." The probability of transitioning to a future state depends *only* on its current state, not the sequence of states that preceded it. Think of Monopoly: your next move depends only on your current square and your dice roll, not how you got to that square.

The Mathematical Machinery

The mechanics of a Markov chain are described by its states and the transition probabilities between them. These probabilities are organized into a square Transition Matrix (P), where the entry in row *i* and column *j* gives the probability of moving from state *i* to state *j*. This matrix allows for powerful calculations: the probability of transitioning from state *i* to state *j* in exactly *k* steps is given by the corresponding entry in the matrix product $P^k$.

For many applications, the most important question is what happens to the system after many steps. If a chain is irreducible (you can get from any state to any other) and aperiodic (it doesn't get stuck in deterministic cycles), it will eventually settle into a long-term equilibrium known as a stationary distribution. This is a probability distribution across the states that remains unchanged when the transition matrix is applied to it. It represents the long-run average time the system spends in each state.

The Limits of Memorylessness

The power of the Markov chain lies in its simplifying assumption of memorylessness. However, this is also its greatest weakness. The model fails in real-world systems where the "present state" cannot realistically encode all relevant history. In financial markets, for example, long-term trends and investor memory influence prices. In language, the meaning of a word often depends on a context established many sentences earlier. Overcoming this limitation has been a primary driver of innovation in fields like AI.

From Solitaire to Superbombs

The Monte Carlo Method

During the Manhattan Project, physicists needed to calculate the "critical mass" of uranium. This depended on the probabilistic behavior of trillions of neutrons. Stanislaw Ulam, inspired by playing solitaire, realized they could simulate the random "walk" of millions of individual neutrons. Each neutron's path—a sequence of scatterings, absorptions, or fissions—is a Markov chain. The state of a neutron is its position, energy, and direction. A "step" is its journey to the next interaction, where the outcome (scatter, capture, or fission) is chosen probabilistically. By averaging millions of these simulated chains, they could predict the macroscopic behavior of the system, a technique they codenamed the Monte Carlo method.

Organizing the Infinite Library: Google's PageRank

In the 90s, Larry Page and Sergey Brin modeled the web as a giant Markov chain. Each webpage is a state, and each hyperlink is a transition. Their PageRank algorithm simulates a "random surfer" who clicks links. A page's importance (its rank) is determined by the amount of time the surfer spends on it in the long run. This is the stationary distribution of the web's Markov chain.

Breaking the Chain: Spider Traps & Dead Ends

The real web, however, is messy. It contains dead ends (pages with no outgoing links) and spider traps (groups of pages that only link to each other). A random surfer would get stuck in these, breaking the model. The ingenious solution was the damping factor: 85% of the time the surfer follows a link, but 15% of the time they get "bored" and teleport to a completely random page on the web. This fiction ensures the chain is irreducible and aperiodic, guaranteeing a meaningful stationary distribution (PageRank) can be calculated.

The Ghost in the Machine: AI & Language

The history of Natural Language Processing (NLP) is a story of escaping the limitations of the Markov property. Early models, called n-grams, were simple Markov chains that predicted the next word based on the previous few words. They had a very short memory.

The Markovian Bottleneck

N-gram models suffered from a fixed context window, making them incapable of capturing long-range dependencies (e.g., subject-verb agreement in a long sentence). They also suffered from data sparsity, as the number of possible word combinations grows exponentially, making it impossible to observe them all in training data.

Escaping the Chain: RNNs and LSTMs

The first major attempt to break free was the Recurrent Neural Network (RNN), which maintains a "hidden state" as a compressed summary of the past. However, these suffered from the vanishing gradient problem, where the signal needed for learning would fade over long sequences. The Long Short-Term Memory (LSTM) network improved on this with a system of "gates" to better control memory, but it was still slow and sequential.

The Transformer Revolution: Attention is All You Need

The breakthrough came with the Transformer architecture, which abandoned recurrence for a self-attention mechanism. This allows the model to directly access and weigh the importance of *all* previous words simultaneously, solving the long-range dependency problem and enabling massive parallelization. While not a simple Markov chain, a Transformer can be seen as a more complex version where the transition rules change at every single step based on the entire context.

Modern Echoes: AI Model Collapse

A new challenge has emerged that can be framed in Markovian terms: model collapse. This occurs when generative models are trained on data produced by other models. This feedback loop causes the models to forget rare events and converge towards a simplified, distorted, and repetitive version of reality—a degenerative Markov chain converging to a poor stationary distribution.

The Devil's Picture Book

How many times must you shuffle a deck of cards to make it truly random? This is a classic Markov chain problem. The "state" is one of the $52!$ (an 8 with 67 zeros) possible orderings of the deck. A shuffle is a transition. The deck is random when every ordering is equally likely.

Mathematicians Persi Diaconis and Dave Bayer proved that for a standard riffle shuffle, this process exhibits a sharp "cutoff" phenomenon. The deck remains highly ordered for the first few shuffles, and then rapidly becomes random. Their calculations showed that seven shuffles are necessary and sufficient to make the deck random enough for practical purposes.

The Secret of Rising Sequences

The genius of the Bayer-Diaconis proof was simplifying the problem. Instead of tracking all $52!$ permutations, they showed that the randomness of the deck could be determined by a single property: its number of rising sequences. A rising sequence is a maximal subsequence of cards that remains in its original relative order. This insight compressed the state space from an intractable number to a maximum of just 52, making the calculation possible.