Welcome to MathOverflow

Question

2

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

flag	asked Dec 22 2009 at 17:29 anadim 39●2

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 2009 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 2009 at 17:54

2

yes, this is true for any alpha> pi/2 – Gil Kalai Dec 22 2009 at 18:26

2

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 2009 at 18:28

1

Gil, you should post this as an answer! – Greg Kuperberg Dec 23 2009 at 6:58

Thorny · Answer 1 · 2009-12-23 08:47:02Z UTC

1

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?

answered Dec 23 2009 at 8:47

Thorny
1,328●4●7

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 2009 at 8:55

Alekk · Answer 2 · 2009-12-22 18:32:02Z UTC

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)$ ?

Concentration of measure for gaussian inner products

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.