7
$\begingroup$

I'm interested in obtaining upper bounds on $$ \Pr[\prod_{i\in[n]}|G_i| > x] $$ where $G_i\sim\mathcal{N}(0,1)$ i.i.d, and $[n] := \{0,1,\dots,n-1\}$.

The most naive bound is to note that each $G_i$ satisfies $\Pr[|G_i| > t] \leq 2\exp(-t^2/2)$. It is simple to check that for $t\geq\sqrt{2\ln(2/\delta)}$ this implies that $\Pr[|G_i| > t] \leq \delta$. So, for each $G_i$, we can condition on the event that $|G_i| < \sqrt{2\ln(2n/\delta)}$ to get that

$$ \Pr[\prod_{i\in[n]}|G_i| > \sqrt{2\ln(2n/\delta)}^{n}] \leq \delta. $$ One can mildly improve this by instead conditioning on the event that $\max(G_i) > t$ (I can reduce $2n\mapsto n$, using for example this), but the general bound you get is of the above form. Other bounds (say using the formalism of sub-Weibull random variables, an extension of sub-Gaussian random variables that satisfies a notion of closure under multiplication) I get are substantially similar.

My issue is that the above appears to be very loose. The most obvious way to show this is to set some number of trials $k$, then

  1. samples $n$ random variables $G_i$ i.i.d., and
  2. set $\vec v_i = \prod_{i\in[n]} \frac{|G_i|}{\sqrt{2\ln(2n/\delta)}}$, then
  3. record in what fraction of the trials $k$ $|\vec v_i|>1$, e.g. the tail-bound is violated. Also record the closest we get, e.g. $\lVert \vec v\rVert_\infty$. This is the minimal value that (post-hoc, for all of our trials) we observed that $\prod_i|G_i| > \lVert \vec v\rVert_\infty \sqrt{2\ln(2n/\delta)}^n$.

My issue is that I never see violations of my bound, and $\lVert \vec v\rVert_\infty$ is extremely small. As an example, for $n = 10^3, \delta = 10^{-3}, k = 10^3$, I see no violations of the bound. Moreover, I get that $\lVert \vec v\rVert_\infty \approx 10^{-948}$. So, my bound is hopelessly loose.

The issue seems to be in that my approach, I am solely bounding the probability that "bad" events happen. In truth, there are many "good" events (say the event that $|G_i| \leq 1/2$) that likely accumulate, as these good events are very likely to occur. These good events may (very quickly) shrink the total size of the product.

Do there exist tight bounds on this quantity? I would prefer quantitative bounds, e.g. with all constants explicit.

Edit:

For the suggestion of Chernoff-Cramer type bounds, one can compute that

  1. the pdf of $Y = \ln|G_i|$ is $\sqrt{\frac{2}{\pi}}\exp(x)\exp(-\exp(2x)/2)$.

  2. the mgf $Y$ is $\mathbb{E}[\exp(tY)] = \sqrt{\frac{2}{\pi}}\int_{-\infty}^\infty \exp(tx)\exp(x)\exp(-\exp(2x)/2)\mathrm{d}x$. One can check that this $\mathbb{E}[|G_i|^\lambda] = \sqrt{\frac{2^\lambda}{\pi}}\Gamma(\frac{\lambda+1}{2})$

  3. I will let $\mu : \mathbb{E}[Y] = -\frac{\gamma+\ln 2}{2}\approx -.63$, where $\gamma$ is the Euler-Mascheroni constant.

  4. The Chernoff-Cramer-Bernstein-Bennett-etc method then gives that

\begin{align} \Pr[\prod_{i\in[n]}|G_i|>x]&=\Pr[\sum_{i\in[n]}\ln|G_i|-\mu>\ln(x)-n\mu]\\ &=\min_{\lambda>0}\Pr[\exp(\sum_{i\in[n]}\lambda\ln|G_i|-\mu)>\exp(\lambda(\ln(x)-n\mu))]\\ &\leq\min_{\lambda>0}\exp(n\mu\lambda)\frac{\mathbb{E}[\prod_{i\in[n]}\exp(\lambda (\ln |G_i|-\mu))]}{x^\lambda}\\ &=\min_{\lambda>0}x^{-\lambda}\mathbb{E}[\exp(\lambda \ln |G_i|)]^n\\ &=\min_{\lambda>0}x^{-\lambda}\sqrt{2^\lambda/\pi}\Gamma(\frac{\lambda+1}{2}). \end{align}

Using Stirling's approximation for the Gamma function

$$ \ln\Gamma(z) \approx z\ln z - z + \frac{1}{2}\ln\frac{2\pi}{z} $$

I get an upper bound

$$ \min_{\lambda>0}x^{-\lambda}\sqrt{\frac{2^\lambda}{\pi}}\left(\frac{1+\lambda}{2}\ln\frac{1+\lambda}{2}-\frac{1+\lambda}{2}+\frac{1}{2}\ln\frac{4\pi}{1+\lambda}\right) $$ I can compute that this has a critical point when

$$ -\ln x + \ln\sqrt{2} + \frac{1}{2}\ln\frac{1+\lambda}{2}-\frac{1}{2}\frac{1}{1+\lambda} = 0 $$

I don't know how to solve an equation of this type for $\lambda$ though.

$\endgroup$
1
  • 1
    $\begingroup$ Stirling's approximation isn't good for small values, which is where we're working. For example, when I use your formula with $x=0.1$ I get a very negative minimum near $\lambda= 2.25$. Using the formula with $\Gamma$ in it I find that for $x<0.5$, the minimum seems to be at $\lambda\approx 0$ $\endgroup$ Commented Jun 13 at 7:51

1 Answer 1

6
$\begingroup$

Consider $H=\log |G|$. The upper tail of $H$ is well-behaved, and in simulation it seems to have mean of $H$ of about $\mu=-0.63$ and a finite standard deviation around $\sigma\approx 1.11$.

So $$P\left(\sum_iH_i> -0.63n+K\times 1.11\sqrt{n}\right)$$ will be small for large $n$ and moderate $K$, with dependence on $K$ controlled by the upper tail of $H$ (using Markov/Chebyshev/Chernoff/Bernstein-type inequalities). This means $$P\left(\prod_i G_i> \exp(-0.63n+K \times 1.11\sqrt{n})\right)$$ is similarly well-controlled.

In simulation, if I define

b<-function(n) exp(-0.63*n+1.11*sqrt(n))

then (for $K=1$ and modest $n$)

> r<-replicate(10000,prod(abs(rnorm(10))))
> mean(r>b(10))
[1] 0.148
> r<-replicate(10000,prod(abs(rnorm(20))))
> mean(r>b(20))
[1] 0.1531
> r<-replicate(100000,prod(abs(rnorm(30))))
> b(30)
[1] 2.705349e-06
> mean(r>b(30))
[1] 0.15193
> b(40)
[1] 1.272441e-08
> r<-replicate(100000,prod(abs(rnorm(40))))
> mean(r>b(40))
[1] 0.15195

It looks as if bounds from this approach may be reasonably sharp. I'm not going to actually work out the inverse upper tail of $H$, but it seems like that should be feasible.

(This approach will only be useful for bounds on the upper tail.)

$\endgroup$
3
  • 6
    $\begingroup$ +1 Since $H=\frac12 \log(G^2)$ would have an expgamma distribution, I believe the mean should be $\frac12 \left(\psi(\frac12)-\log(\frac12) \right)\approx -0.63518$ and standard deviation $\frac{\pi}{\sqrt{8}}\approx 1.11072$ (or see here), agreeing with your results. This distributional information might be of some help if someone want to play with tail calculation, perhaps. $\endgroup$
    – Glen_b
    Commented Jun 13 at 1:53
  • 1
    $\begingroup$ I thought someone was bound to know the PDF or CDF or something! $\endgroup$ Commented Jun 13 at 1:57
  • 1
    $\begingroup$ It has a couple of other names here and there. For a number of things it's not too bad to play with algebraically, even for my fairly pedestrian skills. The log of a gamma random variable tends to come up now and then with my work. $\endgroup$
    – Glen_b
    Commented Jun 13 at 2:03

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.