4
$\begingroup$

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

$\endgroup$
3
  • $\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$ Jun 29, 2016 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, 2016 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$ Jun 29, 2016 at 16:16

1 Answer 1

3
$\begingroup$

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

$\endgroup$
5
  • $\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, 2016 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$ Jun 29, 2016 at 23:42
  • $\begingroup$ You are right, it works for all x. Thx! $\endgroup$
    – Wuchen
    Jun 30, 2016 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, 2016 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$ Jun 30, 2016 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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