# Tail inequality on sum of product of normal variables

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.

• 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. Oct 20 '12 at 9:58
• Also, do you mean $\geq$ instead of $\leq$ inside the probability function? 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? Oct 20 '12 at 11:55
• Yes, all $x_i$ and $y_i$ are independent from each other. Oct 20 '12 at 13:13
• 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/… . Oct 21 '12 at 7:28

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