7
$\begingroup$

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.

$\endgroup$

3 Answers 3

9
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ How good are those bounds when $\epsilon$ is small? $\endgroup$ Oct 18, 2012 at 10:10
  • $\begingroup$ Good question - see my edit above (since the question was about concentration results it is reasonable to assume $m\to\infty$) $\endgroup$ Oct 18, 2012 at 15:23
2
$\begingroup$

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.

$\endgroup$
0

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.