Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - e^{-x/\lambda_i}$. Let $Z = \sum X_i$. Can we prove bounds of the form $Pr(|Z-\mu_Z|>t) < e^{-t^2/\sum (\lambda_i)^2}$. This follows directly if we use the variance form of chernoff bounds and hence I believe is true , but the bounds that I read require bounded-ness or have some dependence on bounded-ness of the variables. Could someone point to me to a proof of the above ?

  • $\begingroup$ just follow the proof of chernoff: it's easy to bound the exponential moment of exponential random variables. $\endgroup$ Commented Jun 29, 2013 at 2:27
  • $\begingroup$ I have tried to repeat the proof of chernoff. I did it for the simpler case when all $\lambda_i = \lambda$. I can get the kind of relation that I am looking for under a mild condition of $t < n\lambda$. Does such a condition arise naturally or is it due to my not so good solution ? $\endgroup$
    – NAg
    Commented Jun 29, 2013 at 4:33
  • 3
    $\begingroup$ Check Lemma 2.8 here eprint.iacr.org/2010/076.pdf $\endgroup$ Commented Jun 29, 2013 at 14:49
  • $\begingroup$ Yes this makes sense. Even in their lemma they have a condition on $t$ being small enough. Okay then my solution seems correct. Thanks a lot for the links and the suggestion. $\endgroup$
    – NAg
    Commented Jun 29, 2013 at 15:58
  • 1
    $\begingroup$ @SureshVenkat done. NAg, I think there are are some typos in your question. First, $\Pr[X_i < x] = e^{-\lambda_i x}$ is a very odd CDF for positive $x$. Did you mean $\Pr[X_i < x] = 1-e^{-\lambda_i x}$? If you did, then the variance is of the form $\lambda_i^{-2}$ and your chernoff bound does not look quite right. $\endgroup$ Commented Jul 2, 2013 at 16:58

2 Answers 2


For concreteness, say that the pdf of the r.v. $X_i$ is

$$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$$

This is the Laplace distribution, or the double exponential distribution. Its variance is $\frac{2}{\lambda_i^2}$. The cdf is

$$ \Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x} $$ for $x \geq 0$.

The moment generating function of $X_i$ is

$$ \mathbf{E}\ e^{uX_i} = \frac{1}{1 - u^2/\lambda_i^2}, $$ for $|u| < \lambda_i$. Using this fact and the exponential moment method which is standard in the proof of Chernoff bounds, you get that for $X = \sum_i X_i$ and $\sigma^2 = 2\sum_i \lambda_i^{-2}$, the following inequality holds

$$ \Pr[X > t\sigma] < e^{-t^2/4}, $$ as long as $t \leq 2\sigma \min_{i}{\lambda_i}$. You can find a detailed derivation in the proof of Lemma 2.8 of this paper.

  • $\begingroup$ Thanks a lot for the answer. However in my application it is not necessaily true that $t \leq \sqrt{2} \sigma min_i \lambda _i$. However one would expect even stronger concentration in case $t > \sqrt{2} \sigma min_i \lambda _i$. We can get such a result if we dont use the approximation of $1/(1-x) \leq e^{cx}$ which restricts the range of $t$ in the proof but the analysis of that becomes unmanageable in the case of different $\lambda _i 's$. Any suggestions on that front ? $\endgroup$
    – NAg
    Commented Jul 2, 2013 at 20:15
  • $\begingroup$ this is going to be some vigorous hand-waving, but I expect that such large values of $X$ are most likely to happen when only a small number of $X_i$ exceed the median of $|X_i|$ by a lot. but double exponential variables have a heavier tail than gaussians, and a small number of them cannot concentrate that tightly $\endgroup$ Commented Jul 3, 2013 at 2:38
  • 2
    $\begingroup$ I am realizing what I wrote above is not clear: I expect that way out in the tail $X$ looks like the tail of another r.v. $X'$ which is the sum of a small number of double exponential r.v. The tail of such $X'$ should not be sub-gaussian. $\endgroup$ Commented Jul 3, 2013 at 4:58

For the Laplace distribution, if you use the Bernoulli bound you can write

$$Ee^{u\sum_i X_i} = \prod_i \frac1{1-u^2/\lambda_i^2} \le \frac1{1-u^2\sigma^2/2},$$ where $\sigma^2=2\sum_i\lambda_i^{-2}$. Then the classical Chernoff method to gives

$$\Pr[\sum_i X_i \ge t\sigma]\le \tfrac{1+\sqrt{1+2t^2}}{2} e^{1-\sqrt{1+2t^2}} \le\cases{ (et/\sqrt2+1) e^{-\sqrt{2}t} \\ e^{-t^2/2 + t^4/8}} .$$

Note that these bounds hold for unrestricted values of $t$ and $\lambda_i$. The bounds on the right show the two possible regimes. For small values of $t$ we get `normal' concentration $e^{-t^2/2}$, while for large values of $t$ we get $\approx e^{-\sqrt{2}t}$, which is also the CDF for a single Laplace distributed variable.

The $1-\sqrt{1+2t^2}$ bound allows you to interpolate between the two situations, but I suspect that in nearly all cases one will be firmly in either the large $t$ or the small $t$ camp.

For the exponential distribution the same techniques give us $Ee^{u\sum_iX_i}\le\frac{1}{1-u\mu}$ where $\mu=\sum_i 1/\lambda_i$. Hence $$\Pr[(\sum_i X_i)-\mu \ge t\mu]\le (t+1) e^{-t} \le e^{-t^2/2+t^3/3}.$$ So you still get something slightly normal looking, but with $t\mu$ rather than $t\sigma$ as we might have hoped for. I don't know if it is possible to get a bound in terms of the variance. You could try to study $Ee^{u(\sum X_i-\mu)^2}$, but it doesn't seem to be easy to work with.

  • $\begingroup$ I don't have the time to work out the details but I'm 99.9% sure that one can get a bound for exponentially distributed random variables that depends on the variance. Your bound on the moment generating function looks excessively loose. $\endgroup$ Commented Aug 16, 2017 at 17:42
  • $\begingroup$ @Warren Schudy, what would be your approach? $\endgroup$ Commented Aug 16, 2017 at 17:47
  • $\begingroup$ Two obvious approaches I see: 1. The second bound listed at en.wikipedia.org/wiki/… looks like it should work. 2. Find a tighter bound on the moment generating function. $\endgroup$ Commented Aug 16, 2017 at 17:50
  • $\begingroup$ @WarrenSchudy The Bernstein bound gives $\Pr[\sum_iX_i\ge t\sigma]\le e^{-t^2/2}$, but only for $t\le\sigma\min_i\lambda_i/2$. I suppose this is similar to Sasho's answer. $\endgroup$ Commented Sep 2, 2017 at 20:31
  • $\begingroup$ It's inevitable that Gaussian-style bounds will stop at some point. Even a single exponentially distributed random variable eventually has fatter tails than any Gaussian. $\endgroup$ Commented Sep 4, 2017 at 17: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.