Andrei Markov

Life and career

Andrei Andreyevich Markov was born in 1856 in Ryazan, a provincial Russian town, and moved as a child to St Petersburg, where he spent essentially his entire career. He had poor health and a limp from childhood, was an indifferent student in most subjects, and was conspicuously good at mathematics early. He entered St Petersburg University in 1874 and fell under the influence of Pafnuty Chebyshev, the dominant figure in Russian mathematics and the founder of what became the St Petersburg school of probability. Markov's doctoral work was on continued fractions and their application to moment problems — a topic that looks unrelated to his famous chains but is not, since the moment problem is the technical machinery behind Chebyshev's approach to limit theorems.

He stayed at the university, became a professor, and was elected to the Imperial Academy of Sciences. His mathematical output ranged over number theory, continued fractions, approximation theory, and probability, and he was, by all accounts, a difficult and combative colleague. He fought publicly and repeatedly with Pavel Nekrasov, a Moscow mathematician who had argued that the observed statistical regularity in social data proved that human acts must be independent, and therefore that free will was mathematically demonstrated. Markov thought this was nonsense, and he set out to refute it in the most direct way available: by constructing a sequence of *dependent* random variables that nonetheless obeys the law of large numbers. This is the origin of the Markov chain. It was, in a real sense, invented to win an argument about theology.

He was equally combative in politics. He was an outspoken opponent of the Tsarist regime's interference in academic life. When the Russian Orthodox Church excommunicated Tolstoy in 1901, Markov requested his own excommunication in protest, and eventually received it. He resigned or refused positions over political objections, and in 1907 he renounced his Academy chair in protest at the dissolution of the Duma while continuing to work.

The most-cited application of his own theory is characteristically odd. In 1913 he took the text of Pushkin's *Eugene Onegin*, counted twenty thousand successive characters by hand, classified each as vowel or consonant, and tabulated the transition frequencies to demonstrate that the sequence exhibits exactly the dependent-but-well-behaved structure his theory described. He did the same for a Aksakov text. This is, by any reasonable reading, the first statistical language model — a bigram model of Russian orthography, computed with pencil and paper to settle a mathematical point.

He continued working through the Revolution and the famine years that followed, teaching in difficult conditions, and died in Petrograd in 1922. His son, also Andrei Andreyevich Markov, became a significant mathematician in his own right in constructive mathematics and the theory of algorithms.

Key contributions

**The Markov property and Markov chains.** The definition is the contribution: a stochastic process in which the conditional distribution of the next state, given the entire history, depends only on the current state. Formally, P(X_{n+1} | X_n, ..., X_1) = P(X_{n+1} | X_n). This is a modeling assumption of extraordinary reach, because it is the weakest form of dependence that still permits a complete theory. Markov proved that for finite chains satisfying suitable connectivity conditions — irreducibility and aperiodicity, in modern terms — the chain converges to a unique stationary distribution regardless of where it started, and that time averages along a single trajectory converge to expectations under that stationary distribution. The law of large numbers and the central limit theorem survive dependence, provided the dependence is Markovian.

For a graduate reader the consequences are everywhere and are worth enumerating precisely because they look so different from one another. **Stationary distributions**: PageRank is the stationary distribution of a random walk on the web graph, nothing more. **Reverse-engineering the stationary distribution**: MCMC — Metropolis-Hastings, Gibbs sampling, Hamiltonian Monte Carlo — constructs a chain whose stationary distribution is a target posterior you cannot sample directly, then runs it. Every modern Bayesian computation is Markov's convergence theorem exploited backward. **Latent state**: hidden Markov models put a Markov chain underneath an observation process, giving the forward-backward algorithm, the Viterbi decoding, and Baum-Welch training that dominated speech recognition for thirty years. **Sequential decision-making**: Markov decision processes add actions and rewards to the state, producing the Bellman equation and the entire framework of reinforcement learning. **Sequence modeling**: n-gram language models are exactly his Eugene Onegin construction with a larger alphabet and a longer context, and the autoregressive factorization at the heart of modern language models is a Markov assumption over a very long window.

**Markov's inequality.** For a nonnegative random variable X and a > 0, P(X ≥ a) ≤ E[X]/a. It is a two-line proof and it is the base of the concentration-inequality pyramid: Chebyshev follows by applying it to (X - μ)², and Chernoff bounds by applying it to the moment generating function. Every generalization bound in statistical learning theory descends from this.

**The Gauss–Markov theorem.** Markov's contribution here is a sharpening and dissemination of Gauss's second, deeper argument: among linear unbiased estimators of the coefficients in a linear model with zero-mean, homoscedastic, uncorrelated errors, ordinary least squares has minimum variance — with no normality assumption anywhere. This is why OLS is defensible on data you have no reason to think is Gaussian, and it is the reason the theorem carries both names.

The limit of the whole framework is the same as its strength. The Markov property says the present screens off the past. When it doesn't — long-range dependence, latent slow variables, fractional processes, genuinely non-stationary environments — the theory gives you nothing, and the standard fix is to enlarge the state until the property holds again, which is either elegant or an admission of defeat depending on how large the state gets.

In battle

Markov's mean is 32.6 with a median of 28, three problems above 80 and seven above 70 — a mid-tier average concealing an unusually sharp specialty. His strongest showings are all the same problem wearing different clothes.

"The rank of every page" is his best at 90, and the profile is explicit that the debt is total: PageRank *is* the stationary distribution of a Markov chain over the web's link structure. He is capped just below the practitioners who actually built the iterative computation at scale, because he never touched a computer. "Decode the hidden path" (85) is the Viterbi algorithm over an HMM — his chain with a latent layer. "A thousand words, connected speech" (75) is HMM-based continuous speech recognition, the technology that ran the field for decades. "The parallel text is the teacher" (75) is statistical machine translation, whose alignment models are Markov chains over word positions. "The trend with a memory" (72) is autoregressive time-series modeling. "Compress the English novel" (70) is character-level statistical modeling of text, which is *literally* what he did to Pushkin in 1913, and his NLP average of 43.7 across six problems reflects that he has a genuine, underappreciated claim to the whole sequential-language tradition. "Sample from the impossible posterior" (66) is MCMC. The surprise on his sheet is "Why least squares, exactly?" at 86, driving a regression category average of 79.0 — the Gauss–Markov theorem, where he supplies the distribution-free optimality argument the problem actually demands. His RL average of 51.0 comes from MDPs being his object with a decision layer bolted on.

His losses share a single property: they are all problems with **no sequential or stochastic structure to exploit**. "Every interesting property is undecidable" (10) and "Let the machine find the proof" (10) are computability and automated deduction — symbolic logic, where a transition kernel buys nothing, and his computability average sits at 15.0. "Prune the game tree, provably" (10) is alpha-beta search: adversarial, deterministic, combinatorial, and the opponent's choices are emphatically not a fixed transition matrix. "Climb the yield surface" (10) is response-surface optimization and "The p-value reckoning" (10) is the replication-crisis critique of null hypothesis testing — a methodological and sociological argument he has no stake in. His floor is "Ship it to a hundred contributors" (8), open-source collaboration infrastructure, where the profile notes he has nothing transferable beyond generic rigor.

The instructive pattern is that Markov's failures are not really about era. He loses to logic and to adversaries, both of which existed in his lifetime as mathematical subjects — he simply worked in a different one. What he gives you is a licence to model dependence tractably, and that licence is worth an enormous amount when the world is a sequence of states and worth nothing when it is a proof, a game against an opponent, or a piece of engineering. Play him on anything that unfolds in time with limited memory: sequences, chains, sampling, latent state, ranking, decoding. Avoid him on decidability, adversarial search, and methodological critique.