Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
    
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. –  Steve Flammia 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$ –  anadim Dec 22 '09 at 17:54
2  
yes, this is true for any alpha> pi/2 –  Gil Kalai Dec 22 '09 at 18:26
4  
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. –  Gil Kalai Dec 22 '09 at 18:28
1  
Gil, you should post this as an answer! –  Greg Kuperberg Dec 23 '09 at 6:58

2 Answers 2

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?

share|improve this answer
1  
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}$. –  Thorny 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)$ ?

share|improve this answer
    
I am trying to find such a function $\phi$ that is exponentially vanishing in $n$. –  anadim Dec 22 '09 at 18:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.