13
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ 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. $\endgroup$
    – cardinal
    Oct 20 '12 at 9:58
  • 1
    $\begingroup$ Also, do you mean $\geq$ instead of $\leq$ inside the probability function? $\endgroup$
    – cardinal
    Oct 20 '12 at 10:00
  • $\begingroup$ 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? $\endgroup$
    – user16093
    Oct 20 '12 at 11:55
  • $\begingroup$ Yes, all $x_i$ and $y_i$ are independent from each other. $\endgroup$
    – user16093
    Oct 20 '12 at 13:13
  • 1
    $\begingroup$ A very similar question was asked on MO: mathoverflow.net/questions/109989/… I'm not totally satisfied with any of the answers. I think you can do better. See stats.stackexchange.com/questions/4816/… . $\endgroup$ Oct 21 '12 at 7:28
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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