## Archive for February, 2013

### Some Gaussians hidden in uniform measures…

February 5, 2013

Consider a vector ${\theta\sim\textsf{N}(0, {\textrm{I}}/N)}$ where ${\theta \in {\mathbb R}^N}$. It is often claimed that this distribution is “very close”, in the limit of large ${N}$, to that of the uniform measure on the sphere ${S_N \subset {\mathbb R}^N}$ of unit radius. This is, in fact, not hard to see (informally) using a Chernoff bound argument. Firstly, let ${\theta_i}$ denote the ${i^{\mathrm{th}}}$ entry of ${\theta}$. More precisely, the Chernoff argument yields the following inequalities:

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}\left(\sum_{i=1}^N\theta_i^2 \le 1-\epsilon\right)&\le& \exp\left\{ \frac{N}{2}(\epsilon - \log(1-\epsilon) \right\} \\ \mathop{\mathbb P}\left(\sum_{i=1}^N\theta_i^2 \ge 1+\epsilon \right)&\le& \exp\left\{ \frac{N}{2}(-\epsilon + \log(1+\epsilon) \right\}. \end{array}$

The way to obtain this is pretty standard. For instance the first inequality can be obtained as:

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}\left(\sum_{i=1}^N\theta_i^2 \le 1-\epsilon\right)&=&\mathop{\mathbb P}\left[\exp(-\lambda \sum_{i=1}^N\theta_i^2) \ge \exp(-\lambda(1-\epsilon)) \right]\\ &\le& \mathop{\mathbb E}\left[ \exp(-\lambda\sum_{i=1}^N \theta_i^2) \right]\exp(\lambda(1-\epsilon)), \end{array}$

where ${\lambda\ge0}$ and the inequality is by Markov. Optimizing over ${\lambda}$ yields the result. This tells us that ${\lVert\theta\rVert^2}$ concentrates around the expected value of 1 at least to the extent of ${O(N^{-1/2 + \delta})}$ for a small constant ${\delta}$. In fact one can do better than this using an exact large deviations calculation, which I will probably leave to another post.

Thus for large dimensions ${N}$, the probability mass of the distribution ${\textsf{N}(0, {\textrm{I}}/N)}$ is concentrated in a shell of thickness ${O(N^{-1/2})}$ and mean radius 1, which intuitively, looks very much like ${S_N}$. The question that interested me is how we can prove the converse: assuming ${\theta\sim U(S_N)}$ where ${U(S_N)}$ denotes the spherical measure on ${S_N}$ do the marginals of each entry, say ${\theta_1}$ look Gaussian? More precisely, let ${\mu_N}$ denote the measure of ${\sqrt N \theta_1}$ on ${({\mathbb R}, \mathcal{B})}$. Then, does ${\mu_N}$ converge weakly to ${\textsf{N}(0, 1)}$? This is, in fact, true and is an old result due to Borel in his (book/treatise) “Introduction géometrique à quelques théorie physiques”. I will sketch a simple argument via characteristic functions.

The function ${\phi(\lambda) \equiv \mathop{\mathbb E}(e^{\iota\lambda\sqrt N \theta_1})}$ is the characteristic function of ${\sqrt N \theta_1 \sim \mu_N}$, where ${\iota = \sqrt{-1}}$. We can compute this integral explicitly. The formula for the “area” of an ${N}$-dimensional spherical cap as given (here) is:

$\displaystyle \begin{array}{rcl} A &=& \frac{1}{2}A_N I_{2h-h^2}\left( \frac{N-1}{2}, \frac{1}{2} \right), \end{array}$

where ${A_N}$ is the surface area of ${S_N}$, ${h}$ is the depth and ${I_{2h-h^2}(\cdot, \cdot)}$ is the normalized incomplete beta function. Differentiating this, dividing by ${A_N}$ and noting that ${h \equiv 1 - \theta_1}$, we can compute the characteristic function as the following integral:

$\displaystyle \begin{array}{rcl} \phi(\lambda) &=& B\left( \frac{n-1}{2}, \frac{1}{2} \right)^{-1} \int_{-1}^1 e^{\iota\lambda\sqrt N \theta_1}(1-\theta_1)^{(N-3)/2}\mathrm{d}\theta_1, \end{array}$

where ${B(\cdot, \cdot)}$ is the beta function. To do the above, we have to take care of a few sign conventions, which I have omitted. Now, ${B(x, y) \approx \Gamma(y)x^{-y}}$ for fixed ${y}$ and large ${x}$ by Stirling’s approximation. With this and a change of variables ${y \equiv \sqrt N \theta_1}$, we obtain:

$\displaystyle \begin{array}{rcl} \phi(\lambda) &\approx& \frac{1}{\Gamma(\frac{1}{2}) \left( \frac{N-1}{2} \right)^{-1/2}\sqrt{N}} \int_{-\sqrt N}^{\sqrt N} e^{\iota\lambda y}\left( 1-\frac{y^2}{N} \right)^{(N-3)/2}\mathrm{d}y \\ &\rightarrow& \frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty e^{\iota \lambda y} e^{-y^2/2}\mathrm{d}y, \end{array}$

by dominated convergence. The last limit is precisely what we require, namely the characteristic function ${\phi_G(\lambda) = \mathop{\mathbb E}(e^{\iota\lambda G})}$ where ${G\sim\textsf{N}(0,1)}$. The rest follows from Lévy’s continuity theorem.

There are significant improvements to this result. Diaconis and Freedman prove that this holds for all low-dimensional marginals, even in the sense of variation distance. More precisely, let ${\theta_k \in {\mathbb R}^k}$ denote the restriction of ${\theta}$ to the first ${k}$ entries. They give a sharp bound on the variation distance between the law of ${\sqrt{N}\theta_k}$ and ${\textsf{N}(0, {\textrm{I}}_k)}$. Interesting generalizations include this result by D’Aristotile, Diaconis and Newman which says that ${\mathop{\textsf{Tr}}(AU) \approx \textsf{N}(0, 1)}$ when ${U}$ is a orthogonal matrix of size ${N\times N}$ chosen uniformly at random, and ${\mathop{\textsf{Tr}}(AA^\textsf{T}) = N}$, and others which state that even a “small” submatrix of ${U}$ behaves as though its entries were iid standard normals.

I am sure I have barely scratched the surface here, but it is clear that many (and sometimes intuitively plausible) approximations of this kind are actually fairly accurate even rigorously.

UPDATE (04/05/13): Thanks to Jiantao Jiao for some corrections above.