Let $U, V$ be two standard normal random variables with covariance $cov(U,V) = \beta \in [0,1)$. Let $W = UV$ be the product of two RV's, and $W_1, W_2, \ldots, W_n$ be n i.i.d copies of $W$, what's the tail bound for $Y = \frac{1}{n}\sum_{i=1}^nW_i  \beta$? That is, for any $t > 0$, $P(Y < t) < ?$ and $P(Y > t) < ?$.

$\begingroup$ What do you mean, specifically, by "the sharpest tail bound"? Without specifying desirable properties of the bound, one can always consider any expression to be the sharpest bound on itself. $\endgroup$ – Iosif Pinelis Jun 29 '16 at 15:19

$\begingroup$ Sorry for the misleading term. I have deleted "sharpest". My intention was to get a very tight bound about the tail probabilities. Thank you! $\endgroup$ – Wuchen Jun 29 '16 at 15:31

$\begingroup$ I think the characterization of the bound needs to be much more specific than "very tight". Perhaps you can do some numerical experiments and come up with a specific conjecture $\endgroup$ – Iosif Pinelis Jun 29 '16 at 16:16
Let $b:=\beta$. Assume, more generally, that $1<b<1$. To reflect the dependence on $b$, write $W_{i,b}$ and $Y_b:= \frac{1}{n}\sum_{i=1}^nW_{i,b}b$ in place of $W_i$ and $Y$. The problem is equivalent to finding a bound on $P(X_b>x)$ for $X_b:=Y_b+b=\frac{1}{n}\sum_{i=1}^nW_{i,b}$, $x:=y+b$, $y>0$, and all $b\in(1,1)$, because the left tail of $X_b$ is the same as the right tail of $X_{b}$. That is, for all $y>0$ one has $P(Y_{b}>y)=P(X_b>y+b)$ if $b\in[0,1)$ and $P(Y_{b}<y)=P(X_b>y+b)$ if $b\in(1,0]$.
One can use an exponential bound. Note that, for independent standard normal random variables $Z_1$ and $Z_2$, the random set $\{U,V\}$ is equal in distribution to the random set $\{(Z_1aZ_2)k,(Z_1+aZ_2)k\}$ if $k^2=\frac{1+b}2$ and $a^2=\frac{1b}{1+b}$, whence $W=UV$ is equal in distribution to $(Z_1aZ_2)(Z_1+aZ_2)k^2=k^2Z_1^2k^2a^2Z_2^2=\frac{1+b}2\,Z_1^2\frac{1b}2\,Z_2^2$. So, for $0\le h<h_b:=\frac1{1+b}$, \begin{equation} E e^{hUV}=E e^{hk^2Z_1^2}E e^{hk^2a^2Z_2^2}=\frac1{\sqrt{1(1+b)h}}\,\frac1{\sqrt{1+(1b)h}}, \end{equation} whence \begin{equation} P(X>x)\le E e^{nh(Xx)}=\exp\{n\ell(h)\}, \end{equation} where $$\ell(h):=\ell_{b,x}(h):=hx\tfrac12\,\ln\big(12bh(1b^2)h^2\big).$$ It is not hard to see that $\ell(h)$ is minimized at $h=h_{b,x}$, where \begin{equation} h_{b,x}:=\frac{\sqrt{\left(1b^2\right)^2+4 x^2}(1b^2+2 b x)}{2 \left(1b^2\right) x}\in(0,h_b) \end{equation} if $x\ne0$ and $h_{b,x}:=\frac b{1b^2}\in(0,h_b)$ if $x=0$ (in which latter case necessarily $b=xy=y<0$). Thus, the best exponential bound on $P(X>y+b)$ is $\exp\{n\ell_{b,y+b}(h_{b,y+b})\}$. Here is the graph of the exponential rate $\ell_{b,y+b}(h_{b,y+b})$ for $b\in(1,1)$ and $y\in(0,3)$:
Note also that, according to Theorem 1 on page 495 in [Chernoff, The Annals of Mathematical Statistics, Vol. 23, No. 4 (1952), pp. 493507], the upper bound $\exp\{n\ell_{b,y+b}(h_{b,y+b})\}$ is optimal in the sense that $$P(X>y+b)=\exp\{n\ell_{b,y+b}(h_{b,y+b})(1+o(1))\}$$ as $n\to\infty$.

$\begingroup$ Thank you for your answer. This is exponential bound is true only when $h_{b,x} < h_{b}$, which poses constraints on $x$. Is that right? $\endgroup$ – Wuchen Jun 29 '16 at 23:18

$\begingroup$ No further constraints on $x>b$. The condition $h_{b,x}\in(0,h_b)$ is automatically satisfied for all such $x$ and all $b\in(1,1)$. I have added this detail to the answer. $\endgroup$ – Iosif Pinelis Jun 29 '16 at 23:42


$\begingroup$ One more question, why is left tail the same as the right tail for $X_b$? It seems to me that $X_b$ is not symmetric around its mean. $\endgroup$ – Wuchen Jun 30 '16 at 0:27

$\begingroup$ As I said, the left tail of $X_b$ is the same as the right tail of $X_{−b}$ (not of $X_b$). Of course, the distribution of $X_b$ is not symmetric (about its mean). $\endgroup$ – Iosif Pinelis Jun 30 '16 at 1:00