Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 . Thanks in advance

share|improve this question
Have you tried truncating the random variables? – charles.y.zheng May 26 '11 at 19:33
I did not use, can you propose me a book or a paper to know how to do this. – Farzad May 26 '11 at 19:46
@Farzad, if you do not get answers here try math.SE or Why do you have sum of product of normal variable, is there a special reason? Also can you elaborate more on what tightness of the bound means? – mpiktas May 26 '11 at 20:06
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. – shabbychef May 26 '11 at 22:05
@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. – cardinal Nov 11 '11 at 1:32

There is a new book on probability inequalities you could take a look at.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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