You are currently browsing the category archive for the ‘math.PR’ category.

Let ${X_1,X_2,\dots}$ be iid copies of an absolutely integrable real scalar random variable ${X}$, and form the partial sums ${S_n := X_1 + \dots + X_n}$. As we saw in the last set of notes, the law of large numbers ensures that the empirical averages ${S_n/n}$ converge (both in probability and almost surely) to a deterministic limit, namely the mean ${\mu= {\bf E} X}$ of the reference variable ${X}$. Furthermore, under some additional moment hypotheses on the underlying variable ${X}$, we can obtain square root cancellation for the fluctuation ${\frac{S_n}{n} - \mu}$ of the empirical average from the mean. To simplify the calculations, let us first restrict to the case ${\mu=0, \sigma^2=1}$ of mean zero and variance one, thus

$\displaystyle {\bf E} X = 0$

and

$\displaystyle {\bf Var}(X) = {\bf E} X^2 = 1.$

Then, as computed in previous notes, the normalised fluctuation ${S_n/\sqrt{n}}$ also has mean zero and variance one:

$\displaystyle {\bf E} \frac{S_n}{\sqrt{n}} = 0$

$\displaystyle {\bf Var}(\frac{S_n}{\sqrt{n}}) = {\bf E} (\frac{S_n}{\sqrt{n}})^2 = 1.$

This and Chebyshev’s inequality already indicates that the “typical” size of ${S_n}$ is ${O(\sqrt{n})}$, thus for instance ${\frac{S_n}{\sqrt{n} \omega(n)}}$ goes to zero in probability for any ${\omega(n)}$ that goes to infinity as ${n \rightarrow \infty}$. If we also have a finite fourth moment ${{\bf E} |X|^4 < \infty}$, then the calculations of the previous notes also give a fourth moment estimate

$\displaystyle {\bf E} (\frac{S_n}{\sqrt{n}})^4 = 3 + O( \frac{{\bf E} |X|^4}{n} ).$

From this and the Paley-Zygmund inequality (Exercise 42 of Notes 1) we also get some lower bound for ${\frac{S_n}{\sqrt{n}}}$ of the form

$\displaystyle {\bf P}( |\frac{S_n}{\sqrt{n}}| \geq \varepsilon ) \geq \varepsilon$

for some absolute constant ${\varepsilon>0}$ and for ${n}$ sufficiently large; this indicates in particular that ${\frac{S_n \omega(n)}{\sqrt{n}}}$ does not converge in any reasonable sense to something finite for any ${\omega(n)}$ that goes to infinity.

The question remains as to what happens to the ratio ${S_n/\sqrt{n}}$ itself, without multiplying or dividing by any factor ${\omega(n)}$. A first guess would be that these ratios converge in probability or almost surely, but this is unfortunately not the case:

Proposition 1 Let ${X_1,X_2,\dots}$ be iid copies of an absolutely integrable real scalar random variable ${X}$ with mean zero, variance one, and finite fourth moment, and write ${S_n := X_1 + \dots + X_n}$. Then the random variables ${S_n/\sqrt{n}}$ do not converge in probability or almost surely to any limit, and neither does any subsequence of these random variables.

Proof: Suppose for contradiction that some sequence ${S_{n_j}/\sqrt{n_j}}$ converged in probability or almost surely to a limit ${Y}$. By passing to a further subsequence we may assume that the convergence is in the almost sure sense. Since all of the ${S_{n_j}/\sqrt{n_j}}$ have mean zero, variance one, and bounded fourth moment, Theorem 24 of Notes 1 implies that the limit ${Y}$ also has mean zero and variance one. On the other hand, ${Y}$ is a tail random variable and is thus almost surely constant by the Kolmogorov zero-one law from Notes 3. Since constants have variance zero, we obtain the required contradiction. $\Box$

Nevertheless there is an important limit for the ratio ${S_n/\sqrt{n}}$, which requires one to replace the notions of convergence in probability or almost sure convergence by the weaker concept of convergence in distribution.

Definition 2 (Vague convergence and convergence in distribution) Let ${R}$ be a locally compact Hausdorff topological space with the Borel ${\sigma}$-algebra. A sequence of finite measures ${\mu_n}$ on ${R}$ is said to converge vaguely to another finite measure ${\mu}$ if one has

$\displaystyle \int_R G(x)\ d\mu_n(x) \rightarrow \int_R G(x)\ d\mu(x)$

as ${n \rightarrow \infty}$ for all continuous compactly supported functions ${G: R \rightarrow {\bf R}}$. (Vague convergence is also known as weak convergence, although strictly speaking the terminology weak-* convergence would be more accurate.) A sequence of random variables ${X_n}$ taking values in ${R}$ is said to converge in distribution (or converge weakly or converge in law) to another random variable ${X}$ if the distributions ${\mu_{X_n}}$ converge vaguely to the distribution ${\mu_X}$, or equivalently if

$\displaystyle {\bf E}G(X_n) \rightarrow {\bf E} G(X)$

as ${n \rightarrow \infty}$ for all continuous compactly supported functions ${G: R \rightarrow {\bf R}}$.

One could in principle try to extend this definition beyond the locally compact Hausdorff setting, but certain pathologies can occur when doing so (e.g. failure of the Riesz representation theorem), and we will never need to consider vague convergence in spaces that are not locally compact Hausdorff, so we restrict to this setting for simplicity.

Note that the notion of convergence in distribution depends only on the distribution of the random variables involved. One consequence of this is that convergence in distribution does not produce unique limits: if ${X_n}$ converges in distribution to ${X}$, and ${Y}$ has the same distribution as ${X}$, then ${X_n}$ also converges in distribution to ${Y}$. However, limits are unique up to equivalence in distribution (this is a consequence of the Riesz representation theorem, discussed for instance in this blog post). As a consequence of the insensitivity of convergence in distribution to equivalence in distribution, we may also legitimately talk about convergence of distribution of a sequence of random variables ${X_n}$ to another random variable ${X}$ even when all the random variables ${X_1,X_2,\dots}$ and ${X}$ involved are being modeled by different probability spaces (e.g. each ${X_n}$ is modeled by ${\Omega_n}$, and ${X}$ is modeled by ${\Omega}$, with no coupling presumed between these spaces). This is in contrast to the stronger notions of convergence in probability or almost sure convergence, which require all the random variables to be modeled by a common probability space. Also, by an abuse of notation, we can say that a sequence ${X_n}$ of random variables converges in distribution to a probability measure ${\mu}$, when ${\mu_{X_n}}$ converges vaguely to ${\mu}$. Thus we can talk about a sequence of random variables converging in distribution to a uniform distribution, a gaussian distribution, etc..

From the dominated convergence theorem (available for both convergence in probability and almost sure convergence) we see that convergence in probability or almost sure convergence implies convergence in distribution. The converse is not true, due to the insensitivity of convergence in distribution to equivalence in distribution; for instance, if ${X_1,X_2,\dots}$ are iid copies of a non-deterministic scalar random variable ${X}$, then the ${X_n}$ trivially converge in distribution to ${X}$, but will not converge in probability or almost surely (as one can see from the zero-one law). However, there are some partial converses that relate convergence in distribution to convergence in probability; see Exercise 10 below.

Remark 3 The notion of convergence in distribution is somewhat similar to the notion of convergence in the sense of distributions that arises in distribution theory (discussed for instance in this previous blog post), however strictly speaking the two notions of convergence are distinct and should not be confused with each other, despite the very similar names.

The notion of convergence in distribution simplifies in the case of real scalar random variables:

Proposition 4 Let ${X_1,X_2,\dots}$ be a sequence of scalar random variables, and let ${X}$ be another scalar random variable. Then the following are equivalent:

• (i) ${X_n}$ converges in distribution to ${X}$.
• (ii) ${F_{X_n}(t)}$ converges to ${F_X(t)}$ for each continuity point ${t}$ of ${F_X}$ (i.e. for all real numbers ${t \in {\bf R}}$ at which ${F_X}$ is continuous). Here ${F_X(t) := {\bf P}(X \leq t)}$ is the cumulative distribution function of ${X}$.

Proof: First suppose that ${X_n}$ converges in distribution to ${X}$, and ${F_X}$ is continuous at ${t}$. For any ${\varepsilon > 0}$, one can find a ${\delta}$ such that

$\displaystyle F_X(t) - \varepsilon \leq F_X(t') \leq F_X(t) + \varepsilon$

for every ${t' \in [t-\delta,t+\delta]}$. One can also find an ${N}$ larger than ${|t|+\delta}$ such that ${F_X(-N) \leq \varepsilon}$ and ${F_X(N) \geq 1-\varepsilon}$. Thus

$\displaystyle {\bf P} (|X| \geq N ) = O(\varepsilon)$

and

$\displaystyle {\bf P} (|X - t| \leq \delta ) = O(\varepsilon).$

Let ${G: {\bf R} \rightarrow [0,1]}$ be a continuous function supported on ${[-2N, t]}$ that equals ${1}$ on ${[-N, t-\delta]}$. Then by the above discussion we have

$\displaystyle {\bf E} G(X) = F_X(t) + O(\varepsilon)$

and hence

$\displaystyle {\bf E} G(X_n) = F_X(t) + O(\varepsilon)$

for large enough ${n}$. In particular

$\displaystyle {\bf P}( X_n \leq t ) \geq F_X(t) - O(\varepsilon).$

A similar argument, replacing ${G}$ with a continuous function supported on ${[t,2N]}$ that equals ${1}$ on ${[t+\delta,N]}$ gives

$\displaystyle {\bf P}( X_n > t ) \geq 1 - F_X(t) - O(\varepsilon)$

for ${n}$ large enough. Putting the two estimates together gives

$\displaystyle F_{X_n}(t) = F_X(t) + O(\varepsilon)$

for ${n}$ large enough; sending ${\varepsilon \rightarrow 0}$, we obtain the claim.

Conversely, suppose that ${F_{X_n}(t)}$ converges to ${F_X(t)}$ at every continuity point ${t}$ of ${F_X}$. Let ${G: {\bf R} \rightarrow {\bf R}}$ be a continuous compactly supported function, then it is uniformly continuous. As ${F_X}$ is monotone increasing, it can only have countably many points of discontinuity. From these two facts one can find, for any ${\varepsilon>0}$, a simple function ${G_\varepsilon(t) = \sum_{i=1}^n c_i 1_{(t_i,t_{i+1}]}}$ for some ${t_1 < \dots < t_n}$ that are points of continuity of ${F_X}$, and real numbers ${c_i}$, such that ${|G(t) - G_\varepsilon(t)| \leq \varepsilon}$ for all ${t}$. Thus

$\displaystyle {\bf E} G(X_n) = {\bf E} G_\varepsilon(X_n) + O(\varepsilon)$

$\displaystyle = \sum_{i=1}^n c_i(F_{X_n}(t_{i+1}) - F_{X_n}(t)) + O(\varepsilon).$

Similarly for ${X_n}$ replaced by ${X}$. Subtracting and taking limit superior, we conclude that

$\displaystyle \limsup_{n \rightarrow \infty} |{\bf E} G(X_n) - {\bf E} G(X)| = O(\varepsilon),$

and on sending ${\varepsilon \rightarrow 0}$, we obtain that ${X_n}$ converges in distribution to ${X}$ as claimed. $\Box$

The restriction to continuity points of ${t}$ is necessary. Consider for instance the deterministic random variables ${X_n = 1/n}$, then ${X_n}$ converges almost surely (and hence in distribution) to ${0}$, but ${F_{X_n}(0) = 0}$ does not converge to ${F_X(0)=1}$.

Example 5 For any natural number ${n}$, let ${X_n}$ be a discrete random variable drawn uniformly from the finite set ${\{0/n, 1/n, \dots, (n-1)/n\}}$, and let ${X}$ be the continuous random variable drawn uniformly from ${[0,1]}$. Then ${X_n}$ converges in distribution to ${X}$. Thus we see that a continuous random variable can emerge as the limit of discrete random variables.

Example 6 For any natural number ${n}$, let ${X_n}$ be a continuous random variable drawn uniformly from ${[0,1/n]}$, then ${X_n}$ converges in distribution to the deterministic real number ${0}$. Thus we see that discrete (or even deterministic) random variables can emerge as the limit of continuous random variables.

Exercise 7 (Portmanteau theorem) Show that the properties (i) and (ii) in Proposition 4 are also equivalent to the following three statements:

• (iii) One has ${\limsup_{n \rightarrow \infty} {\bf P}( X_n \in K ) \leq {\bf P}(X \in K)}$ for all closed sets ${K \subset {\bf R}}$.
• (iv) One has ${\liminf_{n \rightarrow \infty} {\bf P}( X_n \in U ) \geq {\bf P}(X \in U)}$ for all open sets ${U \subset {\bf R}}$.
• (v) For any Borel set ${E \subset {\bf R}}$ whose topological boundary ${\partial E}$ is such that ${{\bf P}(X \in \partial E) = 0}$, one has ${\lim_{n \rightarrow \infty} {\bf P}(X_n \in E) = {\bf P}(X \in E)}$.

(Note: to prove this theorem, you may wish to invoke Urysohn’s lemma. To deduce (iii) from (i), you may wish to start with the case of compact ${K}$.)

We can now state the famous central limit theorem:

Theorem 8 (Central limit theorem) Let ${X_1,X_2,\dots}$ be iid copies of a scalar random variable ${X}$ of finite mean ${\mu := {\bf E} X}$ and finite non-zero variance ${\sigma^2 := {\bf Var}(X)}$. Let ${S_n := X_1 + \dots + X_n}$. Then the random variables ${\frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu)}$ converges in distribution to a random variable with the standard normal distribution ${N(0,1)}$ (that is to say, a random variable with probability density function ${x \mapsto \frac{1}{\sqrt{2\pi}} e^{-x^2/2}}$). Thus, by abuse of notation

$\displaystyle \frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu) \rightarrow N(0,1).$

In the normalised case ${\mu=0, \sigma^2=1}$ when ${X}$ has mean zero and unit variance, this simplifies to

$\displaystyle \frac{S_n}{\sqrt{n}} \rightarrow N(0,1).$

Using Proposition 4 (and the fact that the cumulative distribution function associated to ${N(0,1)}$ is continuous, the central limit theorem is equivalent to asserting that

$\displaystyle {\bf P}( \frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu) \leq t ) \rightarrow \frac{1}{\sqrt{2\pi}} \int_{-\infty}^t e^{-x^2/2}\ dx$

as ${n \rightarrow \infty}$ for any ${t \in {\bf R}}$, or equivalently that

$\displaystyle {\bf P}( a \leq \frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu) \leq b ) \rightarrow \frac{1}{\sqrt{2\pi}} \int_{a}^b e^{-x^2/2}\ dx.$

Informally, one can think of the central limit theorem as asserting that ${S_n}$ approximately behaves like it has distribution ${N( n \mu, n \sigma^2 )}$ for large ${n}$, where ${N(\mu,\sigma^2)}$ is the normal distribution with mean ${\mu}$ and variance ${\sigma^2}$, that is to say the distribution with probability density function ${x \mapsto \frac{1}{\sqrt{2\pi} \sigma} e^{-(x-\mu)^2/2\sigma^2}}$. The integrals ${\frac{1}{\sqrt{2\pi}} \int_{-\infty}^t e^{-x^2/2}\ dx}$ can be written in terms of the error function ${\hbox{erf}}$ as ${\frac{1}{2} + \frac{1}{2} \hbox{erf}(t/\sqrt{2})}$.

The central limit theorem is a basic example of the universality phenomenon in probability – many statistics involving a large system of many independent (or weakly dependent) variables (such as the normalised sums ${\frac{\sqrt{n}}{\sigma}(\frac{S_n}{n}-\mu)}$) end up having a universal asymptotic limit (in this case, the normal distribution), regardless of the precise makeup of the underlying random variable ${X}$ that comprised that system. Indeed, the universality of the normal distribution is such that it arises in many other contexts than the fluctuation of iid random variables; the central limit theorem is merely the first place in probability theory where it makes a prominent appearance.

We will give several proofs of the central limit theorem in these notes; each of these proofs has their advantages and disadvantages, and can each extend to prove many further results beyond the central limit theorem. We first give Lindeberg’s proof of the central limit theorem, based on exchanging (or swapping) each component ${X_1,\dots,X_n}$ of the sum ${S_n}$ in turn. This proof gives an accessible explanation as to why there should be a universal limit for the central limit theorem; one then computes directly with gaussians to verify that it is the normal distribution which is the universal limit. Our second proof is the most popular one taught in probability texts, namely the Fourier-analytic proof based around the concept of the characteristic function ${t \mapsto {\bf E} e^{itX}}$ of a real random variable ${X}$. Thanks to the powerful identities and other results of Fourier analysis, this gives a quite short and direct proof of the central limit theorem, although the arguments may seem rather magical to readers who are not already familiar with Fourier methods. Finally, we give a proof based on the moment method, in the spirit of the arguments in the previous notes; this argument is more combinatorial, but is straightforward and is particularly robust, in particular being well equipped to handle some dependencies between components; we will illustrate this by proving the Erdos-Kac law in number theory by this method. Some further discussion of the central limit theorem (including some further proofs, such as one based on Stein’s method) can be found in this blog post. Some further variants of the central limit theorem, such as local limit theorems, stable laws, and large deviation inequalities, will be discussed in the next (and final) set of notes.

The following exercise illustrates the power of the central limit theorem, by establishing combinatorial estimates which would otherwise require the use of Stirling’s formula to establish.

Exercise 9 (De Moivre-Laplace theorem) Let ${X}$ be a Bernoulli random variable, taking values in ${\{0,1\}}$ with ${{\bf P}(X=0)={\bf P}(X=1)=1/2}$, thus ${X}$ has mean ${1/2}$ and variance ${1/4}$. Let ${X_1,X_2,\dots}$ be iid copies of ${X}$, and write ${S_n := X_1+\dots+X_n}$.

• (i) Show that ${S_n}$ takes values in ${\{0,\dots,n\}}$ with ${{\bf P}(S_n=i) = \frac{1}{2^n} \binom{n}{i}}$. (This is an example of a binomial distribution.)
• (ii) Assume Stirling’s formula

$\displaystyle n! = (1+o(1)) \sqrt{2\pi n} n^n e^{-n} \ \ \ \ \ (1)$

where ${o(1)}$ is a function of ${n}$ that goes to zero as ${n \rightarrow \infty}$. (A proof of this formula may be found in this previous blog post.) Using this formula, and without using the central limit theorem, show that

$\displaystyle {\bf P}( a \leq 2\sqrt{n} (\frac{S_n}{n} - \frac{1}{2}) \leq b ) \rightarrow \frac{1}{\sqrt{2\pi}} \int_{a}^b e^{-x^2/2}\ dx$

as ${n \rightarrow \infty}$ for any fixed real numbers ${a.

The above special case of the central limit theorem was first established by de Moivre and Laplace.

We close this section with some basic facts about convergence of distribution that will be useful in the sequel.

Exercise 10 Let ${X_1,X_2,\dots}$, ${Y_1,Y_2,\dots}$ be sequences of real random variables, and let ${X,Y}$ be further real random variables.

• (i) If ${X}$ is deterministic, show that ${X_n}$ converges in distribution to ${X}$ if and only if ${X_n}$ converges in probability to ${X}$.
• (ii) Suppose that ${X_n}$ is independent of ${Y_n}$ for each ${n}$, and ${X}$ independent of ${Y}$. Show that ${X_n+iY_n}$ converges in distribution to ${X+iY}$ if and only if ${X_n}$ converges in distribution to ${X}$ and ${Y_n}$ converges in distribution to ${Y}$. (The shortest way to prove this is by invoking the Stone-Weierstrass theorem, but one can also proceed by proving some version of Proposition 4.) What happens if the independence hypothesis is dropped?
• (iii) If ${X_n}$ converges in distribution to ${X}$, show that for every ${\varepsilon>0}$ there exists ${K>0}$ such that ${{\bf P}( |X_n| \geq K ) < \varepsilon}$ for all sufficiently large ${n}$. (That is to say, ${X_n}$ is a tight sequence of random variables.)
• (iv) Show that ${X_n}$ converges in distribution to ${X}$ if and only if, after extending the probability space model if necessary, one can find copies ${Z_1,Z_2,\dots}$ and ${Z}$ of ${X_1,X_2,\dots}$ and ${X}$ respectively such that ${Z_n}$ converges almost surely to ${Z}$. (Hint: use the Skorohod representation, Exercise 29 of Notes 0.)
• (v) If ${X_1,X_2,\dots}$ converges in distribution to ${X}$, and ${F: {\bf R} \rightarrow {\bf R}}$ is continuous, show that ${F(X_1),F(X_2),\dots}$ converges in distribution to ${F(X)}$. Generalise this claim to the case when ${X}$ takes values in an arbitrary locally compact Hausdorff space.
• (vi) (Slutsky’s theorem) If ${X_n}$ converges in distribution to ${X}$, and ${Y_n}$ converges in probability to a deterministic limit ${Y}$, show that ${X_n+Y_n}$ converges in distribution to ${X+Y}$, and ${X_n Y_n}$ converges in distribution to ${XY}$. (Hint: either use (iv), or else use (iii) to control some error terms.) This statement combines particularly well with (i). What happens if ${Y}$ is not assumed to be deterministic?
• (vii) (Fatou lemma) If ${G: {\bf R} \rightarrow [0,+\infty)}$ is continuous, and ${X_n}$ converges in distribution to ${X}$, show that ${\liminf_{n \rightarrow \infty} {\bf E} G(X_n) \geq {\bf E} G(X)}$.
• (viii) (Bounded convergence) If ${G: {\bf R} \rightarrow {\bf R}}$ is continuous and bounded, and ${X_n}$ converges in distribution to ${X}$, show that ${\lim_{n \rightarrow \infty} {\bf E} G(X_n) = {\bf E} G(X)}$.
• (ix) (Dominated convergence) If ${X_n}$ converges in distribution to ${X}$, and there is an absolutely integrable ${Y}$ such that ${|X_n| \leq Y}$ almost surely for all ${n}$, show that ${\lim_{n \rightarrow \infty} {\bf E} X_n = {\bf E} X}$.

For future reference we also mention (but will not prove) Prokhorov’s theorem that gives a partial converse to part (iii) of the above exercise:

Theorem 11 (Prokhorov’s theorem) Let ${X_1,X_2,\dots}$ be a sequence of real random variables which is tight (that is, for every ${\varepsilon>0}$ there exists ${K>0}$ such that ${{\bf P}(|X_n| \geq K) < \varepsilon}$ for all sufficiently large ${n}$). Then there exists a subsequence ${X_{n_j}}$ which converges in distribution to some random variable ${X}$ (which may possibly be modeled by a different probability space model than the ${X_1,X_2,\dots}$.)

The proof of this theorem relies on the Riesz representation theorem, and is beyond the scope of this course; but see for instance Exercise 29 of this previous blog post. (See also the closely related Helly selection theorem, covered in Exercise 30 of the same post.)

One of the major activities in probability theory is studying the various statistics that can be produced from a complex system with many components. One of the simplest possible systems one can consider is a finite sequence ${X_1,\dots,X_n}$ or an infinite sequence ${X_1,X_2,\dots}$ of jointly independent scalar random variables, with the case when the ${X_i}$ are also identically distributed (i.e. the ${X_i}$ are iid) being a model case of particular interest. (In some cases one may consider a triangular array ${(X_{n,i})_{1 \leq i \leq n}}$ of scalar random variables, rather than a finite or infinite sequence.) There are many statistics of such sequences that one can study, but one of the most basic such statistics are the partial sums

$\displaystyle S_n := X_1 + \dots + X_n.$

The first fundamental result about these sums is the law of large numbers (or LLN for short), which comes in two formulations, weak (WLLN) and strong (SLLN). To state these laws, we first must define the notion of convergence in probability.

Definition 1 Let ${X_n}$ be a sequence of random variables taking values in a separable metric space ${R = (R,d)}$ (e.g. the ${X_n}$ could be scalar random variables, taking values in ${{\bf R}}$ or ${{\bf C}}$), and let ${X}$ be another random variable taking values in ${R}$. We say that ${X_n}$ converges in probability to ${X}$ if, for every radius ${\varepsilon > 0}$, one has ${{\bf P}( d(X_n,X) > \varepsilon ) \rightarrow 0}$ as ${n \rightarrow \infty}$. Thus, if ${X_n, X}$ are scalar, we have ${X_n}$ converging to ${X}$ in probability if ${{\bf P}( |X_n-X| > \varepsilon ) \rightarrow 0}$ as ${n \rightarrow \infty}$ for any given ${\varepsilon > 0}$.

The measure-theoretic analogue of convergence in probability is convergence in measure.

It is instructive to compare the notion of convergence in probability with almost sure convergence. it is easy to see that ${X_n}$ converges almost surely to ${X}$ if and only if, for every radius ${\varepsilon > 0}$, one has ${{\bf P}( \bigvee_{n \geq N} (d(X_n,X)>\varepsilon) ) \rightarrow 0}$ as ${N \rightarrow \infty}$; thus, roughly speaking, convergence in probability is good for controlling how a single random variable ${X_n}$ is close to its putative limiting value ${X}$, while almost sure convergence is good for controlling how the entire tail ${(X_n)_{n \geq N}}$ of a sequence of random variables is close to its putative limit ${X}$.

We have the following easy relationships between convergence in probability and almost sure convergence:

Exercise 2 Let ${X_n}$ be a sequence of scalar random variables, and let ${X}$ be another scalar random variable.

• (i) If ${X_n \rightarrow X}$ almost surely, show that ${X_n \rightarrow X}$ in probability. Give a counterexample to show that the converse does not necessarily hold.
• (ii) Suppose that ${\sum_n {\bf P}( |X_n-X| > \varepsilon ) < \infty}$ for all ${\varepsilon > 0}$. Show that ${X_n \rightarrow X}$ almost surely. Give a counterexample to show that the converse does not necessarily hold.
• (iii) If ${X_n \rightarrow X}$ in probability, show that there is a subsequence ${X_{n_j}}$ of the ${X_n}$ such that ${X_{n_j} \rightarrow X}$ almost surely.
• (iv) If ${X_n,X}$ are absolutely integrable and ${{\bf E} |X_n-X| \rightarrow 0}$ as ${n \rightarrow \infty}$, show that ${X_n \rightarrow X}$ in probability. Give a counterexample to show that the converse does not necessarily hold.
• (v) (Urysohn subsequence principle) Suppose that every subsequence ${X_{n_j}}$ of ${X_n}$ has a further subsequence ${X_{n_{j_k}}}$ that converges to ${X}$ in probability. Show that ${X_n}$ also converges to ${X}$ in probability.
• (vi) Does the Urysohn subsequence principle still hold if “in probability” is replaced with “almost surely” throughout?
• (vii) If ${X_n}$ converges in probability to ${X}$, and ${F: {\bf R} \rightarrow {\bf R}}$ or ${F: {\bf C} \rightarrow {\bf C}}$ is continuous, show that ${F(X_n)}$ converges in probability to ${F(X)}$. More generally, if for each ${i=1,\dots,k}$, ${X^{(i)}_n}$ is a sequence of scalar random variables that converge in probability to ${X^{(i)}}$, and ${F: {\bf R}^k \rightarrow {\bf R}}$ or ${F: {\bf C}^k \rightarrow {\bf C}}$ is continuous, show that ${F(X^{(1)}_n,\dots,X^{(k)}_n)}$ converges in probability to ${F(X^{(1)},\dots,X^{(k)})}$. (Thus, for instance, if ${X_n}$ and ${Y_n}$ converge in probability to ${X}$ and ${Y}$ respectively, then ${X_n + Y_n}$ and ${X_n Y_n}$ converge in probability to ${X+Y}$ and ${XY}$ respectively.
• (viii) (Fatou’s lemma for convergence in probability) If ${X_n}$ are non-negative and converge in probability to ${X}$, show that ${{\bf E} X \leq \liminf_{n \rightarrow \infty} {\bf E} X_n}$.
• (ix) (Dominated convergence in probability) If ${X_n}$ converge in probability to ${X}$, and one almost surely has ${|X_n| \leq Y}$ for all ${n}$ and some absolutely integrable ${Y}$, show that ${{\bf E} X_n}$ converges to ${{\bf E} X}$.

Exercise 3 Let ${X_1,X_2,\dots}$ be a sequence of scalar random variables converging in probability to another random variable ${X}$.

• (i) Suppose that there is a random variable ${Y}$ which is independent of ${X_i}$ for each individual ${i}$. Show that ${Y}$ is also independent of ${X}$.
• (ii) Suppose that the ${X_1,X_2,\dots}$ are jointly independent. Show that ${X}$ is almost surely constant (i.e. there is a deterministic scalar ${c}$ such that ${X=c}$ almost surely).

We can now state the weak and strong law of large numbers, in the model case of iid random variables.

Theorem 4 (Law of large numbers, model case) Let ${X_1, X_2, \dots}$ be an iid sequence of copies of an absolutely integrable random variable ${X}$ (thus the ${X_i}$ are independent and all have the same distribution as ${X}$). Write ${\mu := {\bf E} X}$, and for each natural number ${n}$, let ${S_n}$ denote the random variable ${S_n := X_1 + \dots + X_n}$.

• (i) (Weak law of large numbers) The random variables ${S_n/n}$ converge in probability to ${\mu}$.
• (ii) (Strong law of large numbers) The random variables ${S_n/n}$ converge almost surely to ${\mu}$.

Informally: if ${X_1,\dots,X_n}$ are iid with mean ${\mu}$, then ${X_1 + \dots + X_n \approx \mu n}$ for ${n}$ large. Clearly the strong law of large numbers implies the weak law, but the weak law is easier to prove (and has somewhat better quantitative estimates). There are several variants of the law of large numbers, for instance when one drops the hypothesis of identical distribution, or when the random variable ${X}$ is not absolutely integrable, or if one seeks more quantitative bounds on the rate of convergence; we will discuss some of these variants below the fold.

It is instructive to compare the law of large numbers with what one can obtain from the Kolmogorov zero-one law, discussed in Notes 2. Observe that if the ${X_n}$ are real-valued, then the limit superior ${\limsup_{n \rightarrow \infty} S_n/n}$ and ${\liminf_{n \rightarrow \infty} S_n/n}$ are tail random variables in the sense that they are not affected if one changes finitely many of the ${X_n}$; in particular, events such as ${\limsup_{n \rightarrow \infty} S_n/n > t}$ are tail events for any ${t \in {\bf R}}$. From this and the zero-one law we see that there must exist deterministic quantities ${-\infty \leq \mu_- \leq \mu_+ \leq +\infty}$ such that ${\limsup_{n \rightarrow \infty} S_n/n = \mu_+}$ and ${\liminf_{n \rightarrow \infty} S_n/n = \mu_-}$ almost surely. The strong law of large numbers can then be viewed as the assertion that ${\mu_- = \mu_+ = \mu}$ when ${X}$ is absolutely integrable. On the other hand, the zero-one law argument does not require absolute integrability (and one can replace the denominator ${n}$ by other functions of ${n}$ that go to infinity as ${n \rightarrow \infty}$).

The law of large numbers asserts, roughly speaking, that the theoretical expectation ${\mu}$ of a random variable ${X}$ can be approximated by taking a large number of independent samples ${X_1,\dots,X_n}$ of ${X}$ and then forming the empirical mean ${S_n/n = \frac{X_1+\dots+X_n}{n}}$. This ability to approximate the theoretical statistics of a probability distribution through empirical data is one of the basic starting points for mathematical statistics, though this is not the focus of the course here. The tendency of statistics such as ${S_n/n}$ to cluster closely around their mean value ${\mu}$ is the simplest instance of the concentration of measure phenomenon, which is of tremendous significance not only within probability, but also in applications of probability to disciplines such as statistics, theoretical computer science, combinatorics, random matrix theory and high dimensional geometry. We will not discuss these topics much in this course, but see this previous blog post for some further discussion.

There are several ways to prove the law of large numbers (in both forms). One basic strategy is to use the moment method – controlling statistics such as ${S_n/n}$ by computing moments such as the mean ${{\bf E} S_n/n}$, variance ${{\bf E} |S_n/n - {\bf E} S_n/n|^2}$, or higher moments such as ${{\bf E} |S_n/n - {\bf E} S_n/n|^k}$ for ${k = 4, 6, \dots}$. The joint independence of the ${X_i}$ make such moments fairly easy to compute, requiring only some elementary combinatorics. A direct application of the moment method typically requires one to make a finite moment assumption such as ${{\bf E} |X|^k < \infty}$, but as we shall see, one can reduce fairly easily to this case by a truncation argument.

For the strong law of large numbers, one can also use methods relating to the theory of martingales, such as stopping time arguments and maximal inequalities; we present some classical arguments of Kolmogorov in this regard.

In the previous set of notes, we constructed the measure-theoretic notion of the Lebesgue integral, and used this to set up the probabilistic notion of expectation on a rigorous footing. In this set of notes, we will similarly construct the measure-theoretic concept of a product measure (restricting to the case of probability measures to avoid unnecessary techncialities), and use this to set up the probabilistic notion of independence on a rigorous footing. (To quote Durrett: “measure theory ends and probability theory begins with the definition of independence.”) We will be able to take virtually any collection of random variables (or probability distributions) and couple them together to be independent via the product measure construction, though for infinite products there is the slight technicality (a requirement of the Kolmogorov extension theorem) that the random variables need to range in standard Borel spaces. This is not the only way to couple together such random variables, but it is the simplest and the easiest to compute with in practice, as we shall see in the next few sets of notes.

In Notes 0, we introduced the notion of a measure space ${\Omega = (\Omega, {\mathcal F}, \mu)}$, which includes as a special case the notion of a probability space. By selecting one such probability space ${(\Omega,{\mathcal F},\mu)}$ as a sample space, one obtains a model for random events and random variables, with random events ${E}$ being modeled by measurable sets ${E_\Omega}$ in ${{\mathcal F}}$, and random variables ${X}$ taking values in a measurable space ${R}$ being modeled by measurable functions ${X_\Omega: \Omega \rightarrow R}$. We then defined some basic operations on these random events and variables:

• Given events ${E,F}$, we defined the conjunction ${E \wedge F}$, the disjunction ${E \vee F}$, and the complement ${\overline{E}}$. For countable families ${E_1,E_2,\dots}$ of events, we similarly defined ${\bigwedge_{n=1}^\infty E_n}$ and ${\bigvee_{n=1}^\infty E_n}$. We also defined the empty event ${\emptyset}$ and the sure event ${\overline{\emptyset}}$, and what it meant for two events to be equal.
• Given random variables ${X_1,\dots,X_n}$ in ranges ${R_1,\dots,R_n}$ respectively, and a measurable function ${F: R_1 \times \dots \times R_n \rightarrow S}$, we defined the random variable ${F(X_1,\dots,X_n)}$ in range ${S}$. (As the special case ${n=0}$ of this, every deterministic element ${s}$ of ${S}$ was also a random variable taking values in ${S}$.) Given a relation ${P: R_1 \times \dots \times R_n \rightarrow \{\hbox{true}, \hbox{false}\}}$, we similarly defined the event ${P(X_1,\dots,X_n)}$. Conversely, given an event ${E}$, we defined the indicator random variable ${1_E}$. Finally, we defined what it meant for two random variables to be equal.
• Given an event ${E}$, we defined its probability ${{\bf P}(E)}$.

These operations obey various axioms; for instance, the boolean operations on events obey the axioms of a Boolean algebra, and the probabilility function ${E \mapsto {\bf P}(E)}$ obeys the Kolmogorov axioms. However, we will not focus on the axiomatic approach to probability theory here, instead basing the foundations of probability theory on the sample space models as discussed in Notes 0. (But see this previous post for a treatment of one such axiomatic approach.)

It turns out that almost all of the other operations on random events and variables we need can be constructed in terms of the above basic operations. In particular, this allows one to safely extend the sample space in probability theory whenever needed, provided one uses an extension that respects the above basic operations; this is an important operation when one needs to add new sources of randomness to an existing system of events and random variables, or to couple together two separate such systems into a joint system that extends both of the original systems. We gave a simple example of such an extension in the previous notes, but now we give a more formal definition:

Definition 1 Suppose that we are using a probability space ${\Omega = (\Omega, {\mathcal F}, \mu)}$ as the model for a collection of events and random variables. An extension of this probability space is a probability space ${\Omega' = (\Omega', {\mathcal F}', \mu')}$, together with a measurable map ${\pi: \Omega' \rightarrow \Omega}$ (sometimes called the factor map) which is probability-preserving in the sense that

$\displaystyle \mu'( \pi^{-1}(E) ) = \mu(E) \ \ \ \ \ (1)$

for all ${E \in {\mathcal F}}$. (Caution: this does not imply that ${\mu(\pi(F)) = \mu'(F)}$ for all ${F \in {\mathcal F}'}$ – why not?)

An event ${E}$ which is modeled by a measurable subset ${E_\Omega}$ in the sample space ${\Omega}$, will be modeled by the measurable set ${E_{\Omega'} := \pi^{-1}(E_\Omega)}$ in the extended sample space ${\Omega'}$. Similarly, a random variable ${X}$ taking values in some range ${R}$ that is modeled by a measurable function ${X_\Omega: \Omega \rightarrow R}$ in ${\Omega}$, will be modeled instead by the measurable function ${X_{\Omega'} := X_\Omega \circ \pi}$ in ${\Omega'}$. We also allow the extension ${\Omega'}$ to model additional events and random variables that were not modeled by the original sample space ${\Omega}$ (indeed, this is one of the main reasons why we perform extensions in probability in the first place).

Thus, for instance, the sample space ${\Omega'}$ in Example 3 of the previous post is an extension of the sample space ${\Omega}$ in that example, with the factor map ${\pi: \Omega' \rightarrow \Omega}$ given by the first coordinate projection ${\pi(i,j) := i}$. One can verify that all of the basic operations on events and random variables listed above are unaffected by the above extension (with one caveat, see remark below). For instance, the conjunction ${E \wedge F}$ of two events can be defined via the original model ${\Omega}$ by the formula

$\displaystyle (E \wedge F)_\Omega := E_\Omega \cap F_\Omega$

or via the extension ${\Omega'}$ via the formula

$\displaystyle (E \wedge F)_{\Omega'} := E_{\Omega'} \cap F_{\Omega'}.$

The two definitions are consistent with each other, thanks to the obvious set-theoretic identity

$\displaystyle \pi^{-1}( E_\Omega \cap F_\Omega ) = \pi^{-1}(E_\Omega) \cap \pi^{-1}(F_\Omega).$

Similarly, the assumption (1) is precisely what is needed to ensure that the probability ${\mathop{\bf P}(E)}$ of an event remains unchanged when one replaces a sample space model with an extension. We leave the verification of preservation of the other basic operations described above under extension as exercises to the reader.

Remark 2 There is one minor exception to this general rule if we do not impose the additional requirement that the factor map ${\pi}$ is surjective. Namely, for non-surjective ${\pi}$, it can become possible that two events ${E, F}$ are unequal in the original sample space model, but become equal in the extension (and similarly for random variables), although the converse never happens (events that are equal in the original sample space always remain equal in the extension). For instance, let ${\Omega}$ be the discrete probability space ${\{a,b\}}$ with ${p_a=1}$ and ${p_b=0}$, and let ${\Omega'}$ be the discrete probability space ${\{ a'\}}$ with ${p'_{a'}=1}$, and non-surjective factor map ${\pi: \Omega' \rightarrow \Omega}$ defined by ${\pi(a') := a}$. Then the event modeled by ${\{b\}}$ in ${\Omega}$ is distinct from the empty event when viewed in ${\Omega}$, but becomes equal to that event when viewed in ${\Omega'}$. Thus we see that extending the sample space by a non-surjective factor map can identify previously distinct events together (though of course, being probability preserving, this can only happen if those two events were already almost surely equal anyway). This turns out to be fairly harmless though; while it is nice to know if two given events are equal, or if they differ by a non-null event, it is almost never useful to know that two events are unequal if they are already almost surely equal. Alternatively, one can add the additional requirement of surjectivity in the definition of an extension, which is also a fairly harmless constraint to impose (this is what I chose to do in this previous set of notes).

Roughly speaking, one can define probability theory as the study of those properties of random events and random variables that are model-independent in the sense that they are preserved by extensions. For instance, the cardinality ${|E_\Omega|}$ of the model ${E_\Omega}$ of an event ${E}$ is not a concept within the scope of probability theory, as it is not preserved by extensions: continuing Example 3 from Notes 0, the event ${E}$ that a die roll ${X}$ is even is modeled by a set ${E_\Omega = \{2,4,6\}}$ of cardinality ${3}$ in the original sample space model ${\Omega}$, but by a set ${E_{\Omega'} = \{2,4,6\} \times \{1,2,3,4,5,6\}}$ of cardinality ${18}$ in the extension. Thus it does not make sense in the context of probability theory to refer to the “cardinality of an event ${E}$“.

On the other hand, the supremum ${\sup_n X_n}$ of a collection of random variables ${X_n}$ in the extended real line ${[-\infty,+\infty]}$ is a valid probabilistic concept. This can be seen by manually verifying that this operation is preserved under extension of the sample space, but one can also see this by defining the supremum in terms of existing basic operations. Indeed, note from Exercise 24 of Notes 0 that a random variable ${X}$ in the extended real line is completely specified by the threshold events ${(X \leq t)}$ for ${t \in {\bf R}}$; in particular, two such random variables ${X,Y}$ are equal if and only if the events ${(X \leq t)}$ and ${(Y \leq t)}$ are surely equal for all ${t}$. From the identity

$\displaystyle (\sup_n X_n \leq t) = \bigwedge_{n=1}^\infty (X_n \leq t)$

we thus see that one can completely specify ${\sup_n X_n}$ in terms of ${X_n}$ using only the basic operations provided in the above list (and in particular using the countable conjunction ${\bigwedge_{n=1}^\infty}$.) Of course, the same considerations hold if one replaces supremum, by infimum, limit superior, limit inferior, or (if it exists) the limit.

In this set of notes, we will define some further important operations on scalar random variables, in particular the expectation of these variables. In the sample space models, expectation corresponds to the notion of integration on a measure space. As we will need to use both expectation and integration in this course, we will thus begin by quickly reviewing the basics of integration on a measure space, although we will then translate the key results of this theory into probabilistic language.

As the finer details of the Lebesgue integral construction are not the core focus of this probability course, some of the details of this construction will be left to exercises. See also Chapter 1 of Durrett, or these previous blog notes, for a more detailed treatment.

Starting this week, I will be teaching an introductory graduate course (Math 275A) on probability theory here at UCLA. While I find myself using probabilistic methods routinely nowadays in my research (for instance, the probabilistic concept of Shannon entropy played a crucial role in my recent paper on the Chowla and Elliott conjectures, and random multiplicative functions similarly played a central role in the paper on the Erdos discrepancy problem), this will actually be the first time I will be teaching a course on probability itself (although I did give a course on random matrix theory some years ago that presumed familiarity with graduate-level probability theory). As such, I will be relying primarily on an existing textbook, in this case Durrett’s Probability: Theory and Examples. I still need to prepare lecture notes, though, and so I thought I would continue my practice of putting my notes online, although in this particular case they will be less detailed or complete than with other courses, as they will mostly be focusing on those topics that are not already comprehensively covered in the text of Durrett. Below the fold are my first such set of notes, concerning the classical measure-theoretic foundations of probability. (I wrote on these foundations also in this previous blog post, but in that post I already assumed that the reader was familiar with measure theory and basic probability, whereas in this course not every student will have a strong background in these areas.)

Note: as this set of notes is primarily concerned with foundational issues, it will contain a large number of pedantic (and nearly trivial) formalities and philosophical points. We dwell on these technicalities in this set of notes primarily so that they are out of the way in later notes, when we work with the actual mathematics of probability, rather than on the supporting foundations of that mathematics. In particular, the excessively formal and philosophical language in this set of notes will not be replicated in later notes.

In analytic number theory, there is a well known analogy between the prime factorisation of a large integer, and the cycle decomposition of a large permutation; this analogy is central to the topic of “anatomy of the integers”, as discussed for instance in this survey article of Granville. Consider for instance the following two parallel lists of facts (stated somewhat informally). Firstly, some facts about the prime factorisation of large integers:

• Every positive integer ${m}$ has a prime factorisation

$\displaystyle m = p_1 p_2 \dots p_r$

into (not necessarily distinct) primes ${p_1,\dots,p_r}$, which is unique up to rearrangement. Taking logarithms, we obtain a partition

$\displaystyle \log m = \log p_1 + \log p_2 + \dots + \log p_r$

of ${\log m}$.

• (Prime number theorem) A randomly selected integer ${m}$ of size ${m \sim N}$ will be prime with probability ${\approx \frac{1}{\log N}}$ when ${N}$ is large.
• If ${m \sim N}$ is a randomly selected large integer of size ${N}$, and ${p = p_i}$ is a randomly selected prime factor of ${m = p_1 \dots p_r}$ (with each index ${i}$ being chosen with probability ${\frac{\log p_i}{\log m}}$), then ${\log p_i}$ is approximately uniformly distributed between ${0}$ and ${\log N}$. (See Proposition 9 of this previous blog post.)
• The set of real numbers ${\{ \frac{\log p_i}{\log m}: i=1,\dots,r \}}$ arising from the prime factorisation ${m = p_1 \dots p_r}$ of a large random number ${m \sim N}$ converges (away from the origin, and in a suitable weak sense) to the Poisson-Dirichlet process in the limit ${N \rightarrow \infty}$. (See the previously mentioned blog post for a definition of the Poisson-Dirichlet process, and a proof of this claim.)

Now for the facts about the cycle decomposition of large permutations:

• Every permutation ${\sigma \in S_n}$ has a cycle decomposition

$\displaystyle \sigma = C_1 \dots C_r$

into disjoint cycles ${C_1,\dots,C_r}$, which is unique up to rearrangement, and where we count each fixed point of ${\sigma}$ as a cycle of length ${1}$. If ${|C_i|}$ is the length of the cycle ${C_i}$, we obtain a partition

$\displaystyle n = |C_1| + \dots + |C_r|$

of ${n}$.

• (Prime number theorem for permutations) A randomly selected permutation of ${S_n}$ will be an ${n}$-cycle with probability exactly ${1/n}$. (This was noted in this previous blog post.)
• If ${\sigma}$ is a random permutation in ${S_n}$, and ${C_i}$ is a randomly selected cycle of ${\sigma}$ (with each ${i}$ being selected with probability ${|C_i|/n}$), then ${|C_i|}$ is exactly uniformly distributed on ${\{1,\dots,n\}}$. (See Proposition 8 of this blog post.)
• The set of real numbers ${\{ \frac{|C_i|}{n} \}}$ arising from the cycle decomposition ${\sigma = C_1 \dots C_r}$ of a random permutation ${\sigma \in S_n}$ converges (in a suitable sense) to the Poisson-Dirichlet process in the limit ${n \rightarrow \infty}$. (Again, see this previous blog post for details.)

See this previous blog post (or the aforementioned article of Granville, or the Notices article of Arratia, Barbour, and Tavaré) for further exploration of the analogy between prime factorisation of integers and cycle decomposition of permutations.

There is however something unsatisfying about the analogy, in that it is not clear why there should be such a kinship between integer prime factorisation and permutation cycle decomposition. It turns out that the situation is clarified if one uses another fundamental analogy in number theory, namely the analogy between integers and polynomials ${P \in {\mathbf F}_q[T]}$ over a finite field ${{\mathbf F}_q}$, discussed for instance in this previous post; this is the simplest case of the more general function field analogy between number fields and function fields. Just as we restrict attention to positive integers when talking about prime factorisation, it will be reasonable to restrict attention to monic polynomials ${P}$. We then have another analogous list of facts, proven very similarly to the corresponding list of facts for the integers:

• Every monic polynomial ${f \in {\mathbf F}_q[T]}$ has a factorisation

$\displaystyle f = P_1 \dots P_r$

into irreducible monic polynomials ${P_1,\dots,P_r \in {\mathbf F}_q[T]}$, which is unique up to rearrangement. Taking degrees, we obtain a partition

$\displaystyle \hbox{deg} f = \hbox{deg} P_1 + \dots + \hbox{deg} P_r$

of ${\hbox{deg} f}$.

• (Prime number theorem for polynomials) A randomly selected monic polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ will be irreducible with probability ${\approx \frac{1}{n}}$ when ${q}$ is fixed and ${n}$ is large.
• If ${f \in {\mathbf F}_q[T]}$ is a random monic polynomial of degree ${n}$, and ${P_i}$ is a random irreducible factor of ${f = P_1 \dots P_r}$ (with each ${i}$ selected with probability ${\hbox{deg} P_i / n}$), then ${\hbox{deg} P_i}$ is approximately uniformly distributed in ${\{1,\dots,n\}}$ when ${q}$ is fixed and ${n}$ is large.
• The set of real numbers ${\{ \hbox{deg} P_i / n \}}$ arising from the factorisation ${f = P_1 \dots P_r}$ of a randomly selected polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ converges (in a suitable sense) to the Poisson-Dirichlet process when ${q}$ is fixed and ${n}$ is large.

The above list of facts addressed the large ${n}$ limit of the polynomial ring ${{\mathbf F}_q[T]}$, where the order ${q}$ of the field is held fixed, but the degrees of the polynomials go to infinity. This is the limit that is most closely analogous to the integers ${{\bf Z}}$. However, there is another interesting asymptotic limit of polynomial rings to consider, namely the large ${q}$ limit where it is now the degree ${n}$ that is held fixed, but the order ${q}$ of the field goes to infinity. Actually to simplify the exposition we will use the slightly more restrictive limit where the characteristic ${p}$ of the field goes to infinity (again keeping the degree ${n}$ fixed), although all of the results proven below for the large ${p}$ limit turn out to be true as well in the large ${q}$ limit.

The large ${q}$ (or large ${p}$) limit is technically a different limit than the large ${n}$ limit, but in practice the asymptotic statistics of the two limits often agree quite closely. For instance, here is the prime number theorem in the large ${q}$ limit:

Theorem 1 (Prime number theorem) The probability that a random monic polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ is irreducible is ${\frac{1}{n}+o(1)}$ in the limit where ${n}$ is fixed and the characteristic ${p}$ goes to infinity.

Proof: There are ${q^n}$ monic polynomials ${f \in {\mathbf F}_q[T]}$ of degree ${n}$. If ${f}$ is irreducible, then the ${n}$ zeroes of ${f}$ are distinct and lie in the finite field ${{\mathbf F}_{q^n}}$, but do not lie in any proper subfield of that field. Conversely, every element ${\alpha}$ of ${{\mathbf F}_{q^n}}$ that does not lie in a proper subfield is the root of a unique monic polynomial in ${{\mathbf F}_q[T]}$ of degree ${f}$ (the minimal polynomial of ${\alpha}$). Since the union of all the proper subfields of ${{\mathbf F}_{q^n}}$ has size ${o(q^n)}$, the total number of irreducible polynomials of degree ${n}$ is thus ${\frac{q^n - o(q^n)}{n}}$, and the claim follows. $\Box$

Remark 2 The above argument and inclusion-exclusion in fact gives the well known exact formula ${\frac{1}{n} \sum_{d|n} \mu(\frac{n}{d}) q^d}$ for the number of irreducible monic polynomials of degree ${n}$.

Now we can give a precise connection between the cycle distribution of a random permutation, and (the large ${p}$ limit of) the irreducible factorisation of a polynomial, giving a (somewhat indirect, but still connected) link between permutation cycle decomposition and integer factorisation:

Theorem 3 The partition ${\{ \hbox{deg}(P_1), \dots, \hbox{deg}(P_r) \}}$ of a random monic polynomial ${f= P_1 \dots P_r\in {\mathbf F}_q[T]}$ of degree ${n}$ converges in distribution to the partition ${\{ |C_1|, \dots, |C_r|\}}$ of a random permutation ${\sigma = C_1 \dots C_r \in S_n}$ of length ${n}$, in the limit where ${n}$ is fixed and the characteristic ${p}$ goes to infinity.

We can quickly prove this theorem as follows. We first need a basic fact:

Lemma 4 (Most polynomials square-free in large ${q}$ limit) A random monic polynomial ${f \in {\mathbf F}_q[T]}$ of degree ${n}$ will be square-free with probability ${1-o(1)}$ when ${n}$ is fixed and ${q}$ (or ${p}$) goes to infinity. In a similar spirit, two randomly selected monic polynomials ${f,g}$ of degree ${n,m}$ will be coprime with probability ${1-o(1)}$ if ${n,m}$ are fixed and ${q}$ or ${p}$ goes to infinity.

Proof: For any polynomial ${g}$ of degree ${m}$, the probability that ${f}$ is divisible by ${g^2}$ is at most ${1/q^{2m}}$. Summing over all polynomials of degree ${1 \leq m \leq n/2}$, and using the union bound, we see that the probability that ${f}$ is not squarefree is at most ${\sum_{1 \leq m \leq n/2} \frac{q^m}{q^{2m}} = o(1)}$, giving the first claim. For the second, observe from the first claim (and the fact that ${fg}$ has only a bounded number of factors) that ${fg}$ is squarefree with probability ${1-o(1)}$, giving the claim. $\Box$

Now we can prove the theorem. Elementary combinatorics tells us that the probability of a random permutation ${\sigma \in S_n}$ consisting of ${c_k}$ cycles of length ${k}$ for ${k=1,\dots,r}$, where ${c_k}$ are nonnegative integers with ${\sum_{k=1}^r k c_k = n}$, is precisely

$\displaystyle \frac{1}{\prod_{k=1}^r c_k! k^{c_k}},$

since there are ${\prod_{k=1}^r c_k! k^{c_k}}$ ways to write a given tuple of cycles ${C_1,\dots,C_r}$ in cycle notation in nondecreasing order of length, and ${n!}$ ways to select the labels for the cycle notation. On the other hand, by Theorem 1 (and using Lemma 4 to isolate the small number of cases involving repeated factors) the number of monic polynomials of degree ${n}$ that are the product of ${c_k}$ irreducible polynomials of degree ${k}$ is

$\displaystyle \frac{1}{\prod_{k=1}^r c_k!} \prod_{k=1}^r ( (\frac{1}{k}+o(1)) q^k )^{c_k} + o( q^n )$

which simplifies to

$\displaystyle \frac{1+o(1)}{\prod_{k=1}^r c_k! k^{c_k}} q^n,$

and the claim follows.

This was a fairly short calculation, but it still doesn’t quite explain why there is such a link between the cycle decomposition ${\sigma = C_1 \dots C_r}$ of permutations and the factorisation ${f = P_1 \dots P_r}$ of a polynomial. One immediate thought might be to try to link the multiplication structure of permutations in ${S_n}$ with the multiplication structure of polynomials; however, these structures are too dissimilar to set up a convincing analogy. For instance, the multiplication law on polynomials is abelian and non-invertible, whilst the multiplication law on ${S_n}$ is (extremely) non-abelian but invertible. Also, the multiplication of a degree ${n}$ and a degree ${m}$ polynomial is a degree ${n+m}$ polynomial, whereas the group multiplication law on permutations does not take a permutation in ${S_n}$ and a permutation in ${S_m}$ and return a permutation in ${S_{n+m}}$.

I recently found (after some discussions with Ben Green) what I feel to be a satisfying conceptual (as opposed to computational) explanation of this link, which I will place below the fold.

I’ve just uploaded to the arXiv my paper “Inverse theorems for sets and measures of polynomial growth“. This paper was motivated by two related questions. The first question was to obtain a qualitatively precise description of the sets of polynomial growth that arise in Gromov’s theorem, in much the same way that Freiman’s theorem (and its generalisations) provide a qualitatively precise description of sets of small doubling. The other question was to obtain a non-abelian analogue of inverse Littlewood-Offord theory.

Let me discuss the former question first. Gromov’s theorem tells us that if a finite subset ${A}$ of a group ${G}$ exhibits polynomial growth in the sense that ${|A^n|}$ grows polynomially in ${n}$, then the group generated by ${A}$ is virtually nilpotent (the converse direction also true, and is relatively easy to establish). This theorem has been strengthened a number of times over the years. For instance, a few years ago, I proved with Shalom that the condition that ${|A^n|}$ grew polynomially in ${n}$ could be replaced by ${|A^n| \leq C n^d}$ for a single ${n}$, as long as ${n}$ was sufficiently large depending on ${C,d}$ (in fact we gave a fairly explicit quantitative bound on how large ${n}$ needed to be). A little more recently, with Breuillard and Green, the condition ${|A^n| \leq C n^d}$ was weakened to ${|A^n| \leq n^d |A|}$, that is to say it sufficed to have polynomial relative growth at a finite scale. In fact, the latter paper gave more information on ${A}$ in this case, roughly speaking it showed (at least in the case when ${A}$ was a symmetric neighbourhood of the identity) that ${A^n}$ was “commensurate” with a very structured object known as a coset nilprogression. This can then be used to establish further control on ${A}$. For instance, it was recently shown by Breuillard and Tointon (again in the symmetric case) that if ${|A^n| \leq n^d |A|}$ for a single ${n}$ that was sufficiently large depending on ${d}$, then all the ${A^{n'}}$ for ${n' \geq n}$ have a doubling constant bounded by a bound ${C_d}$ depending only on ${d}$, thus ${|A^{2n'}| \leq C_d |A^{n'}|}$ for all ${n' \geq n}$.

In this paper we are able to refine this analysis a bit further; under the same hypotheses, we can show an estimate of the form

$\displaystyle \log |A^{n'}| = \log |A^n| + f( \log n' - \log n ) + O_d(1)$

for all ${n' \geq n}$ and some piecewise linear, continuous, non-decreasing function ${f: [0,+\infty) \rightarrow [0,+\infty)}$ with ${f(0)=0}$, where the error ${O_d(1)}$ is bounded by a constant depending only on ${d}$, and where ${f}$ has at most ${O_d(1)}$ pieces, each of which has a slope that is a natural number of size ${O_d(1)}$. To put it another way, the function ${n' \mapsto |A^{n'}|}$ for ${n' \geq n}$ behaves (up to multiplicative constants) like a piecewise polynomial function, where the degree of the function and number of pieces is bounded by a constant depending on ${d}$.

One could ask whether the function ${f}$ has any convexity or concavity properties. It turns out that it can exhibit either convex or concave behaviour (or a combination of both). For instance, if ${A}$ is contained in a large finite group, then ${n \mapsto |A^n|}$ will eventually plateau to a constant, exhibiting concave behaviour. On the other hand, in nilpotent groups one can see convex behaviour; for instance, in the Heisenberg group ${\begin{pmatrix}{} {1} {\mathbf Z} {\mathbf Z} \\ {0} {1} {\mathbf Z} \\ {0} {1} \end{pmatrix}}$, if one sets ${A}$ to be a set of matrices of the form ${\begin{pmatrix} 1 & O(N) & O(N^3) \\ 0 & 1 & O(N) \\ 0 & 0 & 1 \end{pmatrix}}$ for some large ${N}$ (abusing the ${O()}$ notation somewhat), then ${n \mapsto A^n}$ grows cubically for ${n \leq N}$ but then grows quartically for ${n > N}$.

To prove this proposition, it turns out (after using a somewhat difficult inverse theorem proven previously by Breuillard, Green, and myself) that one has to analyse the volume growth ${n \mapsto |P^n|}$ of nilprogressions ${P}$. In the “infinitely proper” case where there are no unexpected relations between the generators of the nilprogression, one can lift everything to a simply connected Lie group (where one can take logarithms and exploit the Baker-Campbell-Hausdorff formula heavily), eventually describing ${P^n}$ with fair accuracy by a certain convex polytope with vertices depending polynomially on ${n}$, which implies that ${|P^n|}$ depends polynomially on ${n}$ up to constants. If one is not in the “infinitely proper” case, then at some point ${n_0}$ the nilprogression ${P^{n_0}}$ develops a “collision”, but then one can use this collision to show (after some work) that the dimension of the “Lie model” of ${P^{n_0}}$ has dropped by at least one from the dimension of ${P}$ (the notion of a Lie model being developed in the previously mentioned paper of Breuillard, Greenm, and myself), so that this sort of collision can only occur a bounded number of times, with essentially polynomial volume growth behaviour between these collisions.

The arguments also give a precise description of the location of a set ${A}$ for which ${A^n}$ grows polynomially in ${n}$. In the symmetric case, what ends up happening is that ${A^n}$ becomes commensurate to a “coset nilprogression” ${HP}$ of bounded rank and nilpotency class, whilst ${A}$ is “virtually” contained in a scaled down version ${HP^{1/n}}$ of that nilprogression. What “virtually” means is a little complicated; roughly speaking, it means that there is a set ${X}$ of bounded cardinality such that ${aXHP^{1/n} \approx XHP^{1/n}}$ for all ${a \in A}$. Conversely, if ${A}$ is virtually contained in ${HP^{1/n}}$, then ${A^n}$ is commensurate to ${HP}$ (and more generally, ${A^{mn}}$ is commensurate to ${HP^m}$ for any natural number ${m}$), giving quite a (qualitatively) precise description of ${A}$ in terms of coset nilprogressions.

The main tool used to prove these results is the structure theorem for approximate groups established by Breuillard, Green, and myself, which roughly speaking asserts that approximate groups are always commensurate with coset nilprogressions. A key additional trick is a pigeonholing argument of Sanders, which in this context is the assertion that if ${A^n}$ is comparable to ${A^{2n}}$, then there is an ${n'}$ between ${n}$ and ${2n}$ such that ${A \cdot A^{n'}}$ is very close in size to ${A^{n'}}$ (up to a relative error of ${1/n}$). It is this fact, together with the comparability of ${A^{n'}}$ to a coset nilprogression ${HP}$, that allows us (after some combinatorial argument) to virtually place ${A}$ inside ${HP^{1/n}}$.

Similar arguments apply when discussing iterated convolutions ${\mu^{*n}}$ of (symmetric) probability measures on a (discrete) group ${G}$, rather than combinatorial powers ${A^n}$ of a finite set. Here, the analogue of volume ${A^n}$ is given by the negative power ${\| \mu^{*n} \|_{\ell^2}^{-2}}$ of the ${\ell^2}$ norm of ${\mu^{*n}}$ (thought of as a non-negative function on ${G}$ of total mass 1). One can also work with other norms here than ${\ell^2}$, but this norm has some minor technical conveniences (and other measures of the “spread” of ${\mu^{*n}}$ end up being more or less equivalent for our purposes). There is an analogous structure theorem that asserts that if ${\mu^{*n}}$ spreads at most polynomially in ${n}$, then ${\mu^{*n}}$ is “commensurate” with the uniform probability distribution on a coset progression ${HP}$, and ${\mu}$ itself is largely concentrated near ${HP^{1/\sqrt{n}}}$. The factor of ${\sqrt{n}}$ here is the familiar scaling factor in random walks that arises for instance in the central limit theorem. The proof of (the precise version of) this statement proceeds similarly to the combinatorial case, using pigeonholing to locate a scale ${n'}$ where ${\mu *\mu^{n'}}$ has almost the same ${\ell^2}$ norm as ${\mu^{n'}}$.

A special case of this theory occurs when ${\mu}$ is the uniform probability measure on ${n}$ elements ${v_1,\dots,v_n}$ of ${G}$ and their inverses. The probability measure ${\mu^{*n}}$ is then the distribution of a random product ${w_1 \dots w_n}$, where each ${w_i}$ is equal to one of ${v_{j_i}}$ or its inverse ${v_{j_i}^{-1}}$, selected at random with ${j_i}$ drawn uniformly from ${\{1,\dots,n\}}$ with replacement. This is very close to the Littlewood-Offord situation of random products ${u_1 \dots u_n}$ where each ${u_i}$ is equal to ${v_i}$ or ${v_i^{-1}}$ selected independently at random (thus ${j_i}$ is now fixed to equal ${i}$ rather than being randomly drawn from ${\{1,\dots,n\}}$. In the case when ${G}$ is abelian, it turns out that a little bit of Fourier analysis shows that these two random walks have “comparable” distributions in a certain ${\ell^2}$ sense. As a consequence, the results in this paper can be used to recover an essentially optimal abelian inverse Littlewood-Offord theorem of Nguyen and Vu. In the nonabelian case, the only Littlewood-Offord theorem I am aware of is a recent result of Tiep and Vu for matrix groups, but in this case I do not know how to relate the above two random walks to each other, and so we can only obtain an analogue of the Tiep-Vu results for the symmetrised random walk ${w_1 \dots w_n}$ instead of the ordered random walk ${u_1 \dots u_n}$.

Hoi Nguyen, Van Vu, and myself have just uploaded to the arXiv our paper “Random matrices: tail bounds for gaps between eigenvalues“. This is a followup paper to my recent paper with Van in which we showed that random matrices ${M_n}$ of Wigner type (such as the adjacency matrix of an Erdös-Renyi graph) asymptotically almost surely had simple spectrum. In the current paper, we push the method further to show that the eigenvalues are not only distinct, but are (with high probability) separated from each other by some negative power ${n^{-A}}$ of ${n}$. This follows the now standard technique of replacing any appearance of discrete Littlewood-Offord theory (a key ingredient in our previous paper) with its continuous analogue (inverse theorems for small ball probability). For general Wigner-type matrices ${M_n}$ (in which the matrix entries are not normalised to have mean zero), we can use the inverse Littlewood-Offord theorem of Nguyen and Vu to obtain (under mild conditions on ${M_n}$) a result of the form

$\displaystyle {\bf P} (\lambda_{i+1}(M_n) - \lambda_i(M_n) \leq n^{-A} ) \leq n^{-B}$

for any ${B}$ and ${i}$, if ${A}$ is sufficiently large depending on ${B}$ (in a linear fashion), and ${n}$ is sufficiently large depending on ${B}$. The point here is that ${B}$ can be made arbitrarily large, and also that no continuity or smoothness hypothesis is made on the distribution of the entries. (In the continuous case, one can use the machinery of Wegner estimates to obtain results of this type, as was done in a paper of Erdös, Schlein, and Yau.)

In the mean zero case, it becomes more efficient to use an inverse Littlewood-Offord theorem of Rudelson and Vershynin to obtain (with the normalisation that the entries of ${M_n}$ have unit variance, so that the eigenvalues of ${M_n}$ are ${O(\sqrt{n})}$ with high probability), giving the bound

$\displaystyle {\bf P} (\lambda_{i+1}(M_n) - \lambda_i(M_n) \leq \delta / \sqrt{n} ) \ll \delta \ \ \ \ \ (1)$

for ${\delta \geq n^{-O(1)}}$ (one also has good results of this type for smaller values of ${\delta}$). This is only optimal in the regime ${\delta \sim 1}$; we expect to establish some eigenvalue repulsion, improving the RHS to ${\delta^2}$ for real matrices and ${\delta^3}$ for complex matrices, but this appears to be a more difficult task (possibly requiring some quadratic inverse Littlewood-Offord theory, rather than just linear inverse Littlewood-Offord theory). However, we can get some repulsion if one works with larger gaps, getting a result roughly of the form

$\displaystyle {\bf P} (\lambda_{i+k}(M_n) - \lambda_i(M_n) \leq \delta / \sqrt{n} ) \ll \delta^{ck^2}$

for any fixed ${k \geq 1}$ and some absolute constant ${c>0}$ (which we can asymptotically make to be ${1/3}$ for large ${k}$, though it ought to be as large as ${1}$), by using a higher-dimensional version of the Rudelson-Vershynin inverse Littlewood-Offord theorem.

In the case of Erdös-Renyi graphs, we don’t have mean zero and the Rudelson-Vershynin Littlewood-Offord theorem isn’t quite applicable, but by working carefully through the approach based on the Nguyen-Vu theorem we can almost recover (1), except for a loss of ${n^{o(1)}}$ on the RHS.

As a sample applications of the eigenvalue separation results, we can now obtain some information about eigenvectors; for instance, we can show that the components of the eigenvectors all have magnitude at least ${n^{-A}}$ for some ${A}$ with high probability. (Eigenvectors become much more stable, and able to be studied in isolation, once their associated eigenvalue is well separated from the other eigenvalues; see this previous blog post for more discussion.)

We now move away from the world of multiplicative prime number theory covered in Notes 1 and Notes 2, and enter the wider, and complementary, world of non-multiplicative prime number theory, in which one studies statistics related to non-multiplicative patterns, such as twins ${n,n+2}$. This creates a major jump in difficulty; for instance, even the most basic multiplicative result about the primes, namely Euclid’s theorem that there are infinitely many of them, remains unproven for twin primes. Of course, the situation is even worse for stronger results, such as Euler’s theorem, Dirichlet’s theorem, or the prime number theorem. Finally, even many multiplicative questions about the primes remain open. The most famous of these is the Riemann hypothesis, which gives the asymptotic ${\sum_{n \leq x} \Lambda(n) = x + O( \sqrt{x} \log^2 x )}$ (see Proposition 24 from Notes 2). But even if one assumes the Riemann hypothesis, the precise distribution of the error term ${O( \sqrt{x} \log^2 x )}$ in the above asymptotic (or in related asymptotics, such as for the sum ${\sum_{x \leq n < x+y} \Lambda(n)}$ that measures the distribution of primes in short intervals) is not entirely clear.

Despite this, we do have a number of extremely convincing and well supported models for the primes (and related objects) that let us predict what the answer to many prime number theory questions (both multiplicative and non-multiplicative) should be, particularly in asymptotic regimes where one can work with aggregate statistics about the primes, rather than with a small number of individual primes. These models are based on taking some statistical distribution related to the primes (e.g. the primality properties of a randomly selected ${k}$-tuple), and replacing that distribution by a model distribution that is easy to compute with (e.g. a distribution with strong joint independence properties). One can then predict the asymptotic value of various (normalised) statistics about the primes by replacing the relevant statistical distributions of the primes with their simplified models. In this non-rigorous setting, many difficult conjectures on the primes reduce to relatively simple calculations; for instance, all four of the (still unsolved) Landau problems may now be justified in the affirmative by one or more of these models. Indeed, the models are so effective at this task that analytic number theory is in the curious position of being able to confidently predict the answer to a large proportion of the open problems in the subject, whilst not possessing a clear way forward to rigorously confirm these answers!

As it turns out, the models for primes that have turned out to be the most accurate in practice are random models, which involve (either explicitly or implicitly) one or more random variables. This is despite the prime numbers being obviously deterministic in nature; no coins are flipped or dice rolled to create the set of primes. The point is that while the primes have a lot of obvious multiplicative structure (for instance, the product of two primes is never another prime), they do not appear to exhibit much discernible non-multiplicative structure asymptotically, in the sense that they rarely exhibit statistical anomalies in the asymptotic limit that cannot be easily explained in terms of the multiplicative properties of the primes. As such, when considering non-multiplicative statistics of the primes, the primes appear to behave pseudorandomly, and can thus be modeled with reasonable accuracy by a random model. And even for multiplicative problems, which are in principle controlled by the zeroes of the Riemann zeta function, one can obtain good predictions by positing various pseudorandomness properties of these zeroes, so that the distribution of these zeroes can be modeled by a random model.

Of course, one cannot expect perfect accuracy when replicating a deterministic set such as the primes by a probabilistic model of that set, and each of the heuristic models we discuss below have some limitations to the range of statistics about the primes that they can expect to track with reasonable accuracy. For instance, many of the models about the primes do not fully take into account the multiplicative structure of primes, such as the connection with a zeta function with a meromorphic continuation to the entire complex plane; at the opposite extreme, we have the GUE hypothesis which appears to accurately model the zeta function, but does not capture such basic properties of the primes as the fact that the primes are all natural numbers. Nevertheless, each of the models described below, when deployed within their sphere of reasonable application, has (possibly after some fine-tuning) given predictions that are in remarkable agreement with numerical computation and with known rigorous theoretical results, as well as with other models in overlapping spheres of application; they are also broadly compatible with the general heuristic (discussed in this previous post) that in the absence of any exploitable structure, asymptotic statistics should default to the most “uniform”, “pseudorandom”, or “independent” distribution allowable.

As hinted at above, we do not have a single unified model for the prime numbers (other than the primes themselves, of course), but instead have an overlapping family of useful models that each appear to accurately describe some, but not all, aspects of the prime numbers. In this set of notes, we will discuss four such models:

1. The Cramér random model and its refinements, which model the set ${{\mathcal P}}$ of prime numbers by a random set.
2. The Möbius pseudorandomness principle, which predicts that the Möbius function ${\mu}$ does not correlate with any genuinely different arithmetic sequence of reasonable “complexity”.
3. The equidistribution of residues principle, which predicts that the residue classes of a large number ${n}$ modulo a small or medium-sized prime ${p}$ behave as if they are independently and uniformly distributed as ${p}$ varies.
4. The GUE hypothesis, which asserts that the zeroes of the Riemann zeta function are distributed (at microscopic and mesoscopic scales) like the zeroes of a GUE random matrix, and which generalises the pair correlation conjecture regarding pairs of such zeroes.

This is not an exhaustive list of models for the primes and related objects; for instance, there is also the model in which the major arc contribution in the Hardy-Littlewood circle method is predicted to always dominate, and with regards to various finite groups of number-theoretic importance, such as the class groups discussed in Supplement 1, there are also heuristics of Cohen-Lenstra type. Historically, the first heuristic discussion of the primes along these lines was by Sylvester, who worked informally with a model somewhat related to the equidistribution of residues principle. However, we will not discuss any of these models here.

A word of warning: the discussion of the above four models will inevitably be largely informal, and “fuzzy” in nature. While one can certainly make precise formalisations of at least some aspects of these models, one should not be inflexibly wedded to a specific such formalisation as being “the” correct way to pin down the model rigorously. (To quote the statistician George Box: “all models are wrong, but some are useful”.) Indeed, we will see some examples below the fold in which some finer structure in the prime numbers leads to a correction term being added to a “naive” implementation of one of the above models to make it more accurate, and it is perfectly conceivable that some further such fine-tuning will be applied to one or more of these models in the future. These sorts of mathematical models are in some ways closer in nature to the scientific theories used to model the physical world, than they are to the axiomatic theories one is accustomed to in rigorous mathematics, and one should approach the discussion below accordingly. In particular, and in contrast to the other notes in this course, the material here is not directly used for proving further theorems, which is why we have marked it as “optional” material. Nevertheless, the heuristics and models here are still used indirectly for such purposes, for instance by

• giving a clearer indication of what results one expects to be true, thus guiding one to fruitful conjectures;
• providing a quick way to scan for possible errors in a mathematical claim (e.g. by finding that the main term is off from what a model predicts, or an error term is too small);
• gauging the relative strength of various assertions (e.g. classifying some results as “unsurprising”, others as “potential breakthroughs” or “powerful new estimates”, others as “unexpected new phenomena”, and yet others as “way too good to be true”); or
• setting up heuristic barriers (such as the parity barrier) that one has to resolve before resolving certain key problems (e.g. the twin prime conjecture).

See also my previous essay on the distinction between “rigorous” and “post-rigorous” mathematics, or Thurston’s essay discussing, among other things, the “definition-theorem-proof” model of mathematics and its limitations.

Remark 1 The material in this set of notes presumes some prior exposure to probability theory. See for instance this previous post for a quick review of the relevant concepts.

Van Vu and I have just uploaded to the arXiv our paper “Random matrices have simple spectrum“. Recall that an ${n \times n}$ Hermitian matrix is said to have simple eigenvalues if all of its ${n}$ eigenvalues are distinct. This is a very typical property of matrices to have: for instance, as discussed in this previous post, in the space of all ${n \times n}$ Hermitian matrices, the space of matrices without all eigenvalues simple has codimension three, and for real symmetric cases this space has codimension two. In particular, given any random matrix ensemble of Hermitian or real symmetric matrices with an absolutely continuous distribution, we conclude that random matrices drawn from this ensemble will almost surely have simple eigenvalues.

For discrete random matrix ensembles, though, the above argument breaks down, even though general universality heuristics predict that the statistics of discrete ensembles should behave similarly to those of continuous ensembles. A model case here is the adjacency matrix ${M_n}$ of an Erdös-Rényi graph – a graph on ${n}$ vertices in which any pair of vertices has an independent probability ${p}$ of being in the graph. For the purposes of this paper one should view ${p}$ as fixed, e.g. ${p=1/2}$, while ${n}$ is an asymptotic parameter going to infinity. In this context, our main result is the following (answering a question of Babai):

Theorem 1 With probability ${1-o(1)}$, ${M_n}$ has simple eigenvalues.

Our argument works for more general Wigner-type matrix ensembles, but for sake of illustration we will stick with the Erdös-Renyi case. Previous work on local universality for such matrix models (e.g. the work of Erdos, Knowles, Yau, and Yin) was able to show that any individual eigenvalue gap ${\lambda_{i+1}(M)-\lambda_i(M)}$ did not vanish with probability ${1-o(1)}$ (in fact ${1-O(n^{-c})}$ for some absolute constant ${c>0}$), but because there are ${n}$ different gaps that one has to simultaneously ensure to be non-zero, this did not give Theorem 1 as one is forced to apply the union bound.

Our argument in fact gives simplicity of the spectrum with probability ${1-O(n^{-A})}$ for any fixed ${A}$; in a subsequent paper we also show that it gives a quantitative lower bound on the eigenvalue gaps (analogous to how many results on the singularity probability of random matrices can be upgraded to a bound on the least singular value).

The basic idea of argument can be sketched as follows. Suppose that ${M_n}$ has a repeated eigenvalue ${\lambda}$. We split

$\displaystyle M_n = \begin{pmatrix} M_{n-1} & X \\ X^T & 0 \end{pmatrix}$

for a random ${n-1 \times n-1}$ minor ${M_{n-1}}$ and a random sign vector ${X}$; crucially, ${X}$ and ${M_{n-1}}$ are independent. If ${M_n}$ has a repeated eigenvalue ${\lambda}$, then by the Cauchy interlacing law, ${M_{n-1}}$ also has an eigenvalue ${\lambda}$. We now write down the eigenvector equation for ${M_n}$ at ${\lambda}$:

$\displaystyle \begin{pmatrix} M_{n-1} & X \\ X^T & 0 \end{pmatrix} \begin{pmatrix} v \\ a \end{pmatrix} = \lambda \begin{pmatrix} v \\ a \end{pmatrix}.$

Extracting the top ${n-1}$ coefficients, we obtain

$\displaystyle (M_{n-1} - \lambda) v + a X = 0.$

If we let ${w}$ be the ${\lambda}$-eigenvector of ${M_{n-1}}$, then by taking inner products with ${w}$ we conclude that

$\displaystyle a (w \cdot X) = 0;$

we typically expect ${a}$ to be non-zero, in which case we arrive at

$\displaystyle w \cdot X = 0.$

In other words, in order for ${M_n}$ to have a repeated eigenvalue, the top right column ${X}$ of ${M_n}$ has to be orthogonal to an eigenvector ${w}$ of the minor ${M_{n-1}}$. Note that ${X}$ and ${w}$ are going to be independent (once we specify which eigenvector of ${M_{n-1}}$ to take as ${w}$). On the other hand, thanks to inverse Littlewood-Offord theory (specifically, we use an inverse Littlewood-Offord theorem of Nguyen and Vu), we know that the vector ${X}$ is unlikely to be orthogonal to any given vector ${w}$ independent of ${X}$, unless the coefficients of ${w}$ are extremely special (specifically, that most of them lie in a generalised arithmetic progression). The main remaining difficulty is then to show that eigenvectors of a random matrix are typically not of this special form, and this relies on a conditioning argument originally used by Komlós to bound the singularity probability of a random sign matrix. (Basically, if an eigenvector has this special form, then one can use a fraction of the rows and columns of the random matrix to determine the eigenvector completely, while still preserving enough randomness in the remaining portion of the matrix so that this vector will in fact not be an eigenvector with high probability.)