# Concentration results for inner products of two independent random gaussian vectors

Hi,

I wanted to know if there are standard results on concentration of absolute value of inner products of two random vectors. Thus if $X, Y \in R^m$ are two independent random vectors with each entry distributed as $\mathcal{N}(0, 1/m)$, then how can we bound the following probability expression: $P ( | X^T Y | > \epsilon )$ ? Here, $\epsilon > 0$ is a given constant that is small.

-

An alternative method is to exploit the rotational invariance of the Gaussian. You can write $$X^T Y = |X| \left( \left(\frac{X}{|X|}\right)^T Y \right).$$ Because $Y$ is rotationally invariant, the inner product is now independent of $X$, and in fact just has distribution $N(0,1/m)$. Now let $C>1$ be an arbitrary parameter. We can bound the probability $X^T Y > \epsilon$ by the probability one of the following two events occur.

1. $\left(\frac{X}{|X|}\right)^T Y \geq \frac{\epsilon}{C}$. Assuming $\epsilon \sqrt{m}/C$ tends to infinity, this occurs with probability $\Phi (\frac{\epsilon \sqrt{m}}{C})=(1+o(1)) \sqrt{\frac{m}{2 \pi}} \exp(-\frac{\epsilon^2 m}{C^2})$.

2. $|X| \geq C$. The norm of a Gaussian vector is well studied, and it is standard (see, for example Chapter 2 of these notes, that $|X|$ is tightly concentrated around its expectation. For example, applying Corollary 2.3 of the linked notes gives that the probability this occurs is at most $\exp(-\frac{1}{4} (1-\frac{1}{C^2})^2 m)$

For $\epsilon$ bounded away from $0$ you can choose $C$ to optimize the sum of the two terms getting a bound that is exponential in $m$ but with a non-optimal exponent. If $\epsilon$ is tending to $0$ with $m$, then the first term is dominant. That term remains small so long as $\epsilon$ is much larger than $\sqrt{\frac{\log m}{m}}$.

-

Since you're trying to bound the sum of zero-mean i.i.d. RVs, I would recommend you try to develop a Chernoff bound: $$\Pr(X^TY>\epsilon)\leq \inf_{s\geq 0}\Big(e^{-s\epsilon }\big(Ee^{sZ}\big)^m\Big)$$ where $Z=X_1Y_1$ is distributed according to a Normal Product distribution. I haven't carried out the calculation in full but I believe the moment generating function $Ee^{sZ}$ can be computed in close form using the expression (6) for $K_0$ found here.

As to tightness of the bound, notice that $$\Pr(X^TY>\epsilon)=\Pr\Big(\sum_{i=1}^m\hat{Z}_i>m\epsilon\Big)$$ where the $\hat{Z}_i$ are i.i.d. and each one is the product of two independent standard ($\mathcal{N}(0,1)$) Gaussian RVs. It is a standard Large Deviations result that such probability goes to zero exponentially fast as $m\to\infty$ for every constant $\epsilon>0$. I am 99% sure that the Chernoff bound always yields the correct exponential rate (but not the correct coefficient of the leading exponent).

-
How good are those bounds when $\epsilon$ is small? – Douglas Zare Oct 18 '12 at 10:10
Good question - see my edit above (since the question was about concentration results it is reasonable to assume $m\to\infty$) – Yair Carmon Oct 18 '12 at 15:23

If $m=2$ then this is a Laplace distribution. Equivalently, the distribution of the determinant of a $2\times2$ matrix with IID centered normal entries is a Laplace distribution. See whuber's comment.

A Laplace distribution is also the difference of two IID exponentials. So, if $m$ is even, then the inner product can be written as a sum of $m/2$ IID Laplace distributions, or the difference of two IID gamma distributions. See "tight bounds on probability of sum of laplace random variables" for the density function as a single sum.

-