Andrey Kolmogorov

How to use this course

Andrey Kolmogorov worked in more fields than almost any mathematician of the twentieth century: real analysis, logic, probability, statistics, fluid mechanics, dynamical systems, approximation theory, information theory and the theory of algorithms. A pattern runs through this range. He would enter a field, find the one or two ideas that organized it, prove the central theorem, and leave the details to his students. Many of those students became leaders of their own fields.

Each technical lesson opens with a paragraph for the general reader in italics, then gives precise statements, proof sketches and exercises with folded solutions. The lessons follow the order in which Kolmogorov took up each subject, from his student work in analysis (1922) to algorithmic complexity (1965).

Timeline

Tambov and Tunoshna, 1903–1920

Andrey Nikolaevich Kolmogorov was born in Tambov on 25 April 1903. The family had no roots there: his mother, Maria Yakovlevna Kolmogorova, was travelling when she gave birth, and she died in childbirth. She was unmarried. His father is usually identified as Nikolai Matveyevich Kataev, an agronomist and the son of a priest, who had been exiled for political activity and who disappeared in 1919 during the Civil War. The boy took his mother’s surname.

He grew up in the house of his maternal grandfather, Yakov Stepanovich Kolmogorov, at Tunoshna near Yaroslavl, cared for by his mother’s sisters. One of them, Vera Yakovlevna, adopted him and remained his closest family until her death in 1950. The aunts educated him at home and produced a journal, The Swallow of Spring. Kolmogorov edited its mathematical section as a small child. He later dated his love of mathematics to the moment, at about six, when he noticed that \(1=1^2\), \(1+3=2^2\), \(1+3+5=3^2\), and so on.

In 1910 his aunt moved with him to Moscow, where he went to school. The Revolution and Civil War interrupted everything. For a time he worked as a conductor on the railway and, in his free hours, wrote a treatise on Newton’s laws of mechanics. He finished school in 1920.

Moscow and Luzitania, 1920–1925

In 1920 Kolmogorov entered Moscow State University. He also enrolled at the Mendeleev Institute of Chemical Technology, intending to study metallurgy, and attended the history seminar of Sergei Bakhrushin. His first research paper was in history: a study of landholding in medieval Novgorod based on tax records.

Moscow mathematics at the time revolved around Nikolai Luzin and his school of real-function theory, nicknamed Luzitania. Its members included Pavel Alexandrov, Pavel Urysohn, Mikhail Suslin and Aleksandr Khinchin. In 1922 Kolmogorov, still an undergraduate, constructed an integrable function whose Fourier series diverges almost everywhere. The result was a sensation, and it made him Luzin’s student. Lesson 04 describes it.

In the same years he taught at an experimental school run by the People’s Commissariat for Education. He enjoyed the work, and the habit of teaching children stayed with him. In 1925 he published a paper on the principle of the excluded middle, one of the first serious studies of intuitionistic logic, and his first paper in probability, written with Khinchin, on series of independent random variables. He graduated that year and became a research student under Luzin.

The road to the Grundbegriffe, 1925–1933

Between 1925 and 1929 Kolmogorov moved from real functions to probability, carrying measure theory with him. His papers on sums of independent variables (1928, 1929) settled when a random series converges and proved the law of the iterated logarithm in general form. He finished his doctorate in 1929 and obtained a post at the university’s Institute of Mathematics and Mechanics.

That summer he set out with Pavel Alexandrov, another student of Luzin, on a boat journey down the Volga, then across the Caucasus to Lake Sevan in Armenia. On the trip Alexandrov worked on topology and Kolmogorov on the analytic theory of Markov processes. The friendship that began there lasted 53 years. The two men shared a home from 1929, and in 1935 they acquired an old house at Komarovka, outside Moscow, where they lived for much of each week, received students and visitors, and kept a large library. Several historians have concluded that the relationship was also romantic; neither man said so publicly.

In 1930 and 1931 Kolmogorov travelled abroad for the first time. He made scientific contacts in Göttingen, the centre built by David Hilbert, visited Munich, and in Paris discussed probability with Paul Lévy. The long paper Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung (1931) founded the theory of Markov processes in continuous time. He became a professor at Moscow in 1931. In 1933 Springer published his short monograph Grundbegriffe der Wahrscheinlichkeitsrechnung, which placed probability on the axioms of measure theory. It ended a long debate about what probability is, at least for mathematicians, and every graduate course in the subject still begins from it.

Divergent Fourier series and intuitionistic logic

For the general reader. A Fourier series writes a function as a sum of sine waves. For well-behaved functions the sum converges back to the function. At nineteen Kolmogorov showed that for merely integrable functions the series can fail everywhere at once. Three years later he turned to logic and showed how classical reasoning can be translated into the stricter reasoning of the intuitionists.

Partial sums

For \(f\in L^1(\mathbb T)\), \(\mathbb T=\mathbb R/2\pi\mathbb Z\), let \(\hat f(k)=\frac1{2\pi}\int_{-\pi}^{\pi}f(t)e^{-ikt}\,dt\) and \(S_nf(x)=\sum_{|k|\le n}\hat f(k)e^{ikx}\). Then \(S_nf=f*D_n\) with the Dirichlet kernel

The unbounded \(L^1\) norms (the Lebesgue constants) are the source of all the trouble.

Idea of the construction

Spread a unit mass over \(m\) nearly equally spaced points and smooth it with Fejér kernels. The result is a non-negative trigonometric polynomial \(P_m\) with \(\|P_m\|_1=1\). Near each of the points, \(P_m\) looks like a large multiple of a Dirichlet kernel, and by choosing the points with arithmetic care one arranges that at most \(x\), some partial sum \(S_kP_m(x)\) has size comparable to \(\log m\). Then set \(f=\sum_j P_{m_j}/\sqrt{\log m_j}\) with rapidly increasing \(m_j\) and frequencies separated so that the blocks do not interfere. The series for \(f\) converges in \(L^1\), but its partial sums are unbounded almost everywhere. The everywhere-divergent version needs a further refinement.

In 1966 Lennart Carleson proved the opposite statement in \(L^2\): the Fourier series of every square-integrable function converges almost everywhere. Richard Hunt extended this to \(L^p\), \(p>1\). So \(L^1\) is exactly where Kolmogorov’s phenomenon lives. In 1925 Kolmogorov also proved that the conjugate-function operator is of weak type \((1,1)\), \(|\{|\tilde f|>\lambda\}|\le C\|f\|_1/\lambda\), a prototype for the later Calderón–Zygmund theory.

Logic, 1925

Intuitionists, following L. E. J. Brouwer, reject the law \(A\vee\neg A\) as a general principle. Kolmogorov asked how much of classical mathematics survives. His answer was a translation.

So classical logic embeds in intuitionistic logic, and intuitionistic reasoning is consistent if classical reasoning is. Kurt Gödel and Gerhard Gentzen found similar translations independently in 1933. In 1932 Kolmogorov added an interpretation of intuitionistic logic as a calculus of problems, in which a proof of \(A\to B\) is a method turning solutions of \(A\) into solutions of \(B\). It is one source of the Brouwer–Heyting–Kolmogorov interpretation.

The axioms of probability

For the general reader. For three centuries probability was a collection of problems about dice, cards and errors, with no agreed definition. In 1900 Hilbert listed its axiomatization among his problems. Kolmogorov’s 1933 book solved it in sixty pages: a probability is a measure of total mass one, an event is a measurable set, and a random variable is a measurable function.

Kolmogorov stated finite additivity and, separately, a continuity axiom: if \(A_1\supseteq A_2\supseteq\cdots\) and \(\bigcap A_n=\varnothing\), then \(P(A_n)\to0\). Together they are equivalent to countable additivity (Exercise 5.1). He noted that the continuity axiom cannot be justified by experience; it is a convenient idealization that makes the theory work.

Building processes

The book’s most consequential theorem constructs probability measures on infinite-dimensional spaces from finite-dimensional data.

This is how Brownian motion, Gaussian processes and Markov chains are constructed as objects. The proof uses inner regularity of Borel measures on \(\mathbb R^k\) (compact approximation) to verify the continuity axiom on cylinder sets, then applies Carathéodory’s extension.

Conditional expectation and the zero–one law

For an integrable \(X\) and a sub-\(\sigma\)-algebra \(\mathcal G\), Kolmogorov defined \(E[X\mid\mathcal G]\) as the \(\mathcal G\)-measurable function with \(\int_G E[X\mid\mathcal G]\,dP=\int_G X\,dP\) for all \(G\in\mathcal G\). It exists and is unique almost surely by the Radon–Nikodym theorem. Conditioning on events of probability zero, which had produced paradoxes, became meaningful.

Proof. \(A\) is independent of \(\sigma(X_1,\dots,X_n)\) for every \(n\), hence of the algebra \(\bigcup_n\sigma(X_1,\dots,X_n)\), hence (by a monotone class argument) of \(\sigma(X_1,X_2,\dots)\supseteq\mathcal T\). So \(A\) is independent of itself: \(P(A)=P(A)^2\).

Sums of independent variables

For the general reader. Toss a coin many times and count heads minus tails. How far can the total stray? Kolmogorov answered with three tools: an inequality for the largest excursion, an exact test for when a random series settles down, and a sharp law for the size of the largest fluctuations. A fourth result tells a statistician whether data really came from a proposed distribution.

Throughout, \(X_1,X_2,\dots\) are independent and \(S_n=X_1+\cdots+X_n\).

This is Chebyshev’s inequality for the whole path rather than its endpoint. The proof (Exercise 6.1) is the first appearance of a stopping-time argument, later generalized by Joseph Doob to martingales.

The proof truncates, applies the three-series theorem to \(\sum (Y_n-EY_n)/n\), and uses Kronecker’s lemma: if \(\sum a_n/n\) converges then \((a_1+\cdots+a_n)/n\to0\).

Khinchin had proved the case of coin tossing in 1924. The hero figure shows the envelope \(\pm\sqrt{2n\log\log n}\) for \(\pm1\) steps.

Goodness of fit

Let \(X_i\) be i.i.d. with continuous distribution function \(F\), and let \(F_n(x)=\frac1n\#\{i\le n:X_i\le x\}\) be the empirical distribution function.

The limit does not depend on \(F\). This is the basis of the Kolmogorov–Smirnov test, completed for two samples by Nikolai Smirnov.

Markov processes and diffusion

For the general reader. A Markov process forgets its past: where it goes next depends only on where it is now. In 1931 Kolmogorov showed that the probabilities of such a process obey differential equations, one looking forward in time and one looking back. The forward equation describes how a cloud of particles spreads; the backward equation computes expected payoffs. Six years later he used similar ideas to describe how an advantageous gene invades a population.

Let \(P(s,x;t,A)\) be the probability that a process at \(x\) at time \(s\) lies in \(A\) at time \(t>s\). The Markov property gives the Chapman–Kolmogorov equation

For a chain on a finite set with generator matrix \(Q\) (off-diagonal rates \(q_{ij}\ge0\), rows summing to 0) the same reasoning gives \(P'(t)=QP(t)\) (backward) and \(P'(t)=P(t)Q\) (forward), so \(P(t)=e^{tQ}\). The physicists’ diffusion equations became theorems about a well-defined class of random processes, and the paper set the agenda for the work of William Feller, Kiyosi Itô and Eugene Dynkin.

Travelling fronts (1937)

With Ivan Petrovsky and Nikolai Piskunov, Kolmogorov studied

a model for the spread of a favoured gene, proposed in the same year by Ronald Fisher with \(f(u)=ru(1-u)\).

Turbulence: the theory of 1941

For the general reader. Stir a fluid hard and it becomes turbulent: large eddies break into smaller ones, which break into smaller ones still, until viscosity turns the motion into heat. In 1941, in notes of a few pages, Kolmogorov argued that the small eddies forget how the flow was stirred and depend only on the rate at which energy cascades down. From that hypothesis and dimensional analysis he derived laws that experiments have confirmed to good accuracy.

Consider the Navier–Stokes equations \(\partial_t\mathbf u+(\mathbf u\cdot\nabla)\mathbf u=-\nabla p+\nu\Delta\mathbf u+\mathbf f\), \(\nabla\cdot\mathbf u=0\), driven at a large scale \(L\). Let \(\varepsilon\) be the mean rate of energy dissipation per unit mass and \(\delta u(r)\) the velocity difference between points at distance \(r\).

The only length built from \(\nu\) (m²/s) and \(\varepsilon\) (m²/s³) is the Kolmogorov scale, and in the inertial range the second hypothesis forces power laws:

The spectral form \(E(k)\) was given by Aleksandr Obukhov, Kolmogorov’s student, in 1941.

Unlike the two-thirds law, this follows from the Navier–Stokes equations via the Kármán–Howarth equation, with no similarity hypothesis. It is one of very few exact results in turbulence. The negative sign expresses the transfer of energy from large to small scales.

Intermittency and the 1962 refinement

Lev Landau objected that \(\varepsilon\) fluctuates in space, so it cannot be a universal parameter. In 1962 Kolmogorov proposed a refined similarity hypothesis with a lognormal distribution of the locally averaged dissipation, which gives structure-function exponents \(\zeta_p=\frac p3-\mu\frac{p(p-3)}{18}\) in place of \(p/3\). Measured exponents do deviate from \(p/3\) for large \(p\), and explaining them remains open.

KAM and entropy

For the general reader. Is the solar system stable? Planets perturb each other, and Henri Poincaré had shown that perturbation series usually diverge. In 1954 Kolmogorov announced that most orderly motions survive small perturbations after all. A few years later he imported Claude Shannon’s measure of information into dynamics and used it to tell chaotic systems apart.

Persistence of invariant tori

An integrable Hamiltonian \(H_0(I)\) in action–angle variables \((I,\varphi)\in\mathbb R^n\times\mathbb T^n\) has motions \(\dot\varphi=\omega(I)=\partial H_0/\partial I\), \(\dot I=0\): each torus \(\{I=\text{const}\}\) is filled by quasi-periodic orbits. Perturb to \(H=H_0(I)+\epsilon H_1(I,\varphi)\).

Where the difficulty lies. Seeking a canonical change of variables that removes the \(\varphi\)-dependence at first order leads to the equation \(\langle\omega,\partial_\varphi S\rangle=-\tilde H_1\), solved in Fourier series by \(S_k=i\,\hat H_{1,k}/\langle k,\omega\rangle\). The denominators \(\langle k,\omega\rangle\) can be arbitrarily small. Kolmogorov’s idea was to keep the frequency fixed, use the Diophantine condition to bound the losses, and iterate with a Newton-type scheme whose quadratic convergence beats the small divisors. His 1954 note sketched this; Arnold gave a complete proof for analytic systems, and Jürgen Moser proved a version for twist maps of finite smoothness.

Entropy (1958)

Let \(T\) preserve a probability measure \(\mu\). For a finite partition \(\xi\), let \(H(\xi)=-\sum_{C\in\xi}\mu(C)\log\mu(C)\) and

\(h(T)\) is an isomorphism invariant. Kolmogorov introduced it in 1958; Yakov Sinai gave the definition above in 1959 and proved that \(h(T)=h(T,\xi)\) for any generating partition.

Whether they were isomorphic had been an open question posed by John von Neumann. Donald Ornstein proved in 1970 that entropy is a complete invariant for Bernoulli shifts.

Superposition and complexity

For the general reader. Can every function of many variables be built from functions of one variable? Hilbert guessed no. Kolmogorov showed that for continuous functions the answer is yes, using only addition as glue. Late in life he asked a different question: what does it mean for a single string of digits to be random? His answer, the length of its shortest description, founded algorithmic information theory.

Hilbert’s 13th problem

Hilbert conjectured in 1900 that a root of the general equation of degree 7, as a function of its coefficients, cannot be written as a composition of continuous functions of two variables. In 1956 Kolmogorov showed that every continuous function of any number of variables is a superposition of continuous functions of three variables. In 1957 Arnold, then his nineteen-year-old student, reduced three to two, refuting Hilbert’s conjecture in its continuous form. Kolmogorov then proved the following.

The inner functions are universal; only the outer ones depend on \(f\). The functions involved are very irregular. For smooth or analytic functions, Hilbert’s intuition is closer to the truth: Kolmogorov’s student Anatoli Vitushkin showed that smoothness creates genuine obstructions to superposition.

Algorithmic complexity (1965)

Fix a machine \(U\) that reads binary programs and outputs binary strings. The complexity of \(x\) is \(C_U(x)=\min\{|p|:U(p)=x\}\).

Proof. Let \(U\) read a self-delimiting code for \(V\) and then simulate \(V\) on the rest of the input. Then \(c_V\) is the length of that code.

A string is called random when \(C(x)\) is close to \(|x|\). Ray Solomonoff (1964) and Gregory Chaitin (1966–69) reached related definitions independently. Kolmogorov’s student Per Martin-Löf showed in 1966 that random infinite sequences can be defined by effective statistical tests, and Leonid Levin, another student, developed prefix complexity.

Academician and teacher, 1933–1980

From 1935 to 1939 Kolmogorov directed the Institute of Mathematics and Mechanics at Moscow University, and in 1935 he became the first head of its chair of probability theory. In 1936 he was drawn into the campaign against his former teacher. Anonymous articles in Pravda accused Luzin of plagiarism and of disloyalty, and a commission of the Academy of Sciences held hearings in July. Kolmogorov, Alexandrov, Khinchin and Lazar Lyusternik testified against Luzin. Luzin lost his official posts but was neither expelled nor arrested. How freely the witnesses acted remains disputed; some historians argue that the police had leverage over Kolmogorov and Alexandrov. The Russian Academy formally reversed the 1936 decision only in 2012.

Kolmogorov was elected a full member of the USSR Academy of Sciences in 1939 and headed the department of probability and statistics at the Steklov Institute. During the war he applied probability to practical problems and wrote his papers on turbulence; he received a Stalin Prize in 1941. In 1942 he married Anna Dmitrievna Egorova.

The postwar decades were his most varied. He was dean of the Faculty of Mechanics and Mathematics from 1954 to 1958 and gave the closing lecture of the 1954 International Congress in Amsterdam, on dynamical systems and classical mechanics. His seminars produced a remarkable list of doctoral students, among them Israel Gelfand, Boris Gnedenko, Sergey Nikolsky, Eugene Dynkin, Yuri Prokhorov, Roland Dobrushin, Vladimir Arnold, Yakov Sinai, Albert Shiryaev, Per Martin-Löf and Leonid Levin. He was president of the Moscow Mathematical Society in 1964–66 and again from 1976.

Education occupied him more and more. In 1963, on his initiative and with support from the physicist Isaak Kikoin and the university, Moscow University opened a physics and mathematics boarding school for gifted children from the provinces, now the Kolmogorov school. He taught there himself for many hours a week, wrote textbooks, took pupils hiking, and from 1964 chaired the mathematics section of the commission that reformed the Soviet school curriculum. The reform, with its emphasis on sets and abstraction, was later criticized and partly withdrawn. In 1971 he sailed on the oceanographic expedition of the research vessel Dmitri Mendeleev to study turbulence in the ocean.

Last years and legacy

In 1980 Kolmogorov took over the chair of mathematical logic at Moscow University and shared the Wolf Prize with Henri Cartan, cited for discoveries in Fourier analysis, probability, ergodic theory and dynamical systems. In 1979 he and Alexandrov marked fifty years of friendship; Alexandrov died in 1982. Kolmogorov died in Moscow on 20 October 1987, aged 84. He is buried in the Novodevichy cemetery.

Honours

• Stalin Prize (1941), Balzan Prize (1962), Lenin Prize (1965, with Arnold, for the stability of Hamiltonian systems), Wolf Prize (1980), and the Lobachevsky Prize.
• Hero of Socialist Labour (1963) and several Orders of Lenin.
• Foreign membership of many academies, including the Leopoldina (1959), the American Academy of Arts and Sciences (1959), the London Mathematical Society (1959), the American Philosophical Society (1961), the Royal Netherlands Academy (1963), the Royal Society (1964), the US National Academy of Sciences (1967) and the French Academy of Sciences (1968).

Legacy

• Probability is a branch of measure theory because of the Grundbegriffe. Its limit theorems, Markov processes and statistical tests carry his name.
• Physics: the K41 theory is the reference point for every study of turbulence, and the \(-5/3\) spectrum is measured in oceans, atmospheres and wind tunnels.
• Dynamics: KAM theory and entropy are the two pillars of modern Hamiltonian and ergodic theory, continued by Arnold, Sinai and Ornstein.
• Computation: Kolmogorov complexity underlies algorithmic randomness and the minimum-description-length principle in statistics and machine learning.
• Schools: the Moscow school of probability and dynamics, and a model of the mathematician who teaches at every level, from primary school to the Academy.

Connections

People linked to Andrey Kolmogorov across this collection. A name without a link has no page here yet. See Andrey Kolmogorov in the network of all 337 lives →

Teachers and advisors

• Nikolai Luzin 1922-1929

Students

• Israel Gelfand 1935
• Yakov Sinai
• Albert Shiryaev
• Alexander Obukhov
• Anatoli Vitushkin
• Boris Gnedenko
• Eugene Dynkin
• Leonid Levin
• Per Martin-Löf
• Roland Dobrushin
• Sergey Nikolsky
• Vladimir Arnold
• Yuri Prokhorov

Influenced by

• Andrey Markov
• Claude Shannon
• David Hilbert
• G. I. Taylor
• Henri Lebesgue
• L. E. J. Brouwer
• Theodore von Kármán
• Vito Volterra 1936
• Émile Borel

Influenced

• Marina Ratner 1956-1965

Colleagues and collaborators

• Paul Lévy
• Ronald Fisher
• Aleksandr Khinchin 1925
• Ivan Petrovsky 1937
• Jürgen Moser
• Nikolai Smirnov

Rivals

• Norbert Wiener

Friends

• Pavel Alexandrov 1929-1982

Also mentioned in this life

• Stefan Banach
• Pafnuty Chebyshev
• Peter Gustav Lejeune Dirichlet
• Joseph Fourier
• Gottlob Frege
• Kurt Gödel
• William Rowan Hamilton
• Leopold Kronecker
• Nikolai Lobachevsky
• Dmitri Mendeleev
• Claude-Louis Navier
• Isaac Newton
• Max Planck
• Henri Poincaré
• Osborne Reynolds
• George Gabriel Stokes
• Alan Turing
• John von Neumann

Fields

• probability theory 23 lives
• real analysis 10 lives
• turbulence 5 lives
• dynamical systems 7 lives
• mathematical logic 10 lives

On CoursesHub

• Kolmogorov Complexity · Information Theory

Sources and further reading

Biography

1. J. J. O’Connor, E. F. Robertson, Andrey Nikolaevich Kolmogorov, MacTutor History of Mathematics.
2. Andrey Kolmogorov, Wikipedia.
3. P. M. B. Vitányi, A short biography of A. N. Kolmogorov, CWI Amsterdam.
4. The Luzin affair, Wikipedia.
5. Kolmogorov Boarding School of Moscow State University.
6. Wolf Prize in Mathematics, list of laureates and citations.
7. A. N. Shiryaev, Kolmogorov: life and creative activities, Annals of Probability 17 (1989) 866–944.
8. V. I. Arnold et al., Kolmogorov in Perspective, American Mathematical Society and London Mathematical Society, 2000.

Mathematics

1. A. Kolmogoroff, Une série de Fourier–Lebesgue divergente presque partout, Fundamenta Mathematicae 4 (1923).
2. A. N. Kolmogorov, On the principle of excluded middle (1925), English translation in J. van Heijenoort, From Frege to Gödel, Harvard, 1967.
3. A. Kolmogoroff, Über das Gesetz des iterierten Logarithmus, Math. Ann. 101 (1929).
4. A. Kolmogoroff, Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung, Math. Ann. 104 (1931).
5. A. Kolmogoroff, Grundbegriffe der Wahrscheinlichkeitsrechnung, Springer, 1933. English: Foundations of the Theory of Probability, Chelsea, 1950.
6. A. N. Kolmogorov, The local structure of turbulence in incompressible viscous fluid for very large Reynolds numbers, Dokl. Akad. Nauk SSSR 30 (1941); English in Proc. R. Soc. Lond. A 434 (1991).
7. U. Frisch, Turbulence: The Legacy of A. N. Kolmogorov, Cambridge University Press, 1995.
8. A. N. Kolmogorov, On conservation of conditionally periodic motions for a small change in Hamilton’s function, Dokl. Akad. Nauk SSSR 98 (1954).
9. Kolmogorov–Arnold representation theorem, Wikipedia (with the original references).
10. A. N. Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information Transmission 1 (1965).
11. M. Li, P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, Springer.