Andrey Markov

How to use this course

Andrey Andreyevich Markov (the elder, 1856–1922) is known everywhere for Markov chains, the model of a random process whose future depends on the present but not on the past. They power search engines, speech recognition, statistical physics and Bayesian computation. The chains came late in his career, when he was fifty. Before that he had done first-rate work in number theory, in the theory of continued fractions and moments, in approximation theory and in the limit theorems of probability. This course presents all of it, together with the life of a man who fought the tsar’s government and the Orthodox Church as fiercely as he fought mathematical errors.

Each technical lesson opens with a paragraph for the general reader, then gives precise statements, proof sketches and exercises with folded solutions. His son, Andrey Markov Jr. (1903–1979), was a logician known for Markov algorithms and constructive mathematics; he appears only in Lesson 12.

Timeline

Ryazan to St Petersburg, 1856–1878

Andrey Andreyevich Markov was born in Ryazan, south-east of Moscow, on 14 June 1856. His father, Andrey Grigorievich Markov, had studied at a church seminary and worked as a government clerk, later as a manager of estates. The family moved to St Petersburg when Markov was a boy. His younger brother Vladimir Andreyevich Markov (1871–1897) also became a mathematician and earned an international reputation before dying of tuberculosis at 25.

At St Petersburg Gymnasium No. 5 Markov excelled mainly in mathematics.

The university

In 1874 he entered the Physics and Mathematics Faculty of St Petersburg University. The faculty was the centre of the school founded by Pafnuty Chebyshev, and Markov studied with Chebyshev and with Chebyshev’s students Aleksandr Korkin and Yegor Zolotarev. Chebyshev’s mathematics was concrete: approximation of functions, inequalities with explicit constants, number theory, and a probability theory built on rigorous estimates. Markov adopted this style for life.

He won the university’s gold medal for an essay on the integration of differential equations by means of continued fractions, a characteristic Chebyshev theme, and graduated in 1878. He stayed at the university to prepare for an academic career.

Chebyshev’s school, 1878–1886

Korkin and Zolotarev had studied the minima of positive definite quadratic forms. They guided Markov’s master’s thesis, On binary quadratic forms with positive determinant, defended in April 1880. Its central results had already appeared in French in Mathematische Annalen in 1879 and 1880. They determine the indefinite binary quadratic forms whose smallest nonzero value is relatively largest, and they introduce the Diophantine equation whose solutions are now called Markov numbers (Lesson 04). The work is now regarded as a classic.

From the autumn of 1880 Markov lectured at the university as a Privatdozent. In 1883 he married Maria Valvatyeva; her family had waited for him to reach a secure position before approving the match. The same year Chebyshev left the university, and Markov took over the course in probability theory.

The doctorate

In 1884 Markov defended his doctoral dissertation, On certain applications of algebraic continued fractions. It treated a question Chebyshev had raised in 1874: if the first moments \(\int x^k\,d\mu\) of a distribution are known, how much can be said about the distribution itself? Chebyshev had stated the answer as a system of inequalities without proof. Markov proved them in 1884, as did the Dutch mathematician Thomas Joannes Stieltjes independently and at almost the same time; a polite priority dispute followed. These inequalities (Lesson 05) later supplied the key step in Markov’s proof of the central limit theorem.

Professor and academician, 1886–1905

In 1886 Markov became extraordinary professor, and on Chebyshev’s proposal the St Petersburg Academy of Sciences elected him an adjunct. He became an extraordinary academician in 1890 and an ordinary academician in 1896, filling the place left by Chebyshev, who died in 1894. He became ordinary professor at the university in 1893.

His teaching covered the calculus of finite differences, on which he published a two-volume text (1889–91), and probability theory. His lectures were demanding and unpolished; he cared about rigour and about getting the inequalities exactly right. He also ran a student mathematical circle. His doctoral students at St Petersburg included Georgy Voronoy (1896), the geometer of Voronoi diagrams; James Victor Uspensky (1910); Abram Besicovitch (1912); Nikolai Günther (1915); and Jacob Tamarkin (1917).

In 1889 he answered a question that the chemist Dmitri Mendeleev had raised while studying the density of solutions as a function of concentration. The answer, published in 1890, was the inequality for derivatives of polynomials in Lesson 06. In 1898 he gave the first correct proof by the method of moments of the central limit theorem that Chebyshev had asserted in 1887, and in 1900 he published his textbook Ischislenie veroyatnostei. After 25 years of service he retired from the university in 1905 as merited professor, but he continued to lecture on probability as an academician. His most famous work was still ahead.

Markov numbers and quadratic forms

For the general reader. Some irrational numbers are harder to approximate by fractions than others; the golden ratio is the hardest of all. Adolf Hurwitz measured this with a single number, \(\sqrt5\). Markov had already found, in 1879, the whole list of values below 3 that this measure can take, and the equation \(x^2+y^2+z^2=3xyz\) that produces them.

Minima of forms

Let \(f(x,y)=ax^2+bxy+cy^2\) have real coefficients and discriminant \(D=b^2-4ac>0\), and suppose \(f\) does not represent 0 at integer points other than \((0,0)\). Its minimum is \(m(f)=\inf\{|f(x,y)|:(x,y)\in\mathbb Z^2\setminus\{0\}\}\). The ratio \(\sqrt D/m(f)\) does not change under scaling of \(f\) or under integral changes of variables with determinant \(\pm1\). Korkin and Zolotarev had studied the analogous problem for positive definite forms.

The values \(\sqrt5,\ \sqrt8,\ \sqrt{221}/5,\ \sqrt{1517}/13,\dots\) increase to 3. Above 3 the set of possible values (the Markov spectrum) becomes complicated, containing intervals beyond Freiman’s constant \(\approx4.528\).

Diophantine approximation

For an irrational \(\alpha\), let \(\nu(\alpha)\) be the supremum of the \(c\) such that \(|\alpha-p/q|<1/(cq^2)\) has infinitely many solutions. Hurwitz proved in 1891 that \(\nu(\alpha)\ge\sqrt5\) always, with equality for the golden ratio. Applied to the forms \((x-\alpha y)(x-\alpha' y)\) of quadratic irrationals, Markov’s theorem shows that the values of \(\nu\) below 3 are exactly the numbers \(\sqrt{9m^2-4}/m\). The values \(\nu(\alpha)\) form the Lagrange spectrum, which agrees with the Markov spectrum below 3.

The tree of triples

The equation is quadratic in each variable. Fixing \(x,y\), the two roots \(z,z'\) of \(z^2-3xyz+(x^2+y^2)=0\) satisfy \(z+z'=3xy\). So \((x,y,z)\mapsto(x,y,3xy-z)\) sends Markov triples to Markov triples. Every triple can be reduced by such moves to \((1,1,1)\), and all triples form a tree in which every triple other than \((1,1,1)\) and \((1,1,2)\) has three distinct entries. Georg Frobenius asked in 1913 whether each Markov number is the largest entry of only one triple, up to order. This uniqueness conjecture is still open.

Moments and continued fractions

For the general reader. Suppose you know the average of a random quantity, the average of its square, and a few more such averages, but not the distribution itself. How much probability can lie below a given value? Chebyshev posed the question; Markov and Stieltjes answered it, using continued fractions and the same nodes and weights that make Gaussian numerical integration so accurate.

Orthogonal polynomials and Gauss quadrature

Let \(\mu\) be a positive measure on \(\mathbb R\) with finite moments \(m_k=\int x^k\,d\mu\) and infinite support. Gram–Schmidt applied to \(1,x,x^2,\dots\) gives orthogonal polynomials \(p_0,p_1,\dots\); \(p_n\) depends only on \(m_0,\dots,m_{2n-1}\). It has \(n\) real simple zeros \(x_1<\dots<x_n\). There are positive weights \(w_k\) (the Christoffel numbers) such that the Gauss rule

holds for every polynomial \(q\) of degree at most \(2n-1\).

The continued fraction

The Stieltjes transform has a continued fraction expansion of Jacobi type,

where \(a_n\) and \(b_n>0\) are the coefficients of the three-term recurrence \(x\,p_n=p_{n+1}+a_np_n+b_np_{n-1}\) for monic \(p_n\). The \(n\)-th convergent is the rational function \(\sum_k w_k/(z-x_k)\), and its denominator is \(p_n\). This is the dictionary that let Markov turn questions about moments into questions about continued fractions.

Proof idea for the upper bound. Construct a polynomial \(q\) of degree \(2n-2\) with \(q\ge\mathbf 1_{(-\infty,x_k]}\) on \(\mathbb R\), \(q(x_j)=1\) for \(j\le k\) and \(q(x_j)=0\) for \(j>k\) (Hermite interpolation with matched derivatives at the nodes). Then \(\nu((-\infty,x_k])\le\int q\,d\nu=\int q\,d\mu=\sum_j w_jq(x_j)=\sum_{j\le k}w_j\). The lower bound is symmetric.

Consequently, as \(n\) grows, the gaps \(w_k\) shrink when the moment problem is determinate, and the distribution function is pinned down by its moments. For the normal distribution this holds, which is why convergence of all moments to the normal ones implies convergence in distribution (Lesson 07).

The Markov inequality for polynomials

For the general reader. A polynomial of degree \(n\) that stays between \(-1\) and \(1\) on an interval cannot be arbitrarily steep there. Markov showed in 1890 that its slope is at most \(n^2\), and that the Chebyshev polynomial is the steepest. The question came from Mendeleev, who wanted to know how far one could trust the slope of a curve fitted to experimental data.

Vladimir Markov’s memoir on functions deviating least from zero appeared in Russian in 1892 and was little known abroad until a German translation appeared in Mathematische Annalen in 1916.

Proof sketch of the first inequality

Normalize \(\max|p|=1\). Two estimates cover the interval.

1. Interior. Bernstein’s inequality (1912) for trigonometric polynomials, applied to \(p(\cos\theta)\), gives \(|p'(x)|\le n/\sqrt{1-x^2}\). This is at most \(n^2\) whenever \(\sqrt{1-x^2}\ge1/n\).
2. Near the ends. Let \(\eta=\cos(\pi/2n)\) be the largest zero of \(T_n\). Interpolating \(p\) at the zeros of \(T_n\) and differentiating, one shows that for \(|x|\ge\eta\) all the derivatives of the Lagrange basis polynomials have the same sign pattern as in \(T_n'\), which gives \(|p'(x)|\le|T_n'(x)|\le T_n'(1)=n^2\).

The two regions overlap, because for \(|x|\le\eta\) we have \(\sqrt{1-x^2}\ge\sin(\pi/2n)\ge1/n\), using \(\sin t\ge2t/\pi\) on \([0,\pi/2]\). ∎

The inequality is now a basic tool in approximation theory, in numerical analysis (stability of polynomial methods) and in theoretical computer science, where it gives lower bounds for the degree of polynomials approximating Boolean functions.

Limit theorems by moments

For the general reader. Average many independent random quantities and the average settles down (the law of large numbers); look at the fluctuations around it and they follow the bell curve (the central limit theorem). Chebyshev proved the first and claimed the second. Markov supplied a correct proof of the second, then spent years defending the method of moments against a faster method of his colleague Aleksandr Lyapunov.

Proof. \(a\,\mathbf 1_{\{Y\ge a\}}\le Y\); take expectations. ∎ Applied to \(Y=(X-EX)^2\) this gives the Bienaymé–Chebyshev inequality \(P(|X-EX|\ge\varepsilon)\le\operatorname{Var}X/\varepsilon^2\). The inequality appears in Markov’s textbook; older literature often calls it Chebyshev’s inequality.

Markov noticed that the proof uses only the variance of the sum, not independence. This observation is the seed of Lesson 08.

The method of moments

Chebyshev’s 1887 argument for the central limit theorem tried to show that every moment of the normalized sum tends to the corresponding moment of the standard normal, \(E[Z^{2k}]=(2k-1)!!\), and then to conclude convergence of distributions. The second step is exactly the Chebyshev–Markov–Stieltjes inequalities of Lesson 05: when the limit is determined by its moments, as the normal distribution is, convergence of moments implies convergence of distribution functions. Chebyshev’s computation of moments was incomplete. Markov gave a correct proof in 1898.

Lyapunov proved this in 1900–01 using characteristic functions, a method that does not require all moments to exist. Markov responded by truncating the variables, so that all moments exist, applying the method of moments to the truncated sums, and controlling the error. He completed this proof in the third edition of his textbook (1913).

Chains: the law of large numbers without independence

For the general reader. In 1902 the Moscow mathematician Pavel Nekrasov argued that the law of large numbers requires independence, and drew from social statistics a conclusion about free will. Markov, who disliked both the mathematics and the theology, built a counterexample: a sequence in which each trial depends on the one before, yet averages still settle down. This sequence was the first Markov chain.

The setting

A sequence \(X_0,X_1,\dots\) with values in a finite set \(S\) is a (homogeneous) Markov chain with transition matrix \(P=(p_{ij})\) if

Then \(P(X_{t+n}=j\mid X_t=i)=(P^n)_{ij}\). Markov’s 1906 paper, published in the Izvestiya of the Physico-Mathematical Society at Kazan University, treated variables “connected in a chain” in exactly this sense, beginning with two states.

Two states

Take \(S=\{1,0\}\) (say vowel and consonant) with \(P(X_{t+1}=1\mid X_t=1)=p_1\) and \(P(X_{t+1}=1\mid X_t=0)=p_2\). Then

The eigenvalues of \(P\) are 1 and \(\lambda\), and

Proof. From the formula for \(P^n\), \(|E X_t-\pi|\le|\lambda|^t\), and for \(s<t\), \(|\operatorname{Cov}(X_s,X_t)|\le C|\lambda|^{t-s}\) for a constant \(C\). Hence

and Chebyshev’s inequality finishes the proof, since \(E\big[\frac1n\sum X_t\big]\to\pi\). ∎ Independence was never used, only the geometric decay of correlations. Markov extended the argument to chains with any finite number of states whose transition probabilities are all positive.

Stationarity, Onegin and the central limit theorem

For the general reader. On 23 January 1913 Markov told the Academy of Sciences about an unusual experiment. He had taken the first 20,000 letters of Alexander Pushkin’s verse novel Eugene Onegin, marked each as vowel or consonant, and counted how often a vowel follows a vowel. Real text, he showed, behaves like a chain and not like coin tosses. It was the first application of his chains to data.

Markov proved results of this kind for stochastic matrices in 1906–08, including the role of the eigenvalue 1. Oskar Perron (1907) and Georg Frobenius (1908–1912) proved the general theory of positive and nonnegative matrices, now called Perron–Frobenius theory. A short proof for stochastic matrices uses contraction: if every entry of \(P^r\) is at least \(\varepsilon>0\), then any two rows of \(P^{rk}\) differ in total variation by at most \((1-\varepsilon)^k\).

Fluctuations

In 1907 Markov proved the central limit theorem for a two-state chain and in 1908 for finitely many states. For the two-state stationary chain, \(\operatorname{Cov}(X_0,X_k)=\pi(1-\pi)\lambda^k\), so

Compared with independent trials, the variance is multiplied by \((1+\lambda)/(1-\lambda)\): positive dependence inflates fluctuations, negative dependence damps them.

The Onegin count

Markov wrote the 20,000 letters, without spaces or punctuation, in blocks of 100. He counted 8,638 vowels and 11,362 consonants, a vowel frequency of about 0.432. He found the probability of a vowel after a vowel to be \(p_1\approx0.128\), and after a consonant \(p_2\approx0.663\). He then compared the observed dispersion of vowel counts across blocks with the dispersion predicted for independent letters and for a chain, and found the chain fitted. He made a similar study of 100,000 letters of prose by Sergei Aksakov.

Least squares

For the general reader. When measurements contain errors, the method of least squares picks the parameter values that make the sum of squared errors smallest. Carl Friedrich Gauss proved in the 1820s that this choice is, in a precise sense, the best possible among simple estimators. Markov’s textbook presented the result in the clean form now taught to every statistics student, and so the theorem carries both names.

Consider the linear model \(y=X\beta+\varepsilon\), where \(X\) is a known \(n\times p\) matrix of rank \(p\), \(\beta\in\mathbb R^p\) is unknown, and the errors satisfy \(E\varepsilon=0\) and \(\operatorname{Cov}(\varepsilon)=\sigma^2I\). The least-squares estimator is \(\hat\beta=(X^{\mathsf T}X)^{-1}X^{\mathsf T}y\).

Proof. Write \(C=(X^{\mathsf T}X)^{-1}X^{\mathsf T}+D\). Unbiasedness for all \(\beta\) forces \(CX=I\), hence \(DX=0\). Then

because the cross terms contain \(DX=0\). Since \(DD^{\mathsf T}\) is positive semidefinite, the claim follows. ∎

Gauss proved the optimality of least squares in his Theoria combinationis observationum erroribus minimis obnoxiae (1821–23). Markov gave a careful exposition in his textbook, and a 1938 paper by Florence Nightingale David and Jerzy Neyman, titled an extension of “the Markoff theorem on least squares”, helped fix his name to it. Historians regard the attribution to Markov as generous; the name is now standard.

The rebel academician, 1902–1917

Markov was a liberal and an atheist, and he said so in public. In 1902 the Academy elected the writer Maxim Gorky an honorary member; Tsar Nicholas II had the election annulled. Markov protested repeatedly, and in 1903 he refused the state decorations he was due. When the tsar dissolved the Second Duma in June 1907, Markov renounced his rights as a voter in protest.

His quarrels with Nekrasov were both mathematical and political. Nekrasov, a conservative Moscow mathematician, used probability to argue for free will and the established order; Markov regarded the arguments as abuses of mathematics. The chains of Lesson 08 were one answer. Nekrasov in turn accused Markov of Marxism, which was an exaggeration.

In 1912, after the Orthodox Church had excommunicated Leo Tolstoy, Markov asked the Holy Synod to excommunicate him as well. The request was granted. In 1913, when the government celebrated three hundred years of the Romanov dynasty, Markov organized a rival celebration of the two hundredth anniversary of Jacob Bernoulli’s Ars Conjectandi and the law of large numbers. The same year the university elected him an honorary member; the minister of education did not confirm the election until after the February Revolution of 1917.

He kept teaching after his retirement. In 1908 he refused a government order to report on students during unrest and was removed from university teaching. His work on chains continued: nonhomogeneous chains (1910), and in 1911–12 more general schemes, including chains observed only through some of their variables.

Last years and legacy, 1917–1922

In September 1917 Markov asked the Academy to send him to some small town in the interior. He spent the famine winter in Zaraisk, south of Moscow, teaching mathematics in the secondary school without pay. Back in Petrograd, he continued to lecture in 1921 although he could scarcely stand, and underwent an operation. He died in Petrograd on 20 July 1922 after months of severe suffering, aged 66.

His son Andrey Markov Jr. (1903–1979) became a leading logician, known for Markov algorithms, the unsolvability of the homeomorphism problem for 4-manifolds, and the Russian school of constructive mathematics.

Legacy

• Stochastic processes: the term “Markov chain” was in use by the 1920s. Andrey Kolmogorov’s 1931 theory of Markov processes in continuous time, Wolfgang Doeblin’s and Joseph Doob’s work on general state spaces, and the Markov property in modern probability all descend from the 1906 paper.
• Applications: Markov chain Monte Carlo (from the Metropolis algorithm of 1953), hidden Markov models in speech recognition and genomics, queueing theory, statistical mechanics, and the PageRank algorithm for ranking web pages. Claude Shannon’s 1948 theory of information modelled English text as a Markov source, directly echoing the Onegin study.
• Number theory: the Markov spectrum and Markov numbers, connected today with hyperbolic geometry, cluster algebras and exceptional vector bundles; Frobenius’s uniqueness conjecture is still open.
• Analysis: the Markov brothers’ inequality, the Chebyshev–Markov–Stieltjes inequalities and the theory of moments.
• Statistics: the Gauss–Markov theorem and Markov’s inequality, standard in every course.
• School: through Voronoy, Uspensky, Besicovitch, Tamarkin and others his influence reached geometry of numbers, geometric measure theory and American analysis.

Sources and further reading

Biography

1. J. J. O’Connor and E. F. Robertson, Andrei Andreyevich Markov, MacTutor History of Mathematics.
2. Andrey Markov, Wikipedia.
3. A. P. Youschkevitch, Markov, Andrei Andreevich, Dictionary of Scientific Biography, via MacTutor.
4. Markov, Andrei Andreevich, Encyclopedia of Mathematics.
5. G. P. Basharin, A. N. Langville and V. A. Naumov, The life and work of A. A. Markov, Linear Algebra and its Applications 386 (2004), 3–26.
6. B. Hayes, First links in the Markov chain, American Scientist 101 (2013).
7. A. A. Markov, Mathematics Genealogy Project.

Mathematics

1. A. Markoff, Sur les formes quadratiques binaires indéfinies, Math. Ann. 15 (1879), 381–406; 17 (1880), 379–399.
2. A. A. Markov, On a question by D. I. Mendeleev, Zapiski Imp. Akad. Nauk 62 (1890); see notes and translation, University of Auckland.
3. A. A. Markov, Extension of the law of large numbers to quantities depending on each other, Izv. Fiz.-Mat. Obshch. Kazan. Univ. (2) 15 (1906).
4. A. A. Markov, An example of statistical investigation of the text Eugene Onegin concerning the connection of samples in chains, Izv. Imp. Akad. Nauk (1913); English translation in Science in Context 19 (2006).
5. A. A. Markov, Ischislenie veroyatnostei, 1900; 3rd ed. 1913.
6. M. Aigner, Markov’s Theorem and 100 Years of the Uniqueness Conjecture, Springer, 2013.
7. T. W. Cusick and M. E. Flahive, The Markoff and Lagrange Spectra, AMS, 1989.
8. N. I. Akhiezer, The Classical Moment Problem, Oliver and Boyd, 1965.
9. Markov chain, Markov number and Markov brothers’ inequality, Wikipedia.