3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Dec 22, 2009 at 17:39
  • $\begingroup$ 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$ $\endgroup$
    – anadim
    Dec 22, 2009 at 17:54
  • 2
    $\begingroup$ yes, this is true for any alpha> pi/2 $\endgroup$
    – Gil Kalai
    Dec 22, 2009 at 18:26
  • 4
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Dec 22, 2009 at 18:28
  • 1
    $\begingroup$ Gil, you should post this as an answer! $\endgroup$ Dec 23, 2009 at 6:58

2 Answers 2

1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Thorny
    Dec 23, 2009 at 8:55
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I am trying to find such a function $\phi$ that is exponentially vanishing in $n$. $\endgroup$
    – anadim
    Dec 22, 2009 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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