# Concentration of measure for gaussian inner products

There exists extensive theory for the concentration of Gaussian measure. Through that, it can be easily proved that the square of the $\ell_2$ norm of a length $n$ zero mean Gaussian vector ${\bf x}$ with covariance matrix ${\bf I}_n$ is concentrated around $n$ with overwhelming probability. Such a result also follows immediately from the Restricted Isometry Property that holds for Gaussian matrices. I was wondering if any concentration results could be inferred for inner products of Gaussian i.i.d random variables. Namely, if $\Pr(|{\bf x}{\bf y}|<\alpha)$ is overwhelming (or exponentially vanishing in $n$) for some meaningful $\alpha$.

• Your notation isn't clear. Do you want a concentration result for ${\rm Pr}(| |\langle x,y\rangle| - \mu | < \epsilon$? Where $\mu$ is say a mean or median and $x$ and $y$ are independent Gaussian vectors? If so, this is a standard result. Dec 22 '09 at 17:39
• I was looking for $\Pr(||\langle x,y\rangle|-\sqrt{n}|<\epsilon)$ and x,y are i.i.d Gaussian zero mean vector with covariance matrix the identity of size $n\times n$ Dec 22 '09 at 17:54
• yes, this is true for any alpha> pi/2 Dec 22 '09 at 18:26
• One way to say it is that most ponts in the sphere are near the equator. (You can assume x is the north pole.) This follows from the formulas for volumes of spherical caps. Dec 22 '09 at 18:28
• Gil, you should post this as an answer! Dec 23 '09 at 6:58

If you have 2 standard Gaussians in $\mathbb{R}^n$, their inner product is the sum of $n$ i.i.d. variables, with their common distribution fixed (and having finite moments), so you will get convergence to the appropriate Gaussian distribution in line with the central limit theorem, with exponential bounds coming from Hoeffding's inequality, say. Do you need tight bounds or asymptotics is enough?
• Also, what Gil Kalai said: testing for $|\langle x,y \rangle|<\alpha$ is with high probability in $x$ testing for $y$ to fall within a layer of width $2\alpha/\sqrt{n}$ centered around the origin, so up to an exponentially decaying error you get $2\Phi\left(\frac{\alpha}{\sqrt{n}}\right)$, so you will get exponential bounds for $\alpha >> \sqrt{n \log n}$. Dec 23 '09 at 8:55
I am not sure if I am understanding you quite clearly: you have i.i.d Gaussian random variables $x_i, y_i$ so that for any $\alpha > 0$ the quantity $P[|\sum_i x_i y_i| < \alpha]$ goes to zero. What you are looking for is the rate of convergence to zero ? Or you are looking for a function $\phi$ that gives non-trivial bounds like $P[|\sum_{i=1}^n x_i y_i| < \alpha] \leq \phi(\alpha, n)$ ?
• I am trying to find such a function $\phi$ that is exponentially vanishing in $n$. Dec 22 '09 at 18:41