I am looking for some probability inequalities for sums of unbounded random variables. I would really appreciate it if anyone can provide me some thoughts.

My problem is to find an exponential upper bound over the probability that the sum of unbounded i.i.d. random variables, which are in fact the multiplication of two i.i.d. Gaussian, exceeds some certain value, i.e., $\mathrm{Pr}[ X \geq \epsilon\sigma^2 N] \leq \exp(?)$, where $X = \sum_{i=1}^{N} w_iv_i$, $w_i$ and $v_i$ are generated i.i.d. from $\mathcal{N}(0, \sigma)$.

I tried to use the Chernoff bound using moment generating function (MGF), the derived bound is given by:

$\begin{eqnarray} \mathrm{Pr}[ X \geq \epsilon\sigma^2 N] &\leq& \min\limits_s \exp(-s\epsilon\sigma^2 N)g_X(s) \\ &=& \exp\left(-\frac{N}{2}\left(\sqrt{1+4\epsilon^2} -1 + \log(\sqrt{1+4\epsilon^2}-1) - \log(2\epsilon^2)\right)\right) \end{eqnarray}$

where $g_X(s) = \left(\frac{1}{1-\sigma^4 s^2}\right)^{\frac{N}{2}}$ is the MGF of $X$. But the bound is not so tight. The main issue in my problem is that the random variables are unbounded, and unfortunately I can not use the bound of Hoeffding inequality.

I will be to happy if you help me find some tight exponential bound.

  • 3
    $\begingroup$ Sounds like a compressed-sensing related problem. Look up R. Vershynin's notes on nonasymptotic random matrix theory, specifically the bounds on what he calls subexponential random variables. That'll get you started. If you need more pointers, let us know and I'll try to post some more info. $\endgroup$ – cardinal May 26 '11 at 20:14
  • 1
    $\begingroup$ There are at least a couple related questions and answers on this topic on math.SE (disclaimer: including one I participated in). $\endgroup$ – cardinal May 26 '11 at 20:16
  • 1
    $\begingroup$ The product $w_i v_i$ has as a 'normal product' distribution. I believe the the mean of this product is zero and the variance is $\sigma^4$ where $\sigma^2$ is the variance of $w_i$ and $v_i$. For $N$ largeish, you could use the central limit theorem to get approximate norality of $X$. If you can compute the skew of the normal product distribution, I believe you can apply the Berry-Esseen theorem to bound the rate of convergence of the CDF. $\endgroup$ – shabbychef May 26 '11 at 22:05
  • 1
    $\begingroup$ @shabbychef, Berry-Esseen has pretty slow convergence, since it's a uniform bound over the class of all distribution functions $F$. $\endgroup$ – cardinal May 26 '11 at 23:30
  • 4
    $\begingroup$ @DilipSarwate: Sorry that I am just now seeing your comment from awhile ago. I think you might be interested in the following little paper, which I've linked to a couple of times on math.SE as well: T. K. Phillips and R. Nelson (1995), The moment bound is tighter than Chernoff's bound for positive tail probabilities, The American Statistician, vol 42, no. 2., 175-178. $\endgroup$ – cardinal Nov 11 '11 at 1:32

Using the Chernoff bound you suggested for some $s\le 1/(2\sigma^2)$ that will be specified later, \[ P[X>t] \le \exp(-st) \exp\Big(-(N/2) \log(1-\sigma^4s^2) \Big) \le \exp(-st + \sigma^4s^2 N) \] where the second inequality holds thanks to $-\log(1-x)\le 2x$ for any $x\in(0,1/2)$. Now take $t=\epsilon \sigma^2 N$ and $s=t/(2\sigma^4N)$, the right hand side becomes $\exp(-t^2/(4\sigma^4N)=\exp(-\epsilon^2 N/4)$ which yields \[ P[X>\epsilon \sigma^2 N] \le \exp(-\epsilon^2 N/4). \] for any $\epsilon\in(0,1)$.

Another avenue is to directly apply concentration inequalities such as the Hanson-Wright inequality, or concentration inequalities for Gaussian chaos of order 2 which encompasses the random variable you are interested in.

Simpler approach without using the moment generating function

Take $\sigma=1$ for simplicity (otherwise, one may rescale by dividing by $\sigma^2$).

Write $v=(v_1,...,v_n)^T$ and $w=(w_1,...,w_n)^T$. You are asking for upper bounds on $P(v^Tw>\epsilon N)$.

Let $Z= w^T v/\|v\|$. Then $Z\sim N(0,1)$ by independence of $v,w$ and $\|v\|^2$ is independent of $Z$ with the $\chi^2$ distribution with $n$ degrees-of-freedom.

By standard bounds on standard normal and $\chi^2$ random variables, $$P(|Z|>\epsilon\sqrt{n/2})\le 2\exp(-\epsilon^2 n/4), \qquad\qquad P(\|v\|>\sqrt{2n}) \le \exp(-n(\sqrt 2 -1)^2/2). $$ Combining with the union bound gives an upper bound on $P(v^Tw>\epsilon N)$ of the form $ 2\exp(-\epsilon^2 n/4) + \exp(-n(\sqrt 2 -1)^2/2)$.

| cite | improve this answer | |

The bound you obtain is of order $e^{-\epsilon}$ as $\epsilon \to \infty$. I don't think you can do much better for general $\epsilon$. From the Wikipedia page on Product Variables the distribution of $w_i v_i$ is $K_0(z)/\pi$ where $K_0$ is a modified Bessel function. From (10.25.3) in the DLMF function list, $K_0(t) \sim e^{-t}/\sqrt{t}$ so that for $x$ sufficiently large $\mathbb{P}(w_i v_i > x) \sim \int_x^\infty e^{-t}/\sqrt{t} dt$ which is not going to give you a sub-Gaussian bound.

| cite | improve this answer | |

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.