Informal aspects of free probability

July 16th, 2014 No comments
Dan-Virgil Voiculescu

Dan-Virgil Voiculescu (photo by G. Bergman)

This post gives some few bits of free probability theory. The content is mostly taken from the expository text arXiv:1405.1003. Free probability theory was forged in the 1980′s by Dan-Virgil Voiculescu, while working on isomorphism problems in von Neumann operator algebras of free groups. Voiculescu discovered later in the 1990′s that free probability is the algebraic structure that emerges from the asymptotic global spectral analysis of random matrix models as the dimension tends to infinity. Free probability theory comes among other things with algebraic analogues of the central limit theorem and the Boltzmann entropy. The term “free” in “free probability theory” and in “free entropy” comes from the free group (see below), and has no relation with the term “free” in the Helmholtz free energy which comes from thermodynamics (available work obtainable at constant temperature).

Algebraic probability space. Let \( {\mathcal{A}} \) be an algebra over \( {\mathbb{C}} \), with unity \( {id} \), equipped with an involution \( {a\mapsto a^*} \) and a normalized linear form \( {\tau:\mathcal{A}\rightarrow\mathbb{C}} \) such that \( {\tau(ab)=\tau(ba)} \), \( {\tau(id)=1} \), and \( {\tau(aa^*)\geq0} \). A basic non commutative example is given by the algebra of square complex matrices: \( {\mathcal{A}=\mathcal{M}_n(\mathbb{C})} \), \( {id=I_n} \), \( {a^*=\bar{a}^\top} \), \( {\tau(a)=\frac{1}{n}\mathrm{Tr}(a)} \), for which \( {\tau} \) appears as an expectation with respect to the empirical spectral distribution: denoting \( {\lambda_1(a),\ldots,\lambda_n(a)\in\mathbb{C}} \) the eigenvalues of \( {a} \), we have

\[ \tau(a)=\frac{1}{n}\sum_{k=1}^n\lambda_k(a)=\int\!x\,d\mu_a(x) \quad\text{where}\quad \mu_a:=\frac{1}{n}\sum_{k=1}^n\delta_{\lambda_k(a)}. \]

If \( {a=a^*} \) (we say that \( {a} \) is real or Hermitian) then \( {\mu_a} \) is supported in \( {\mathbb{R}} \) and is fully characterized by the collection of moments \( {\tau(a^m)} \), \( {m\geq0} \), which can be seen as a sort of algebraic distribution of \( {a} \). Beyond this example, by analogy with classical probability theory, we may see the elements of \( {\mathcal{A}} \) as algebraic analogues of bounded random variables, and \( {\tau} \) as an algebraic analogue of an expectation, and \( {\tau(a^m)} \) as the analogue of the \( {m} \)-th moment of \( {a} \). We say that \( {a\in\mathcal{A}} \) has mean \( {\tau(a)} \) and variance \( {\tau((a-\tau(a))^2)=\tau(a^2)-\tau(a)^2} \), and that \( {a} \) is centered when \( {\tau(a)=0} \). The \( {*} \)-law of \( {a} \) is the collection of mixed moments of \( {a} \) and \( {a^*} \) called the \( {*} \)-moments:

\[ \tau(b_1\cdots b_m)\text{ where } b_1,\ldots,b_m\in\{a,a^*\}\text{ and } m\geq1. \]

In contrast with classical probability, the product of algebraic variables may be non commutative. When \( {a\in\mathcal{A}} \) is real \( {a^*=a} \), then the \( {*} \)-law of \( {a} \) boils down to the moments: \( {\tau(a^m)} \), \( {m\geq0} \). In classical probability theory, the law of a real bounded random variable \( {X} \) is characterized by its moments \( {\mathbb{E}(X^m)} \), \( {m\geq0} \), thanks to the (Stone-)Weierstrass theorem. When the bounded variable is not real and takes its values in \( {\mathbb{C}} \) then we need the mixed moments \( {\mathbb{E}(X^m\bar{X}^n)} \), \( {m,n\geq0} \).

The so-called Gelfand-Naimark-Segal (GNS) construction shows that any algebraic probability space can be realized as a subset of the algebra of bounded operators on a Hilbert space. Using then the spectral theorem, this shows that any compactly supported probability measure is the \( {*} \)-law of some algebraic random variable.

Hermitization and Brown spectral measure. One can connect \( {*} \)-law and spectrum even for non real elements. Namely, if \( {a\in\mathcal{M}_n(\mathbb{C})} \) and if \( {\mu_a:=\frac{1}{n}\sum_{k=1}^n\delta_{\lambda_k(a)}} \) is its empirical spectral distribution in \( {\mathbb{C}} \), then, for any \( {z\not\in\{\lambda_1(a),\ldots,\lambda_n(a)\}} \),

\[ \begin{array}{rcl} \frac{1}{2}\tau(\log((a-zid)(a-zid)^*)) &=&\frac{1}{n}\log\left|\det(a-zI_n)\right| \\ &=&\int\!\log\left|z-\lambda\right|\,d\mu_a(\lambda) \\ &=&(\log\left|z-\cdot\right|*\mu_a)(z) \\ &=&:-U_{\mu_a}(z). \end{array} \]

The quantity \( {U_{\mu_a}(z)} \) is the logarithmic potential at point \( {z\in\mathbb{C}} \) of the probability measure \( {\mu_a} \). Since \( {-\frac{1}{2\pi}\log\left|\cdot\right|} \) is the so-called fundamental solution of the Laplace equation in dimension \( {2} \), it follows that in the sense of Schwartz distributions,

\[ \mu_a=\frac{1}{2\pi}\Delta U_{\mu_a}. \]

Following Brown, beyond the matrix case \( {\mathcal{A}=\mathcal{M}_n(\mathbb{C})} \), this suggest to define the spectral measure of an algebraic variable \( {a\in\mathcal{A}} \) in an abstract algebra \( {\mathcal{A}} \) as being the probability measure \( {\mu_a} \) on \( {\mathbb{C}} \) given by

\[ \mu_a:=-\frac{1}{\pi}\Delta\tau(\log((a-zid)(a-zid)^*)) \]

where here again \( {\Delta=4\partial\bar{\partial}} \) is the two-dimensional Laplacian acting on \( {z} \), as soon as we know how to define the operator \( {\log((a-zid)(a-zid)^*)} \) for every \( {z} \) such that \( {a-zid} \) is invertible. This makes sense for instance if \( {\mathcal{A}} \) is a von Neumann algebra of bounded operators on a Hilbert space, since one may define \( {\log(b)} \) if \( {b^*=b} \) by using functional calculus. The moral of the story is that the \( {*} \)-law of \( {a} \) determines the \( {*} \)-law of the Hermitian element \( {(a-zid)(a-zid)^*} \) for every \( {z\in\mathbb{C}} \), which in turn determines the Brown spectral measure \( {\mu_a} \). This strategy is known as Hermitization.

Freeness. The notion of freeness is an algebraic analogue of independence. In classical probability theory, a collection of \( {\sigma} \)-field are independent if the product of bounded random variables is centered as soon as the factors are centered and measurable with respect to different \( {\sigma} \)-fields. We say that \( {\mathcal{B}\subset\mathcal{A}} \) is a sub-algebra of \( {\mathcal{A}} \) when it is stable by the algebra operations, by the involution, and contains the unity \( {id} \). By analogy with classical probability, we say that the collection \( {{(\mathcal{A}_i)}_{i\in I}} \) of sub-algebras of \( {\mathcal{A}} \) are free when for any integer \( {m\geq1} \), \( {i_1,\ldots,i_m\in I} \), and \( {a_1\in\mathcal{A}_{i_1},\ldots,a_m\in\mathcal{A}_{i_m}} \), we have

\[ \tau(a_1\cdots a_m)=0 \]

as soon as \( {\tau(a_1)=\cdots=\tau(a_m)=0} \) and \( {i_1\neq \cdots\neq i_m} \) (only consecutive indices are required to be different). We say that \( {{(a_i)}_{i\in I}\subset\mathcal{A}} \) are free when the sub-algebras that they generate are free. If for instance \( {a,b\in\mathcal{A}} \) are free and centered, then \( {\tau(ab)=0} \), and \( {\tau(abab)=0} \). Note that in classical probability, the analogue of this last expression will never be zero if \( {a} \) and \( {b} \) are not zero, due to the commutation relation \( {abab=a^2b^2} \).

Can we find examples of free matrices in \( {\mathcal{M}_n(\mathbb{C})} \)? Actually, this will not give exciting answers. Freeness is more suited for infinite dimensional operators. It turns out that the definition and the name of freeness come from a fundamental infinite dimensional example constructed from the free group. More precisely, let \( {F_n} \) be the free group with \( {2n} \) generators (letters and anti-letters) \( {g_1^{\pm1},\ldots,g_n^{\pm1}} \) with \( {n\geq2} \) (for \( {n=1} \), \( {F_n=\mathbb{Z}} \) is commutative). The term “free” comes from the fact that \( {F_n} \) is the free product of \( {n} \) copies of \( {\mathbb{Z}} \), without any additional relation. Let \( {\varnothing} \) be the neutral element of \( {F_n} \) (empty string). Let \( {A_n} \) be the associated free algebra identified with \( {\ell_\mathbb{C}^2(F_n)} \). Each element of \( {A_n} \) can be seen as a complex measure of the form \( {\sum_{w\in F_n}c_w\delta_w} \), and \( {{(\delta_w)}_{w\in F_n}} \) is the canonical basis: \( {\langle\delta_w,\delta_{w’}\rangle=\mathbf{1}_{w=w’}} \). The product on \( {A_n} \) is the convolution of measures on \( {F_n} \):

\[ \left(\sum_{w\in F_n}c_w\delta_w\right)\left(\sum_{w\in F_n}c'_w\delta_w\right) =\sum_{w\in F_n}\left(\sum_{v\in F_n}c_vc'_{v^{-1}w}\right)\delta_w =\sum_{w\in F_n}(c*c')_w\delta_w. \]

Now, let \( {\mathcal{A}} \) be the algebra over \( {\mathbb{C}} \) of linear operators from \( {\ell_\mathbb{C}^2(F_n)} \) to itself. The product in \( {\mathcal{A}} \) is the composition of operators. The involution \( {*} \) in \( {\mathcal{A}} \) is the transposition-conjugacy of operators. The identity operator is denoted \( {id} \). We consider the linear form \( {\tau:\mathcal{A}\rightarrow\mathbb{C}} \) defined for every \( {a\in\mathcal{A}} \) by

\[ \tau(a)=\langle a\delta_\varnothing,\delta_\varnothing\rangle. \]

For every \( {w\in F_n} \), let \( {u_w\in\mathcal{A}} \) be the left translation operator defined by \( {u_w(\delta_v)=\delta_{wv}} \). Then

\[ u_w u_{w'}=u_{ww'},\quad (u_w)^*=u_{w^{-1}},\quad u_\varnothing=id, \]

and therefore \( {u_w u_w^*=u_w^* u_w=id} \) (we say that \( {u_w} \) is unitary). We have \( {\tau(u_w)=\mathbf{1}_{w=\varnothing}} \). Let us show that the sub-algebras \( {\mathcal{A}_1,\ldots,\mathcal{A}_n} \) generated by \( {u_{g_1},\ldots,u_{g_n}} \) are free. Each \( {\mathcal{A}_i} \) consists in linear combinations of \( {u_{g_i^r}} \) with \( {r\in\mathbb{Z}} \), and centering forces \( {r=0} \). For every \( {w_1,\ldots,w_m\in F_n} \), we have

\[ \tau(u_{w_1}\cdots u_{w_m}) =\tau(u_{w_1\cdots w_m}) =\mathbf{1}_{w_1\cdots w_m=\varnothing}. \]

Let us consider the case \( {w_j=g_{i_j}^{r_j}\in\mathcal{A}_{i_j}} \) with \( {r_j\in\mathbb{Z}} \), for every \( {1\leq j\leq m} \). Either \( {r_j=0} \) and \( {w_j=\varnothing} \) or \( {r_j\neq0} \) and \( {\tau(w_j)=0} \). Let us assume that \( {r_1\neq0,\ldots,r_n\neq0} \), which implies \( {\tau(u_{w_1})=\cdots=\tau(u_{w_n})=0} \). Now since \( {G_n} \) is a tree, it does not have cycles, and thus if we follow a path starting from the root \( {\varnothing} \) then we cannot go back to the root if we never go back locally along the path (this is due to the absence of cycles). Consequently, if additionally \( {i_1\neq\cdots\neq i_m} \) (i.e. two consecutive terms are different), then we have necessarily \( {w_1\cdots w_m\neq\varnothing} \), and therefore \( {\tau(u_{w_1}\cdots u_{w_m})=0} \). From this observation one can conclude that \( {\mathcal{A}_1,\ldots,\mathcal{A}_n} \) are free.

Beyond the example of the free group: if \( {G_1,\ldots,G_n} \) are groups and \( {G} \) their free product, then the algebras generated by \( {\{u_g:g\in G_1\},\ldots,\{u_g:g\in G_n\}} \) are always free in the one generated by \( {\{u_g:g\in G\}} \).

Conceptual dictionary between classical probability and free probability. The first is commutative while the second is typically non commutative. Free probability is the algebraic structure that emerges from the asymptotic analysis, over the dimension, of the empirical spectral distribution of unitary invariant random matrices. The term free comes from the algebra of linear operators over the free algebra of the free group, an example in which the concept of freeness emerges naturally, in relation with the symmetric random walk on the infinite regular tree of even degree \( {\geq 4} \) (which is the Cayley graph of a non-commutative free group).

Classical probability Free probability
Bounded r.v. \( {X} \) on \( {\mathbb{C}} \) Algebra element \( {a\in\mathcal{A}} \)
\( {\mathbb{E}(X^m\bar{X}^{n})} \) \( {\tau(b_1\cdots b_m)} \), \( {b\in\{a,a^*\}^m} \)
Law = Moments Law = \( {*} \)-moments
\( {X} \) is real \( {a=a^*} \)
Independence Freeness
Classical convolution \( {*} \) Free convolution \( {\boxplus} \)
Gaussian law (with CLT) Semicircle law (with CLT)
Boltzmann entropy \( {\mathcal{S}} \) Voiculescu entropy \( {\chi} \)

Law of free couples and free convolution. In classical probability theory, the law of a couple of independent random variables is fully characterized by the couple of laws of the variables. In free probability theory, the \( {*} \)-law of the couple \( {(a,b)} \) is the collection of mixed moments in \( {a,a^*,b,b^*} \). If \( {a,b} \) are free, then one can compute the \( {*} \)-law of the couple \( {(a,b)} \) by using the \( {*} \)-law of \( {a} \) and \( {b} \), thanks to the centering trick. For instance, in order to compute \( {\tau(ab)} \), we may write using freeness \( {0=\tau((a-\tau(a))(b-\tau(b)))=\tau(ab)-\tau(a)\tau(b)} \) to get \( {\tau(ab)=\tau(a)\tau(b)} \). As a consequence, one can show that the \( {*} \)-law of a couple of free algebraic variables is fully characterized by the couple of \( {*} \)-laws of the variables. This works for arbitrary vectors of algebraic variables.

In classical probability theory, the law of the sum of two independent random variables is given by the convolution of the law of the variables. In free probability theory, the \( {*} \)-law of the sum \( {a+b} \) of two free algebraic variables \( {a,b\in\mathcal{A}} \) is given by the so-called free convolution \( {\mathrm{dist}(a)\boxplus\mathrm{dist}(b)} \) of the \( {*} \)-law of \( {a} \) and \( {b} \), which can be defined using the \( {*} \)-law of the couple \( {(a,b)} \). Given an at most countable family of compactly supported probability measures on \( {\mathbb{R}} \), it can be show that one can always construct an algebraic probability space containing free algebraic variables admitting these probability measures as their \( {*} \)-distributions. The free convolution \( {\boxplus} \) of probability measures is associative. We have so far at hand an algebraic framework, called free probability theory, in which the concepts of algebra elements, trace, \( {*} \)-law, freeness, and free convolution are the analogue of the concepts of bounded random variables, expectation, law, independence, and convolution of classical probability theory. Do we have a CLT, and an analogue of the Gaussian? The answer is positive.

Free CLT and semicircle law. It is natural to define the convergence in \( {*} \)-law, denoted \( {\overset{*}{\rightarrow}} \), as being the convergence of all \( {*} \)-moments. The Voiculescu free CLT states that if \( {a_1,a_2,\ldots\in\mathcal{A}} \) are free, real \( {a_i=a_i^*} \), with same \( {*} \)-law, zero mean \( {\tau(a_i)=0} \), unit variance \( {\tau(a_i^2)=1} \), then

\[ s_n:=\frac{a_1+\cdots+a_n}{\sqrt{n}} \overset{*}{\underset{n\rightarrow\infty}{\longrightarrow}} \frac{\sqrt{4-x^2}\mathbf{1}_{[-2,2]}}{2\pi}dx. \]

The limiting \( {*} \)-law is given by the moments of the semicircle law on \( {[-2,2]} \), which are \( {0} \) for odd moments and the Catalan numbers \( {{(C_m)}_{m\geq0}} \) for even moments: for every \( {m\geq0} \),

\[ \int_{-2}^2\!x^{2m+1}\frac{\sqrt{4-x^2}}{2\pi}dx=0 \quad\text{and}\quad \int_{-2}^2\!x^{2m}\frac{\sqrt{4-x^2}}{2\pi}dx =C_m:=\frac{1}{1+m}\binom{2m}{m}. \]

The semicircle law is also known as the Wigner distribution in random matrix theory and the Sato-Tate distribution in number theory. An algebraic variable \( {b\in\mathcal{A}} \) has semicircle \( {*} \)-law when it is real \( {b=b^*} \) and \( {\tau(b^{2m+1})=0} \) and \( {\tau(b^{2m})=C_m} \) for every \( {m\geq0} \). The proof of the free CLT consists in computing the moments of \( {s_n} \) using freeness. This reveals three type of terms: terms which are zero at fixed \( {n} \) thanks to freeness and centering, terms having zero contribution asymptotically as \( {n\rightarrow\infty} \), and terms which survive at the limit, and which involve only the second moment of the \( {a_i} \)’s. Beyond freeness, there exists other notions of algebraic independence, allowing to compute moments, and leading to a CLT with other limiting distributions, including the Bernoulli distribution and the arcsine distribution.

As for the classical CLT, the first two moments are conserved along the free CLT: \( {\tau(s_n)=0} \) and \( {\tau(s_n^2)=1} \) for all \( {n\geq1} \). The semicircle \( {*} \)-law is the free analogue of the Gaussian distribution of classical probability. The semicircle \( {*} \)-law is stable by free convolution: if \( {a_1,\ldots,a_n} \) are free with semicircle \( {*} \)-law then the \( {*} \)-law of \( {a_1+\cdots+a_n} \) is also semicircle and its second moment is the sum of the second moments. In particular \( {s_n=(a_1+\cdots+a_n)/\sqrt{n}} \) is semicircle, just like the Gaussian case in the CLT of classical probability! If \( {\mu_1,\ldots,\mu_n} \) are semicircle laws then their free convolution \( {\mu_1\boxplus\cdots\boxplus\mu_n} \) is also a semicircle law and its variance is the sum of the variances.

Random walks and CLT. Let us reconsider the free group \( {F_n} \). The algebraic variables

\[ a_1=\frac{u_{g_1}+u_{g_1^{-1}}}{\sqrt{2}},\ldots, a_n=\frac{u_{g_n}+u_{g_n^{-1}}}{\sqrt{2}} \]

are free, real, centered, with unit variance. Let us define

\[ a=\sum_{i=1}^n(u_{g_i}+u_{g_i}^{-1})=\sqrt{2}\sum_{i=1}^n a_i \quad\text{and}\quad p =\frac{a}{2n} =\frac{a_1+\cdots+a_n}{\sqrt{2}n}. \]

Then \( {a} \) is the adjacency operator of the Cayley graph \( {G_n} \) of the free group \( {F_n} \), which is \( {2n} \)-regular, without cycles (a tree!), rooted at \( {\varnothing} \). Moreover, \( {\langle p\delta_v,\delta_w\rangle=\frac{1}{2n}\mathbf{1}_{wv^{-1}\in S}} \) where \( {S=\{g_1^{\pm1},\ldots,g_n^{\pm}\}} \), and thus \( {p} \) is the transition kernel of the simple random walk on \( {G_n} \). For every integer \( {m\geq0} \), the quantity \( {\tau(a^m)=\langle a^m\delta_\varnothing,\delta_\varnothing\rangle} \) is the number of paths of length \( {m} \) in \( {G_n} \) starting and ending at the root \( {\varnothing} \). From the Kesten-McKay theorem, for every integer \( {m\geq0} \),

\[ \tau(a^m) =\langle a^m\delta_\varnothing,\delta_\varnothing\rangle =\int\!x^m\,d\mu_{d}(x), \]

where \( {\mu_{d}} \) is the Kesten-McKay distribution with parameter \( {d=2n} \), given by

\[ d\mu_{d}(x) :=\frac{d\sqrt{4(d-1)-x^2}}{2\pi(d^2-x^2)} \mathbf{1}_{[-2\sqrt{d-1},2\sqrt{d-1}]}(x)dx. \]

By parity we have \( {\tau(a^{2m+1})=0} \) for every \( {m\geq0} \). When \( {n=1} \) then \( {d=2} \) and \( {G_2} \) is the Cayley graph of \( {F_1=\mathbb{Z}} \), the corresponding Kesten-McKay law \( {\mu_{2}} \) is the arcsine law on \( {[-2,2]} \),

\[ \langle a^{2m}\delta_\varnothing,\delta_\varnothing\rangle =\int\!x^{2m}\,d\mu_{2}(x) =\int_{-2}^2\frac{x^{2m}}{\pi\sqrt{4-x^2}}dx =\binom{2m}{m}, \]

and we recover the fact that the number of paths of length \( {2m} \) in \( {\mathbb{Z}} \) starting and ending at the root \( {\varnothing} \) (which is the origin \( {0} \)) is given by the central binomial coefficient. The binomial combinatorics is due to the commutativity of \( {F_1=\mathbb{Z}} \). At the opposite side of degree, when \( {d=2n\rightarrow\infty} \) then \( {\mu_{d}} \), scaled by \( {(d-1)^{-1/2}} \), tends to the semicircle law on \( {[-2,2]} \):

\[ \lim_{d\rightarrow\infty} \frac{\langle a^{2m}\delta_\varnothing,\delta_\varnothing\rangle}{(d-1)^m} =\lim_{d\rightarrow\infty} \int\!\left(\frac{x}{\sqrt{d-1}}\right)^{2m}\!\!\!\!d\mu_{d}(x) =\int_{-2}^2 y^{2m}\frac{\sqrt{4-y^2}}{2\pi}dy =C_m:=\frac{1}{1+m}\binom{2m}{m}. \]

As a consequence, we have, thanks to \( {(d-1)^m\sim_{n\rightarrow\infty}d^m=(2n)^m=(\sqrt{2n})^{2m}} \),

\[ \tau\left(\left(\frac{a_1+\cdots+a_n}{\sqrt{n}}\right)^{2m}\right) =\frac{\tau(a^{2m})}{(2n)^m} = \frac{\langle a^{2m}\delta_\varnothing,\delta_\varnothing\rangle}{d^m} \underset{n\rightarrow\infty}{\longrightarrow} C_m. \]

This is nothing else but a free CLT for the triangular array \( {{((a_1,\ldots,a_n))}_{n\geq1}} \)! The free CLT is the algebraic structure that emerges from the asymptotic analysis, as \( {n\rightarrow\infty} \), of the combinatorics of loop paths of the simple random walk on the Cayley graph \( {G_n} \) of the free group \( {F_n} \), and more generally on the \( {d} \)-regular infinite graph without cycles (a tree!) as the degree \( {d} \) tends to infinity.

We have \( {a=b_1+\cdots+b_n} \) where \( {b_i=\sqrt{2}a_i=u_{g_i}+u_{g_i^{-1}}} \). But for any \( {m\in\mathbb{N}} \) we have \( {\tau(b_i)^{2m+1}=0} \) and \( {\tau(b_i^{2m})=\sum_{r=1}^{2m}\binom{2m}{r}\tau(u_{g_i^{2(r-m)}})=\binom{2m}{m}} \), and therefore the \( {*} \)-law of \( {b_i} \) is the arcsine law \( {\mu_2} \), and thanks to the freeness of \( {b_1,\ldots,b_n} \) we obtain

\[ \mu_d=\underbrace{\mu_{2}\boxplus\cdots\boxplus\mu_{2}}_{d\text{ times}}. \]

The Kesten-McKay distribution appears for regular trees of even degree (Cayley graph of free groups) in the doctoral thesis of Harry Kesten published in 1959. It seems that no connections were made at that time with the contemporary works of Eugene Wigner on random matrices published in the 1950′s. In 1981, Brendan McKay showed that these distributions appear as the limiting empirical spectral distributions of the adjacency matrices of sequences of (random) graphs which are asymptotically regular and without cycles (trees!). He does not cite Kesten and Wigner.

Free entropy. Inspired by the Boltzmann H-Theorem view of Shannon on the CLT of classical probability theory, one may ask if there exists, in free probability theory, a free entropy functional, maximized by the semicircle law at fixed second moment, and which is monotonic along the free CLT. We will see that the answer is positive. Let us consider a real algebraic variable \( {a\in\mathcal{A}} \), \( {a^*=a} \), such that there exists a probability measure \( {\mu_a} \) on \( {\mathbb{R}} \) such that for every integer \( {m\geq0} \),

\[ \tau(a^m)=\int\!x^m\,d\mu_a(x). \]

Inspired from the micro-macro construction of the Boltzmann entropy, one may consider an approximation at the level of the moments of the algebraic variable \( {a} \) (which is in general infinite dimensional) by Hermitian matrices (which are finite dimensional). Namely, following Voiculescu, for every real numbers \( {\varepsilon>0} \) and \( {R>0} \) and integers \( {m\geq0} \) and \( {d\geq1} \), let \( {\Gamma_R(a;m;d,\varepsilon)} \) be the relatively compact set of Hermitian matrices \( {h\in\mathcal{M}_d(\mathbb{C})} \) such that \( {\left\Vert h\right\Vert\leq R} \) and \( {\max_{0\leq k\leq m}\left|\tau(a^k)-\frac{1}{d}\mathrm{Tr}(h^k)\right|\leq\varepsilon} \). The volume \( {\left|\Gamma_R(a;m,d,\varepsilon)\right|} \) measures the degree of freedom of the approximation of the algebraic variable \( {a} \) by matrices, and is the analogue of the cardinal (which was multinomial) in the combinatorial construction of the Boltzmann entropy. We find

\[ \chi(a) :=\sup_{R>0}\inf_{m\in\mathbb{N}}\inf_{\varepsilon>0} \varlimsup_{d\rightarrow\infty} \left(\frac{1}{d^2}\log\left|\Gamma_R(a;m,d,\varepsilon)\right|+\frac{\log(d)}{2}\right) =\iint\!\log\left|x-y\right|\,d\mu_a(x)d\mu_a(y). \]

This quantity depends only on \( {\mu_a} \) and is also denoted \( {\chi(\mu_a)} \). It is a quadratic form in \( {\mu_a} \). It is the Voiculescu entropy functional (a survey is available). When \( {\mu} \) is a probability measure on \( {\mathbb{C}} \), we will still denote

\[ \chi(\mu):=\iint\!\log\left|x-y\right|\,d\mu(x)d\mu(y). \]

However, this is not necessarily the entropy of an algebraic variable when \( {\mu} \) is not supported in \( {\mathbb{R}} \). The Voiculescu free entropy should not be confused with the von Neumann entropy in quantum probability defined by \( {S(a)=-\tau(a\log(a))} \), which was considered by Elliot Lieb. For some models of random graphs, one can imitate Voiculescu and forge some sort of graphical Boltzmann entropy, which can be related to a large deviations rate functional, see the work of Bordenave and Caputo and references therein.

The semicircle law is for the free entropy the analogue of the Gaussian law for the Boltzmann entropy. The semicircle law on \( {[-2,2]} \) is the unique law that maximizes the Voiculescu entropy \( {\chi} \) among the laws on \( {\mathbb{R}} \) with second moment equal to \( {1} \):

\[ \arg\max\left\{\chi(\mu):\mathrm{supp}(\mu)\subset\mathbb{R},\int\!x^2\,d\mu(x)=1\right\} =\frac{\sqrt{4-x^2}\mathbf{1}_{[-2,2]}(x)}{2\pi}dx. \]

How about laws on \( {\mathbb{C}} \) instead of \( {\mathbb{R}} \)? The uniform law on the unit disc is the unique law that maximizes the functional \( {\chi} \) among the set of laws on \( {\mathbb{C}} \) with second moment (mean squared modulus) equal to \( {1} \) (here \( {z=x+iy} \) and \( {dz=dxdy} \)):

\[ \arg\max\left\{\chi(\mu):\mathrm{supp}(\mu)\subset\mathbb{C},\int\!|z|^2\,d\mu(z)=1\right\} =\frac{\mathbf{1}_{\{z\in\mathbb{C}:|z|=1\}}}{\pi}dz, \]

Under the uniform law on the unit disc, the real and the imaginary parts follow the semicircle law on \( {[-1,1]} \), and are not independent. If we say that an algebraic variable \( {c\in\mathcal{A}} \) is circular when its \( {*} \)-law is the uniform law on the unit disc of \( {\mathbb{C}} \), then, if \( {s_1,s_2\in\mathcal{A}} \) are free with \( {*} \)-law equal to the semicircle law on \( {[-2,2]} \), then \( {\frac{s_1+is_2}{\sqrt{2}}} \) is circular (here \( {i=(0,1)\in\mathbb{C}} \) is such that \( {i^2=-1} \)).

It turns out that the Voiculescu free entropy \( {\chi} \) is monotonic along the Voiculescu free CLT:

\[ \chi(a)=\chi(s_1)\leq\cdots\leq\chi(s_n)\leq\chi(s_{n+1})\leq\cdots \underset{n\rightarrow\infty}{\nearrow} \max\chi(s) \]

where still \( {s_n=n^{-1/2}(a_1+\cdots+a_n)} \) and where \( {s} \) is an semicircle algebraic variable. Dimitri Shlyakhtenko considered this problem in two papers. He gave a proof of this remarkable fact, based on a free Fisher information functional (which is a Hilbert transform), that captures simultaneously the classical and the free CLT. The Boltzmann-Shannon H-Theorem interpretation of the CLT is thus remarkably valid in classical probability theory, and in free probability theory.

A famous theorem of Eugene Wigner. Let \( {H} \) be a random \( {n\times n} \) Hermitian matrix belonging to the Gaussian Unitary Ensemble (GUE). This means that \( {H} \) has density proportional to

\[ e^{-\frac{n}{4}\mathrm{Tr}(H^2)} =e^{-\frac{n}{4}\sum_{1\leq j\leq 1}^n H_{jj}^2-\frac{n}{2}\sum_{1\leq j<k\leq n}|H_{jk}|^2}. \]

The entries of \( {H} \) are Gaussian, centered, independent, with variance \( {2/n} \) on the diagonal and \( {1/n} \) outside. Let \( {\mu_n=\frac{1}{n}\sum_{j=1}^n\delta_{\lambda_{j}(H)}} \) be the empirical spectral distribution of \( {H} \), which is a random discrete probability measure on \( {\mathbb{R}} \). For every \( {m\geq0} \), the mean \( {m} \)-th moment of \( {\mu_n} \) is given by

\[ \mathbb{E}\int\!x^m\,d\mu_n(x) =\frac{1}{n}\sum_{j=1}^n\lambda_{j}^m =\frac{\mathbb{E}\mathrm{Tr}(H^m)}{n} =\sum_{i_1,\ldots,i_m}\frac{\mathbb{E}(H_{i_1i_2}\cdots H_{i_{m-1}i_m}H_{i_mi_1})}{n}. \]

In particular, the first two moments of \( {\mathbb{E}\mu_n} \) satisfy to

\[ \mathbb{E}\int\!x\,d\mu_n(x)=\frac{\mathbb{E}(\mathrm{Tr}(H))}{n} =\frac{\mathbb{E}\sum_{j=1}^n H_{jj}}{n}=0 \]


\[ \mathbb{E}\int\!x^2\,d\mu_n(x)=\frac{\mathbb{E}(\mathrm{Tr}(H^2))}{n} =\mathbb{E}\frac{\sum_{j,k=1}^n |H_{jk}|^2}{n} =\frac{n(2/n)+(n^2-n)(1/n)}{n} \underset{n\rightarrow\infty}{\longrightarrow}1. \]

More generally, for any \( {m>2} \), the computation of the limiting \( {m} \)-th moment of \( {\mathbb{E}\mu_n} \) boils down to the combinatorics of the paths \( {i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_m} \). It can be shown that the surviving terms as \( {n\rightarrow\infty} \) correspond to paths forming a tree and passing exactly zero or two times per each edge. This gives finally, for every integer \( {m\geq0} \), denoting \( {C_m} \) the \( {m} \)-th Catalan number,

\[ \lim_{n\rightarrow\infty}\mathbb{E}\int\!x^{2m+1}\,d\mu_n(x)=0 \quad\text{and}\quad \lim_{n\rightarrow\infty}\mathbb{E}\int\!x^{2m}\,d\mu_n(x)=C_m. \]

This means that \( {\mathbb{E}\mu_n} \) tends as \( {n\rightarrow\infty} \) in the sense of moments to the semicircle law on \( {[-2,2]} \) (which has unit variance). Just like the CLT, the result is actually universal, in the sense that it remains true if one drops the Gaussian distribution assumption of the entries. This is the famous Wigner theorem, in its modern general form, named after Eugene Paul Wigner (1902 — 1995) who proved a version of it in the 1950′s. The GUE case is in fact exactly solvable: one can compute the density of the eigenvalues, which turns out to be proportional to

\[ \prod_{j=1}^ne^{-\frac{n}{4}\lambda_{j}^2}\prod_{j<k}(\lambda_j-\lambda_k)^2 =\exp \left(-\frac{n}{4}\sum_{j=1}^n\lambda_j^2 -\sum_{j\neq k}\log\frac{1}{\left|\lambda_j-\lambda_k\right|}\right). \]

The logarithmic repulsion is the Coulomb repulsion in dimension \( {2} \). Also, this suggest to interpret the eigenvalues \( {\lambda_1,\ldots,\lambda_n} \) as a Coulomb gas of two-dimensional charged particles forced to stay in a one dimensional ramp (the real line) and experiencing a confinement by a quadratic potential. These formulas allow to deduce the semicircle limit of the one-point correlation (density of \( {\mathbb{E}\mu_n} \)), by using various methods, such as orthogonal polynomials, or large deviations theory.

Asymptotic freeness of unitary invariant random matrices. If \( {A} \) and \( {B} \) are two Hermitian \( {n\times n} \) matrices, then the spectrum of \( {A+B} \) depend not only on the spectrum of \( {A} \) and the spectrum of \( {B} \), but also on the eigenvectors of \( {A} \) and \( {B} \). Even if \( {A} \) and \( {B} \) commute, then they admit the same eigenvectors and the spectrum of \( {A+B} \) is the sum of the spectra of \( {A} \) and \( {B} \), but this depends on the way we label the eigenvalues, which depends in turn on the eigenvectors. Now if \( {A} \) and \( {B} \) are two independent random Hermitian matrices, there is no reason to believe that the empirical spectral distribution \( {\mu_{A+B}} \) of \( {A+B} \) depend only on the empirical spectral distributions \( {\mu_A} \) and \( {\mu_B} \) of \( {A} \) and \( {B} \). Let \( {A} \) be a \( {n\times n} \) random Hermitian matrix in the GUE, normalized such that \( {\mu_A} \) has a mean second moment equal to \( {1} \). Then the Wigner theorem says that \( {\mathbb{E}\mu_A} \) tend in the sense of moments, as \( {n\rightarrow\infty} \), to the semicircle law of unit variance. If \( {B} \) is an independent copy of \( {A} \), then, thanks to the convolution of Gaussian laws, \( {A+B} \) is identical in law to \( {\sqrt{2}A} \), and thus \( {\mathbb{E}\mu_{A+B}} \) tend, in the sense of moments, as \( {n\rightarrow\infty} \), to the semicircle law of variance \( {2} \). Then, thanks to the free convolution of semicircle laws, we have

\[ \mathbb{E}\mu_{A+B}-\mathbb{E}\mu_A\boxplus\mathbb{E}\mu_B \underset{n\rightarrow\infty}{\overset{*}{\longrightarrow}}0, \]

where \( {\overset{*}{\rightarrow}} \) denotes the convergence of moments. Voiculescu has established that this asymptotic freeness phenomenon remains actually true beyond the GUE case, provided that the eigenspaces of the two matrices are randomly decoupled using a random unitary conjugation. For example, let \( {A} \) and \( {B} \) two \( {n\times n} \) Hermitian matrices such that \( {\mu_A\rightarrow\mu_a} \) and \( {\mu_B\rightarrow\mu_b} \) in the sense of moments as \( {n\rightarrow\infty} \), where \( {\mu_a} \) and \( {\mu_b} \) are two compactly supported laws on \( {\mathbb{R}} \). Let \( {U} \) and \( {V} \) be independent random unitary matrices uniformly distributed on the unitary group (we say Haar unitary). Then

\[ \mathbb{E}\mu_{UAU^*+VBV^*} \underset{n\rightarrow\infty}{\overset{*}{\longrightarrow}} \mu_a\boxplus\mu_b. \]

This asymptotic freeness reveals that free probability is the algebraic structure that emerges from asymptotic analysis of large dimensional unitary invariant models of random matrices.

Since the functional \( {\chi} \) is maximized by the uniform law on the unit disc, one may ask about an analogue of the Wigner theorem for non-Hermitian random matrices. The answer is positive. For our purposes, we will focus on a special ensemble of random matrices, introduced by Jean Ginibre in the 1960′s, for which he computed explicitly the density of the eigenvalues. Note by the way that Jean Ginibre is also famous for Fortuin-Kasteleyn-Ginibre (FKG) correlation inequality, and for scattering theory for nonlinear Schrödinger equations.

Complex Ginibre Ensemble and the circular law. One of the most fascinating result in the asymptotic analysis of large dimensional random matrices is the circular law for the complex Ginibre ensemble, which can be proved using the Voiculescu functional \( {\chi} \) (maximized at fixed second moment by uniform law on unit disc). A simple model of random matrix is the Ginibre model:

\[ G= \begin{pmatrix} G_{11}&\cdots&G_{1n}\\ \vdots & \vdots & \vdots\\ G_{n1} & \cdots & G_{nn} \end{pmatrix} \]

where \( {{(G_{jk})}_{1\leq j,k\leq n}} \) are i.i.d. random variables on \( {\mathbb{C}} \), with \( {\Re G_{jk},\Im G_{jk}} \) of Gaussian law of mean \( {0} \) and variance \( {1/(2n)} \). In particular, \( {\mathbb{E}(|G_{jk}|^2)=1/n} \). The density of \( {G} \) is proportional to

\[ \prod_{j,k=1}^ne^{-n\left|G_{jk}\right|^2} = e^{-\sum_{j,k=1}^n n\left|G_{jk}\right|^2} = e^{-n\mathrm{Tr}(GG^*)}. \]

This shows that the law of \( {G} \) is unitary invariant, meaning that \( {UGU^*} \) and \( {G} \) have the same law, for every unitary matrix \( {U} \). Can we compute the law of the eigenvalues of \( {G} \)? Let \( {G=UTU^*} \) be the Schur unitary triangularization of \( {G} \). Here \( {T=D+N} \) where \( {D} \) is diagonal and \( {N} \) is upper triangular with null diagonal. In particular \( {N} \) is nilpotent, \( {T} \) is upper triangular, and the diagonal of \( {D} \) is formed with the eigenvalues \( {\lambda_1,\ldots,\lambda_n} \) in \( {\mathbb{C}} \) of \( {G} \). The Jacobian of the change of variable \( {G\mapsto (U,D,N)} \) is proportional to \( {\prod_{1\leq j<k\leq n}\left|\lambda_j-\lambda_k\right|^2} \) (for simplicity, we neglect here delicate problems related to the non-uniqueness of the Schur unitary decomposition). On the other hand,

\[ \mathrm{Tr}(GG^*) =\mathrm{Tr}(DD^*)+\mathrm{Tr}(DN^*)+\mathrm{Tr}(ND^*)+\mathrm{Tr}(NN^*) =\mathrm{Tr}(DD^*). \]

This allows to integrate out the \( {U,N} \) variables. The law of the eigenvalues is then proportional to

\[ e^{-n\sum_{j=1}^n\left|\lambda_j\right|^2}\prod_{1\leq j<k\leq n}\left|\lambda_j-\lambda_k\right|^2. \]

This defines a determinantal process on \( {\mathbb{C}} \): the complex Ginibre ensemble. In order to interpret the law of the eigenvalues as a Boltzmann measure, we put the Vandermonde determinant inside the exponential:

\[ e^{-n\sum_j\left|\lambda_j\right|^2+2\sum_{j<k}\log\left|\lambda_j-\lambda_k\right|}. \]

If we encode the eigenvalues by the empirical measure \( {\mu_n:=\frac{1}{n}\sum_{j=1}^n\delta_{\lambda_j}} \), this takes the form

\[ e^{-n^2 \mathcal{I}(\mu_n)} \]

where the “energy” \( {\mathcal{I}(\mu_n)} \) of the configuration \( {\mu_n} \) is defined via

\[ \mathcal{I}(\mu):= \int\!\left|z\right|^2\,d\mu(z) +\iint_{\neq}\!\log\frac{1}{\left|z-z'\right|}\,d\mu(z)d\mu(z'). \]

This suggests to interpret the eigenvalues \( {\lambda_1,\ldots,\lambda_n} \) of \( {G} \) as Coulomb gas of two-dimensional charged particles, confined by a an external field (quadratic potential) and subject to pair Coulomb repulsion. Note that \( {-\mathcal{I}} \) can also be seen as a penalized Voiculescu functional. Minimizing a penalized functional is equivalent to minimizing without penalty but under constraint (Lagrange). Presently, if \( {\mathcal{M}} \) is the set of probability measures on \( {\mathbb{C}} \) then \( {\inf_{\mathcal{M}}\mathcal{I}>-\infty} \) and the infimum is achieved at a unique probability measure \( {\mu_*} \), which is the uniform law on the unit disc of \( {\mathbb{C}} \).

How does the random discrete probability measure \( {\mu_n} \) behave as \( {n\rightarrow\infty} \)? Following Hiai and Petz one may adopt a large deviations approach. Let \( {\mathcal{M}} \) be the set of probability measures on \( {\mathbb{C}} \). One may show that the functional \( {\mathcal{I}:\mathcal{M}\rightarrow\mathbb{R}\cup\{+\infty\}} \) is lower semi continuous for the topology of narrow convergence, is strictly convex, and has compact level sets. Let us consider a distance compatible with the topology. It can be shown that for every ball \( {B} \) for this distance,

\[ \mathbb{P}(\mu_n\in B) \approx \exp\left(-n^2\inf_{B}(\mathcal{I}-\inf_{\mathcal{M}}\mathcal{I})\right) \]

Now either \( {\mu_*\in B} \) and in this case \( {\mathbb{P}(\mu_n\in B)\approx 1} \), or \( {\mu_*\not\in B} \) and in this case \( {\mathbb{P}(\mu_n\in B)\rightarrow0} \) exponentially fast. Actually, the first Borel-Cantelli lemma allows to deduce that almost surely

\[ \lim_{n\rightarrow\infty}\mu_n = \mu_* = \arg\inf \mathcal{I} = \frac{\mathbf{1}_{\{z\in\mathbb{C}:\left|z\right|\leq1\}}}{\pi}dz, \]

where \( {z=x+iy} \) and \( {dz=dxdy} \). This phenomenon is known as the circular law. If one starts with a Hermitian random Gaussian matrix — the Gaussian Unitary Ensemble (GUE) — then the same analysis is available, and produces a convergence to the semicircle law on \( {[-2,2]} \).

The circular law is universal, in the sense that it remains valid if one drops the Gaussian assumption of the entries of the matrix, while keeping the i.i.d. structure and the \( {1/n} \) variance. This was the subject of a long series of works by Girko, Bai, Tao and Vu, among others, and was the subject of several posts. Another way to go beyond the Gaussian case is to start from the Coulomb gas and to replace the quadratic confining potential \( {\left|\cdot\right|^2} \) by a more general potential \( {V:\mathbb{C}\rightarrow\mathbb{R}} \), not necessarily radial. This type of generalization was studied by Saff and Totik, Hiai and Petz, Adrien Hardy, among others.

Beyond random matrices, how about the empirical measure of random particles in \( {\mathbb{R}^d} \) with Coulomb type singular repulsion and external field confinement? Is there an analogue of the circular law phenomenon? Does the ball replace the disc? The answer is positive.

Further reading.


Laurent Schwartz – Un mathématicien aux prises avec le siècle

June 7th, 2014 2 comments

Laurent Schwartz

Je viens de terminer la relecture, à presque quinze années d’intervalle, de l’autobiographie de Laurent Schwartz (1915 – 2002) intitulée « Un mathématicien aux prises avec le siècle », publiée en 1997 chez Odile Jacob. Ma première lecture datait de l’École d’été de Saint-Flour 1999 ! Ce grand livre de 528 pages est très riche sur les plans de l’histoire, de la science, et de la politique. Voilà donc un grand scientifique plutôt intellectuel, passionné, et passionnant. Mais le livre ne dit pas si ce libre penseur était facile à vivre. Table des matières  :

AVANT-PROPOS ..........................9
INTRODUCTION. Le jardin d’Éden .......11
CHAPITRE I. La révélation des mathématiques ..41
CHAPITRE II. Normalien et amoureux ...........71
CHAPITRE III. Trotskiste .....................99
CHAPITRE IV. Un chercheur dans la guerre ....137
CHAPITRE V. La guerre aux Juifs .............189
CHAPITRE VI. L'invention des distributions ........223
CHAPITRE VII. Militer, enseigner, chercher ........267
CHAPITRE VIII. Une reconnaissance internationale ..309
CHAPITRE IX. La réforme de l'École polytechnique ..333
CHAPITRE X. L'engagement algérien ...................371
CHAPITRE XI. Pour un Viêt-nam indépendant ...........421
CHAPITRE XII. La lointaine guerre afghane ...........483
CHAPITRE XIII. Le Comité des mathématiciens .........497

Entre autres combats, Laurent Schwartz défendait que l’enseignement supérieur français avait besoin d’une profonde refonte, rapprochant recherche et élitisme : mettre de la recherche dans les grandes écoles et de la sélection à l’Université. S’il n’a pas été écouté pour l’Université, on peut dire, avec le recul, que son œuvre à l’École Polytechnique (1959 – 1980) a plutôt réussi, malgré ce qu’il en dit. L’X d’aujourd’hui lui doit beaucoup. Il avait même souhaité, à l’époque, un projet comparable à ce qu’est aujourd’hui Universtité Paris-Saclay. Extraits  :

Sur la réforme de l’École Polytechnique (pages 353 , 354, 357, 358)

Mon ambition première avait été de donner à l’École polytechnique les moyens de former des ingénieurs de haut niveau capables de renforcer l’industrie française. Dans ce domaine, on peut parler d’un demi-échec. En 1980, lorsque je pris ma retraite, la formation des ingénieurs de l’industrie française connaissait encore un retard, car les mêmes pratiques nuisibles sévissaient dans toutes les grandes écoles, mais en pire, car le niveau de la recherche et des professeurs n’y est en général pas comparable à celui de l’X. Les reçus obtenaient pratiquement toujours le diplôme. L’École polytechnique constituait le cas le plus caricatural. Les Mines, les Ponts et les Télécommunications présentaient des traits similaires mais moins prononcés. Seules les « petites grandes » écoles réussissaient mieux, car l’avenir de leurs élèves était moins assuré, et les industriels qui y recrutaient des ingénieurs se montraient plus exigeants quant à leur formation. C’était le prestige général fondé sur la tradition, sur la hiérarchie des écoles, qui primait. Je dénonçai encore le laxisme de l’École vis-à-vis des élèves lors d’une cérémonie organisée à l’occasion de mon départ.

En tout cas, les défauts signalés ici constituent un cercle vicieux. L’industrie française ne s’intéresse pas assez aux qualités de recherche de ses ingénieurs, et même pas assez à la recherche ; trop peu d’entreprises ont un laboratoire de recherche ou un bureau d’étude, trop peu ont des relations avec l’Université. Si un ancien élève de grande école a fait une thèse, il entre dans l’industrie plus tard que ses camarades de promotion, et touche donc une rémunération plus faible puisqu’on ne tient pas compte de sa thèse. Il sera en fait pénalisé. Dans ces conditions, les élèves des grandes écoles ne souhaiteront pas faire de recherche. L’industrie empêche donc bien l’École de former des chercheurs. Inversement, l’École, ainsi conditionnée, n’enverra pas de bons esprits chercheurs dans l’industrie, et celle-ci ne s’intéressera pas à la recherche ; l’École empêchera le développement d’une bonne recherche industrielle, et ainsi de suite. Entreprise-École, chacun renforcera la déficience de l’autre. C’est juste le contraire en Allemagne et aux États-Unis. J’ai participé sur ce sujet à une intense propagande, écrit des articles et des livres, organisé des conférences et des journées d’étude, etc. La situation a notablement changé en plusieurs décennies, mais pas encore assez. Un bon ingénieur doit savoir qu’il existe une recherche, des laboratoires d’industries et d’universités, un CNRS, des bibliothèques scientifiques et technologiques. Il doit avoir affronté dans sa jeunesse les difficultés de la recherche. Contrairement à la formation à la recherche qui prépare des futurs chercheurs et universitaires, la formation par la recherche est une recherche de début, qui ne sera pas suivie d’une carrière de recherche. On devrait repenser la formation dans les grandes écoles dans cette optique.

L’Université avait aussi ses problèmes. L’absence de sélection conduisait à une dégénérescence de plus en plus profonde, avant tout dans les premiers cycles. Beaucoup de mes articles et même de mes livres portent sur ce sujet, je ne le reprends donc pas ici. Je me trouvais donc en position de combat sur tous les fronts, mais n’ai pas été seul dans ce combat. Je crois avoir fondamentalement réussi à rénover le département et l’enseignement en ce qui concerne les mathématiques pures. Mais il y a aussi les mathématiques appliquées, dans lesquelles figurent les probabilités. J’ai déjà dit qu’à mon arrivée à l’École les probabilités étaient enseignées à un niveau très bas. Après de nombreuses péripéties, c’est Métivier, probabiliste éminent, qui fut nommé professeur de probabilités. Mais Métivier est mort prématurément d’un cancer. Il avait montré un courage exceptionnel, et sa perte fut très douloureuse pour tous. Jacques Neveu, probabiliste mondialement connu, lui succéda. Le groupe des probabilités a connu un grand développement, et cette branche des mathématiques, ignorée du temps de Paul Lévy, séduit à présent nombre d’élèves.

En ce qui concerne les mathématiques appliquées, qui se développent autour de l’analyse numérique, c’est l’arrivée de Jacques-Louis Lions à l’École qui a tout changé. Jacques-Louis Lions, on s’en souvient, avait été mon élève à Nancy en 1949 et fit sa thèse avec moi en 1954. C’était une thèse sur les équations aux dérivées partielles, pas encore vraiment sur les mathématiques appliquées.

J’avais quelques divergences avec Ésambert. Je trouvais souhaitable, à la fois du point de vue de l’École et de celui de l’Université, qu’un polytechnicien obtint au moins un diplôme universitaire. Aucune direction de l’École n’a jamais accepté cette idée, craignant, c’est évident, les comparaisons qui pourraient en découler. Des données intangibles auraient alors montré que les meilleurs élèves de l’École polytechnique étaient très au-dessus de ceux de l’université, mis à part les normaliens, et qu’environ le tiers d’entre eux n’atteignait pas le niveau inférieur des élèves moyens de l’université. J’ai moi-même eu l’occasion de vérifier ce fait, en proposant aux élèves d’une promotion une interrogation écrite que j’avais donnée en examen à l’université, pendant ma période cumulante. Le résultat confirma point par point ce que je viens de décrire. Les meilleurs élèves de l’École ont eu des notes très élevées, mais beaucoup ont eu des notes qui ne dépassaient pas 2 ou 3, équivalant aux résultats les plus bas des étudiants d’université. C’est évidemment scandaleux.

Comme Claude Allègre, lorsqu’il était conseiller spécial de Lionel Jospin au ministère de l’Éducation nationale, j’aurais souhaité que fût créée une université technologique de haut niveau dans le sud de Paris. Il n’existe en France qu’une seule université technologique, celle de Compiègne, l’UTC, fondée par Daniélou, dont j’ai moi-même fait l’évaluation pour le Comité national d’évaluation lorsque j’en étais président (1988). Son niveau, incontestablement bon, reste inférieur à celui des grandes universités. La formation des ingénieurs, en trois ans après un premier cycle d’université ou en cinq ans après le baccalauréat, y est toutefois excellente. Dans un sondage réalisé parmi les grandes industries à ce sujet, celles-ci l’avaient placée en tête. Mais l’UTC ne propose que des enseignements appliqués. C’était d’ailleurs ma conclusion comme celle de son directeur. Or ce qui est très intéressant dans les universités technologiques étrangères, celles des États-Unis dont je viens de donner deux exemples particulièrement remarquables, celles de Suisse et en particulier du Polytechnicum de Zurich, ou celles d’Allemagne, les Technische Hochschulen, c’est qu’à côté des départements d’ingénieurs elles possèdent des départements de sciences fondamentales du plus haut niveau. Je connais bien l’exemple du Polytechnicum de Zurich dont le département de mathématiques est célèbre. Heinz Hopf, un des principaux fondateurs de la topologie algébrique, mathématique abstraite s’il en fut, y enseigna longtemps, comme Eckmann, également topologiste algébriste de très haut niveau, et Chandrasekharan, qui travaillait en théorie analytique des nombres et s’installa en Suisse après avoir mené une large partie de sa carrière au Tata Institute of Fundamental Research de Bombay. On ne dédaigne pas les sciences les plus abstraites dans les universités technologiques étrangères, et tous les intermédiaires entre celles-ci et les sciences appliquées sont enseignés. L’École polytechnique, bien qu’elle donne le titre d’ingénieurs à ceux qui en sortent, est principalement une école de science fondamentale. Le département de mathématiques appliquées n’a lui-même rien à voir avec un département d’ingénierie. La plupart des autres sont en effet des écoles d’ingénieurs, mais le niveau de leurs départements fondamentaux est nettement moins élevé que celui de leurs départements d’ingénieurs, et il s’y fait peu de recherche fondamentale. Une université technologique regroupant, dans le sud de Paris, l’université d’Orsay, l’École polytechnique et l’École nationale supérieure d’électricité (Supélec) aurait pu entrer en compétition avec les meilleurs établissements de ce type à l’étranger. Ésambert n’a jamais voulu et je l’ai regretté.

Sur les classes préparatoires (pages 68 et 69)

Les taupes sont littéralement épuisantes. La plupart des élèves qui en sortent pour rejoindre les différentes écoles se sont tellement épuisés dans ces classes préparatoires qu’ils se reposent en première année. Le rendement des écoles s’en trouve d’autant diminué. Dans toutes les grandes et même dans beaucoup de petites écoles, certains élèves travailleront peu (voire pas du tout) pendant la totalité de leur scolarité et décrocheront néanmoins le diplôme, profitant du seul avantage d’avoir été reçus à l’entrée. C’est particulièrement flagrant à Polytechnique. Les universités d’Oxford et de Cambridge recrutent leurs jeunes à la sortie de la terminale. Elles opèrent une sélection en fonction de certains critères de valeur scientifique. Les élèves ainsi recrutés ne peuvent en aucun cas se permettre de ne plus travailler s’ils sont reçus à Oxford ou à Cambridge. D’abord, ils en seraient rapidement exclus. Si toutefois ils ne l’étaient pas, leurs connaissances ne dépasseraient pas celles du baccalauréat, et aucun industriel sérieux ne s’intéresserait à un étudiant sortant d’Oxford qui n’y aurait pas travaillé, alors que nos industriels ne craignent pas de recruter quelqu’un qui sort de Polytechnique, de lui confier un poste important, sachant qu’il a tout de même franchi l’obstacle de la taupe. Et tant pis s’il n’a plus travaillé après ! Nous formons donc des ingénieurs d’une valeur scientifique souvent faible.

Je ne voudrais en aucun cas qu’on supprime brutalement les taupes, car elles fonctionnent bien, ce qui n’est guère le cas du premier cycle universitaire. Cela reviendrait tout simplement à démolir le système. Mais je serais partisan d’introduire un certain nombre de modifications importantes. Il devrait exister plusieurs modes de recrutement des Écoles dont l’un reposerait sur le concours, comme c’est le cas aujourd’hui, tandis que d’autres différeraient. On pourrait imaginer qu’un examen du dossier scolaire accompagné d’un entretien ou tout autre type de modalité à étudier seraient susceptibles de drainer vers les Écoles d’excellents éléments. La diversité des recrutements est une nécessité vitale. Le physicien Alfred Kastler a fait une proposition à laquelle personne n’a jamais donné suite. L’École normale, disait-il, devrait proposer à tous ceux qui ont une nomination au concours général dans une des branches adaptées à l’ENS d’entrer tout de suite à l’École sans concours, et leur enseigner, non pas le programme tel qu’il est, mais un programme en cinq ans, analogue à celui du DEUG suivi des trois années actuelles d’École normale, entièrement dispensé par des professeurs d’université, comme c’est à présent le cas à l’École. Je sais que le concours général est loin d’être toujours significatif; il l’est cependant grosse modo en mathématiques et dans les branches littéraires ; il l’est nettement moins dans les sciences expérimentales, physique, chimie ou biologie, car il repose sur une épreuve écrite ou orale à caractère purement théorique. La proposition de Kastler serait donc à moduler. Ajoutons que les filles réussissent souvent mieux au concours d’entrée que les garçons dans les disciplines littéraires, mais peu ou pas du tout dans les disciplines scientifiques, où leurs résultats s’avèrent catastrophiques. D’autres classes que les taupes, et/ou d’autres méthodes de recrutement que le concours actuel leur permettraient sans doute de réaliser de bien meilleures performances. Toujours est-il que cette question du recrutement à partir des classes préparatoires et du concours d’entrée demande à être étudiée avec des idées entièrement nouvelles.

À méditer au vu de l’expérience de Paris-Dauphine ! Il est difficile de parler de l’université française en général. Pour les mathématiques, les laboratoires universitaires sont riches en universitaires qui ne sont pas issus de l’université, qui n’y mettent pas leurs enfants, et qui ne souhaitent pas que l’université change. Souvent de gauche, ils conçoivent l’université comme une œuvre sociale massive, qui ne doit pas faire d’élitisme. L’université pratique donc une sélection par l’échec, qui ne valorise pas les diplômes. Parallèlement, les filières élitistes qui ont produits ces universitaires sont depuis longtemps trustées par les enfants de ceux qui en sont issus. Ce double phénomène illustre à merveille les thèses du sociologue Pierre Bourdieu sur la domination et la dialectique des élites. Le système actuel organise une séparation entre chercheurs en mathématiques, massivement à l’université, et bons élèves, massivement hors de l’université. Il y a beaucoup à dire sur la psychologie et la sociologie des universitaires. Pendant que certains déclarent qu’ils sont trop payés, d’autres pensent exactement le contraire et quittent la France ! Voilà donc toute une gauche universitaire, malade de ses symboles, qui organise depuis longtemps un immobilisme délétère. Malgré tout, certains établissements comme l’École Polytechnique et l’Université Paris-Dauphine font preuve de raison et d’audace. Ils tiennent lieu de laboratoires du futur pour un système à bout de souffle. La période est passionnante !

Note. Les extraits ont été obtenus en utilisant le logiciel de reconnaissance optique de caractères Tesseract sous Debian à partir de pages numérisées par un scanner avec Sane.


Souvenirs – Saint-Flour 1999

June 7th, 2014 2 comments
Saint-Flour 1999

Saint-Flour 1999

From July 9 to 24 1999, I attended as a doctoral student the École d’été de calcul des probabilités de Saint-Flour XXIX. The  courses were given by Erwin Bolthausen (Large deviations and interacting random walks), Edwin Perkins (Dawson-Watanabe superprocesses and measure-valued diffusions), and Aad van der Vaart (Semiparametric statistics). Here is a list of participants:  Abraham · Allard · Arnaudon · Bahadoran · Bardet · Bardina · Beffara · Ben Arous · Ben Hariz · Benassi · Bernard · Bertrand · Birgé · Birkner · Blachère · Bodineau · Brunaud · Campanino · Carstellan-Guérin · Cerny · Chafaï  · Comets · Dedecker · Delmas · Dembo · Dhersin · Djellout · Duquesne · Dury · Espinouze · Fleury · Fougères · Gallardo · Gentil · Guillin · Guionnet · Huet · Ioffe · Klemela · Kulik · Laredo · Le Gall · Lemaire · Letué · Lévy · Löcherbach · Lopez-Mimbela · Malrieu · Markckert · Martin · Massart · Matias · Moret · Mselati · Nicaise · Nualart D. · Nualart E · Owhadi · Pardoux · Paroux · Perisic · Picard · Rachad · Rio · Rovira · Rozenholc · Saint Loubert · Savona · Scheffer · Sega · Serlet · Sortais · Taupin · Thiebot · Tindel · Todorova-Kolkovska · Trashorras · Velenik · Vert · Zani · Zeitouni.


Back to basics – Order statistics of exponential distribution

June 3rd, 2014 No comments
Alfred and Katalin Rényi in Oberwolfach in 1966

Alfred and Katalin Rényi – Oberwolfach, 1966

This short post is devoted to one of these beautiful elementary facts, which can be found in a paper by Alfréd Rényi (1921 – 1970) entitled On the theory of order statistics published in Acta Math. Acad. Sci. Hungar. 4, (1953) 191-231, dedicated to A. N. Kolmogorov on the occasion of his fiftieth birthday. It seems that it can also be found in a paper by Benjamin Epstein and Milton Sobel entitled Life testing published in J. Amer. Statist. Assoc. 48 (1953) 486-502.

The identity. Let \( {E_1,\ldots,E_n} \) be i.i.d. real random variables following an exponential distribution on \( {[0,\infty)} \). Since \( {(E_1,\ldots,E_n)} \) has a density, it follows that with probability one, the random variables \( {E_1,\ldots,E_n} \) are pairwise distinct, and therefore there exists a unique random permutation \( {\sigma\in S_n} \) such that \( {E_{\sigma(1)}<\cdots< E_{\sigma(n)}} \). Let us write \( {E_{(k)}:=E_{\sigma(k)}} \). Note that \( {E_{(1)}=\min(E_1,\ldots,E_n)} \) and \( {E_{(n)}=\max(E_1,\ldots,E_n)} \). We have the following beautiful identity in distribution:

\[ (E_{(1)},\ldots,E_{(n)}) \overset{d}{=} \left(\frac{E_1}{n},\cdots,\frac{E_1}{n}+\cdots+\frac{E_n}{1}\right). \]

In particular \( {E_{(k)}\overset{d}{=}\frac{E_1}{n}+\cdots+\frac{E_{k}}{n-k+1}} \) for every \( {1\leq k\leq n} \). To see it, for every bounded and measurable test function \( {\varphi:\mathbb{R}^n\rightarrow\mathbb{R}} \), we get, using changes of variables,

\[ \begin{array}{rcl} \mathbb{E}(\varphi(E_{(1)},\ldots,E_{(n)})) &=&\int_{[0,\infty)^n}\!\varphi(x_{(1)},\ldots,x_{(n)})\, \lambda^ne^{-\lambda(x_1+\cdots+x_n)}\,dx_1\cdots dx_n\\ &=&n!\int_{0\leq y_1<\cdots<y_n}\!\varphi(y_{1},\ldots,y_{n})\, \lambda^ne^{-\lambda(y_1+\cdots+y_n)}\,dy_1\cdots dy_n\\ &=&\int_{[0,\infty)^n}\!\varphi(z_1,\ldots,z_1+\cdots+z_n)\, n!\lambda^ne^{-\lambda(nz_1+\cdots+1z_n)}\,dz_1\cdots dz_n. \end{array} \]

It follows that the real random variables \( {E_{(1)},E_{(2)}-E_{(1)},\ldots,E_{(n)}-E_{(n-1)}} \) are independent with \( {E_{(k)}-E_{(k-1)}} \) exponential with mean \( {1/((n-k+1)\lambda)} \).

The identity \( {E_{(1)}\overset{d}{=}\frac{1}{n}E_1} \) is a special case of the more general identity

\[ \min\left(\frac{E_1}{\lambda_1},\ldots,\frac{E_n}{\lambda_n}\right) \overset{d}{=}\frac{E_1}{\lambda_1+\cdots+\lambda_n}, \]

valid for any \( {\lambda_1>0,\ldots,\lambda_n>0} \), which plays a fundamental role in the structure of Markov processes. With probability one the \( {\min} \) is achieved at a unique random integer \( {N} \) in \( {\{1,\ldots,n\}} \) independent of the value of the minimum and distributed according to the discrete law \( {\mathbb{P}(N=k)=\lambda_k/(\lambda_1+\cdots+\lambda_n)} \) for every \( {1\leq k\leq n} \).

The identity \( {E_{(n)}\overset{d}{=}\frac{E_1}{n}+\cdots+\frac{E_n}{1}} \) appears in the analysis of the jump times of the continuous time regular branching tree called the Yule process, and in the analysis of the more recent common ancestor in the genealogy of the Fisher-Wright model.

To go a bit further, if \( {F_E} \) is the cumulative distribution function of the \( {E_i} \)’s, which is exponential: \( {F_E(x)=(1-e^{-\lambda x})\mathbf{1}_{[0,\infty)}(x)} \), and if \( {X_1,\ldots,X_n} \) are i.i.d. with continuous cumulative distribution function \( {F_X} \), then, by monotonicity,

\[ (X_{(1)},\ldots,X_{(n)}) \overset{d}{=} \left((F_X^{-1}\circ F_E)\left(\frac{E_1}{n}\right), \ldots,(F_X^{-1}\circ F_E)\left(\frac{E_1}{n}+\cdots+\frac{E_n}{1}\right)\right). \]

Link with Dirichlet distribution. Actually, it is more customary to express order statistics in terms of i.i.d. uniforms rather than in terms of i.i.d. exponentials. Order statistics of uniforms are linked with Dirichlet distributions. Namely, the random variables \( {U_1:=F_X(X_1),\ldots,U_n:=F_X(X_n)} \) are i.i.d. uniform on \( {[0,1]} \), and therefore it is well known that \( {(U_{(1)},U_{(2)}-U_{(1)},\ldots,1-U_{(n)})} \) follows a Dirichlet distribution on \( {[0,1]} \) of size \( {n} \) and parameter \( {(1,\ldots,1)} \), and thus, by monotonicity,

\[ (F_X(X_{(1)}),\ldots,F_X(X_{(n)})) \overset{d}{=} \frac{(E_1,\ldots,E_1+\cdots+E_n)}{E_1+\cdots+E_{n+1}}. \]

In particular, if the \( {X_i} \)’s are uniform on \( {[0,1]} \) then we get the identity in distribution

\[ \left(F_E\left(\frac{E_1}{n}\right), \ldots,F_E\left(\frac{E_1}{n}+\cdots+\frac{E_n}{1}\right)\right) \overset{d}{=} \frac{(E_1,\ldots,E_1+\cdots+E_n)}{E_1+\cdots+E_{n+1}}. \]

In particular, for every \( {1\leq k\leq n} \), the random variable \( {F_E(E_1/n+\cdots+E_k/(n-k+1))} \) is identical in distribution to the random variable \( {(E_1+\cdots+E_k)/(E_1+\cdots+E_{n+1})} \), a marginal of a Dirichlet distribution, which follows the Beta distribution on \( {[0,1]} \) of parameter \( {(1,n-1)} \). All these funny identities in distribution constitute actually the tip of an iceberg dealing with Beta, Gamma, Dirichlet distributions and Poisson point processes. They are useful for instance for the analysis of Kolmogorov-Smirnov type statistics, which constitute actually the main motivation of the paper of Rényi. This is also useful in many other situations. One may take a look for instance at the paper by Raoul LePage, Michael Woodroofe, and Joel Zinn, entitled Convergence to a stable distribution via order statistics and published in Ann. Probab. 9 (1981) 624-632. We used the approach with Charles Bordenave and Pietro Caputo for our analysis of random Markov chains models in arXiv:0903.3528 and published in Ann. Probab. 39(4) (2011) 1544-1590.

Further reading. Concentration inequalities for order statistics, by S. V. Boucheron and M. Thomas, Electronic Communications in Probability 17, paper 51, 1-12 (2012)

Categories: Probability, Statistics