Question

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.

Answer 1

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

Answer 2

Thanks for the answers.

@Yair Carmon: Will work on computing the characteristic function. I am quite sure Chernoff bound should be tight enough for my purpose. Thnx !!

Answer 3

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.

Answer 4

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}(e^{-s\epsilon }(Ee^{sZ})^m) $$ 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(\sum_{i=1}^m\hat{Z}_i>m\epsilon)$$ 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).