Press "Enter" to skip to content

Month: November 2011

Central limit theorems for convex bodies

Gaussian

This post is devoted to central limit theorems for convex bodies.

The uniform law on the cube. Let \( {X=(X_1,\ldots,X_n)} \) be a random variable distributed according to the uniform law on the cube

\[ B_{n,\infty}(\sqrt{3}) =\left\{x\in\mathbb{R}^n:\max_{1\leq i\leq n}|x_i|\leq\sqrt{3}\right\} \]

The coordinates \( {X_1,\ldots,X_n} \) are i.i.d. with uniform law on \( {[-\sqrt{3},\sqrt{3}]} \). In particular,

\[ \mathbb{E}(X)=0 \quad\text{and}\quad \mathrm{Cov}(X)=I_n. \]

The classical central limit theorem gives then that as \( {n\rightarrow\infty} \),

\[ \frac{X_1+\cdots+X_n}{\sqrt{n}}\overset{d}{\longrightarrow}\mathcal{N}(0,1), \]

where \( {\mathcal{N}(0,1)} \) stands for the Gaussian law on \( {\mathbb{R}} \) with mean \( {0} \) and variance \( {1} \). Actually, and more generally, by the classical Berry-Esseen theorem (the version for independent and possibly not identically distributed random variables), we know that for a well spread \( {\theta} \) in the unit sphere (in the sense of a ratio of norms), as \( {n\rightarrow\infty} \),

\[ \left<X,\theta\right>\overset{d}{\longrightarrow}\mathcal{N}(0,1). \]

This does not hold for all \( {\theta} \) in the unit sphere, and a simple counter example is given by \( {\theta=e_1} \) for which \( {\left<X,\theta\right>=X_1\sim\mathrm{Uniform}([-\sqrt{3},\sqrt{3}])} \) which is not Gaussian as \( {n\rightarrow\infty} \).

The uniform law on the sphere. Let \( {X=(X_1,\ldots,X_n)} \) be a random variable distributed according to the uniform law on the sphere

\[ S_{n,2}(\sqrt{n}) =\left\{x\in\mathbb{R}^n:\sqrt{x_1^2+\cdots+x_n^2}=\sqrt{n}\right\}. \]

A way to simulate \( {X} \) consists in using the identity in law

\[ X \overset{d}{=} \sqrt{n}\frac{G}{\sqrt{G_1^2+\cdots+G_n^2}} \]

where \( {G=(G_1,\ldots,G_n)\sim\mathcal{N}(0,I_n)} \). The classical law of large numbers gives \( {G_1^2+\cdots+G_n^2=n(1+o(1))} \) almost surely. This gives that \( {X_1\overset{d}{=}(1+o(1))G_1} \) converges in law to \( {\mathcal{N}(0,1)} \) as \( {n\rightarrow\infty} \). By rotational invariance, for any \( {\theta} \) in the unit sphere, as \( {n\rightarrow\infty} \),

\[ \left<X,\theta\right>\overset{d}{\longrightarrow}\mathcal{N}(0,1). \]

In particular, for \( {\theta=(1/\sqrt{n},\ldots,1/\sqrt{n})} \), we get, as \( {n\rightarrow\infty} \),

\[ \frac{X_1+\cdots+X_n}{\sqrt{n}}\overset{d}{\longrightarrow}\mathcal{N}(0,1). \]

From the sphere to the ball with the Archimedes principle. The Archimedes principle states that the projection of the uniform law of the unit sphere of \( {\mathbb{R}^3} \), on a diameter, is exactly the uniform law on the diameter. More generally, if \( {n\geq3} \) and \( {X=(X_1,\ldots,X_n)} \) is a uniform random variable on the unit sphere \( {S_{n,2}(1)} \) of \( {\mathbb{R}^n} \) then \( {(X_1,\ldots,X_{n-2})} \) is uniform on the unit ball \( {B_{n-2,2}(1)} \) of \( {\mathbb{R}^{n-2}} \). Letac has few pages on this nice antic observation. This does not work if one replaces \( {n-2} \) by \( {n-1} \). Note that the projection of the uniform law of the unit circle on a diameter gives an arc-sine law and not the uniform law.

The uniform law on the ball. Let \( {X=(X_1,\ldots,X_n)} \) be a random variable following the uniform law on the ball

\[ B_{n,2}(\sqrt{n})=\left\{x\in\mathbb{R}^n:\sqrt{x_1^2+\cdots+x_n^2}\leq\sqrt{n}\right\}. \]

A way to simulate \( {X} \) is to use the Archimedes principle:

\[ X\overset{d}{=}\frac{\sqrt{n}}{\sqrt{n+2}}(Y_1,\ldots,Y_n) \]

where \( {Y=(Y_1,\ldots,Y_{n+2})} \) is uniform on \( {S_{n+2,2}(\sqrt{n+2})} \). Now, from our preceding analysis on the sphere, we obtain that \( {X_1\overset{d}{=}(1+o(1))Y_1} \) tends in law to \( {\mathcal{N}(0,1)} \) as \( {n\rightarrow\infty} \). By rotational invariance, for any \( {\theta} \) in the unit sphere, as \( {n\rightarrow\infty} \),

\[ \left<X,\theta\right>\overset{d}{\longrightarrow}\mathcal{N}(0,1). \]

In particular, taking \( {\theta=(1/\sqrt{n},\ldots,1/\sqrt{n})} \), we get, as \( {n\rightarrow\infty} \),

\[ \frac{X_1+\cdots+X_n}{\sqrt{n}}\overset{d}{\longrightarrow}\mathcal{N}(0,1). \]

Note that here again we have

\[ \mathbb{E}(X)=0 \quad\text{and}\quad \mathrm{Cov}(X)\approx I_n. \]

It is worthwhile to mention an alternative simulation algorithm of the uniform law on \( {B_{n,2}(1)} \). Namely, and following Barthe, Guédon, Mendelson, and Naor, if \( {G=(G_1,\ldots,G_n)} \) and \( {E} \) are independent with \( {G\sim\mathcal{N}(0,I_n)} \) and \( {E\sim\mathrm{Exponential}(1)} \) then

\[ X\overset{d}{=}\sqrt{n}\frac{G}{\sqrt{G_1^2+\cdots+G_n^2+2E}}. \]

Exercise. Show that the central limit theorem holds for the \( {\ell^1} \) ball with suitable radius, using the probabilistic representation of the uniform law on the \( {\ell^1} \) unit sphere

\[ \frac{E}{|E_1|+\cdots+|E_1|} \]

where \( {E=(E_1,\ldots,E_n)} \) has i.i.d. components following a symmetric exponential distribution.

The central limit theorem for convex bodies. So, well, the central limit theorem holds for the uniform law on the cube and on the ball, two remarkable convex bodies. We note also:

  • normalization used: zero mean and identity covariance. In other words, the coordinates are centered, uncorrelated, with unit variance. This does not mean that they are independent. Their possible dependence is related to the geometry of the convex body (independent for the cube but dependent for the ball). For any \( {\theta} \) in the unit sphere, since \( {X} \) has zero mean and identity covariance,

    \[ \mathbb{E}(\left<X,\theta\right>)=0 \quad\text{and}\quad \mathbb{E}(\left<X,\theta\right>^2) =\mathrm{Var}(\left<X,\theta\right>) =\left<\theta,\mathrm{Cov}(X)\theta\right> =\left\Vert\theta\right\Vert_2^2=1. \]

    Therefore \( {\left<X,\theta\right>} \) and \( {\mathcal{N}(0,1)} \) have identical first two moments.

  • possible weights: the \( {\theta} \) version may not work for all \( {\theta} \), and the example of the cube shows that one may experience problems if the most of the mass of \( {\theta} \) is supported by few coordinates. It is actually well known that even for independent random variables, the central limit theorem may fail in the presence of sparsity or localization.

Let \( {K} \) be a convex body, in other words a convex and non empty compact sub-set of \( {\mathbb{R}^n} \). Let us equip \( {K} \) with the uniform law, which is the Lebesgue measure normalized to give a total mass \( {1} \) to \( {K} \). Let us assume that this law has zero mean and identity covariance (isotropy). All \( {\ell^p} \) balls are of this kind. From the examples \( {p=2} \) and \( {p=\infty} \) considered above, it is quite natural to ask if a central limit theorem holds on a generic convex body such as \( {K} \).

The celebrated Dvoretzky theorem is an encouraging result in this direction, dealing with sections instead of projections. Using ideas going back to Sudakov, it has been understood that a central limit theorem is implied by the thin shell property: the norm on \( {K} \) is well concentrated around its mean and most of the mass of \( {K} \) lies in a thin shell. This roughly reduces the problem to show that there exists a sequence \( {\varepsilon_n\rightarrow0} \) which does not depend on \( {K} \) such that if \( {X} \) follows the uniform law of \( {K} \) then

\[ \mathbb{P}\left(\left|\frac{\left\Vert X\right\Vert_2}{\sqrt{n}}-1\right| \geq\varepsilon_n\right) \leq\varepsilon_n. \]

Note that \( {\mathbb{E}(\left\Vert X\right\Vert_2^2)^{1/2}=\sqrt{n}} \). The details are in Anttila, Ball, and Perissinaki. In this kind of convex geometry, the study of uniform laws on convex bodies in naturally superseded by the study of \( {\log} \)-concave probability measures (the indicator of a convex set is \( {\log} \)-concave). Let \( {f:\mathbb{R}^n\rightarrow\mathbb{R}_+} \) be a \( {\log} \)-concave probability density function with respect to the Lebesgue measure, with mean \( {0} \) and covariance \( {I_n} \). In other words, \( {f=e^{-V}} \) with \( {V} \) convex, and

\[ \int\!xf(x)\,dx=0\quad\text{and}\quad\int\!x_ix_jf(x)\,dx=\delta_{i,j}. \]

Let \( {X=(X_1,\ldots,X_n)} \) be a random vector of \( {\mathbb{R}^n} \) with density \( {f} \). The central limit theorem of Klartag states that if additionally \( {f} \) is invariant by any signs flips on the coordinates (we say that it is unconditional, and this holds in particular for all \( {\ell^p} \) balls), then, as \( {n\rightarrow\infty} \),

\[ \frac{X_1+\cdots+X_n}{\sqrt{n}} \overset{d}{\longrightarrow} \mathcal{N}(0,1). \]

Moreover, there exists a uniform quantitative version à la Berry-Esseen on cumulative distribution functions. If one drops the unconditional assumption, then a weaker version of the central limit theorem remains available. Moreover, the central limit theorem remains valid for \( {\left<X,\theta\right>} \), for most \( {\theta} \) in the unit sphere (some directions are however possibly bad, as shown for the cube). The work of Klartag is crucially based on a proof of the thin shell property. An alternative proof was also given by Fleury, Guédon, and Paouris (slightly after Klartag).

Further reading. The main source for this post is the expository paper by Franck Barthe entitled Le théorème central limite pour les corps convexes, d’après Klartag et Fleury-Guédon-Paouris, published in Séminaire Bourbaki (2010). One may also take a look at the survey High-dimensional distributions with convexity properties, by Klartag, and to the paper Variations on the Berry-Esseen theorem by Klartag and Sodin. On this blog, you may also be interested by the blog posts When the central limit theorem fails. Sparsity and localization and Independence and central limit theorems. It is worthwhile to mention that there exists other kinds of central limit theorems for convex bodies, such as the central limit theorem for the volume and the number of faces of random polytopes, obtained by Barany and Vu (it is another convex universe).

Leave a Comment
Syntax · Style · .