14

For independent random variables $ x_1,..,x_n$ and $y_1,...,y_n$ following normal distribution $N(0,1)$, I need a simple estimate formula for $P(|\sum_1^n x_iy_i|\ge nt) \leq e^{(?)}$ for $t>1$. Thanks.

Spätzle
  • 2,331
  • 1
  • 10
  • 25
user16093
  • 141
  • 3
  • 3
    Are the $x_i$ and $y_i$ independent? If so, the inner product is a *subexponential* random variable in the sense of R. Vershynin. See his recent expository introduction to nonasymptotic random matrix theory for relevant bounds of the type you desire. – cardinal Oct 20 '12 at 09:58
  • 1
    Also, do you mean $\geq$ instead of $\leq$ inside the probability function? – cardinal Oct 20 '12 at 10:00
  • Thanks. You are right, it should be $P(|\sum_1^n x_iy_i| \geq nt)≤e^{(?)}$. Can you be more specific about the reference? – user16093 Oct 20 '12 at 11:55
  • Yes, all $x_i$ and $y_i$ are independent from each other. – user16093 Oct 20 '12 at 13:13
  • 1
    A very similar question was asked on MO: http://mathoverflow.net/questions/109989/concentration-results-for-inner-products-of-two-independent-random-gaussian-vecto/ I'm not totally satisfied with any of the answers. I think you can do better. See http://stats.stackexchange.com/questions/4816/what-are-the-sharpest-known-tail-bounds-for-chi-k2-distributed-variables . – Douglas Zare Oct 21 '12 at 07:28

1 Answers1

2

The answer to this question is given in Berstein's inequality, as presented in Chapter 2 in Vershynin's book.

For $z_1,...,z_n$ independent, zero-mean, sub-exponential RVs, $$P\left(\left|\sum_i{z_i}\right|\ge nt\right)\le2\exp\left( -cn\cdot\min\left\{ \frac{t^2}{K^2},\frac{t}{K}\right\} \right)$$ where $c$ is a universal constant, $K=\max_i\left\|z_i\right\|_{\psi_1}$ and $\left\|z_i\right\|_{\psi_1}$ is the sub-exponential norm of $z_i$.

Denote $z_i=x_iy_i$. As $x_i,y_i$ are standardized normal RVs, each is a sub-gaussian RV with the sub-gaussian norm $\left\|x_i\right\|_{\psi_2}=\left\|y_i\right\|_{\psi_2}=1$ so $\left\|z_i\right\|_{\psi_1}\le\left\|x_i\right\|_{\psi_2}\cdot\left\|y_i\right\|_{\psi_2}=1$ (see Lemma 2.7.7 in Vershynin's). For convenience, we'll take $\left\|z_i\right\|_{\psi_1}=1$ (lower values would yield tighter bounds). Taking $c=\frac{1}{2}$ (as done in Section 1.3 here), we eventually get:

$$P\left(\left|\sum_i{z_i}\right|\ge nt\right)\le2\exp\left( -\frac{n}{2}\cdot\min\left\{ t^2,t\right\} \right)$$

Spätzle
  • 2,331
  • 1
  • 10
  • 25