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_1-aZ_2)k,(Z_1+aZ_2)k\}$ if $k^2=\frac{1+b}2$ and $a^2=\frac{1-b}{1+b}$, whence $W=UV$ is equal in distribution to $(Z_1-aZ_2)(Z_1+aZ_2)k^2=k^2Z_1^2-k^2a^2Z_2^2=\frac{1+b}2\,Z_1^2-\frac{1-b}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+(1-b)h}}, \end{equation} whence \begin{equation} P(X>x)\le E e^{nh(X-x)}=\exp\{n\ell(h)\}, \end{equation} where $$\ell(h):=\ell_{b,x}(h):=-hx-\tfrac12\,\ln\big(1-2bh-(1-b^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(1-b^2\right)^2+4 x^2}-(1-b^2+2 b x)}{2 \left(1-b^2\right) x}\in(0,h_b) \end{equation} if $x\ne0$ and $h_{b,x}:=-\frac b{1-b^2}\in(0,h_b)$ if $x=0$ (in which latter case necessarily $b=x-y=-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)$:

enter image description here

Note also that, according to Theorem 1 on page 495 in [Chernoff, The Annals of Mathematical Statistics, Vol. 23, No. 4 (1952), pp. 493--507], 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$.

| cite | improve this answer | |
  • $\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$ You are right, it works for all x. Thx! $\endgroup$ – Wuchen Jun 30 '16 at 0:18
  • $\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

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.