<p>For concreteness, say that the pdf of the r.v. <span class="math-container">$X_i$</span> is </p>

<p><span class="math-container">$$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$$</span> </p>

<p>This is the Laplace distribution, or the double exponential distribution. Its variance is <span class="math-container">$\frac{2}{\lambda_i^2}$</span>. The cdf is</p>

<p><span class="math-container">$$
\Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x}
$$</span>
for <span class="math-container">$x \geq 0$</span>. </p>

<p>The moment generating function of <span class="math-container">$X_i$</span> is </p>

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

<p><span class="math-container">$$
\Pr[X &gt; t\sigma] &lt; e^{-t^2/4},
$$</span>
as long as <span class="math-container">$t \leq 2\sigma \min_{i}{\lambda_i}$</span>. You can find a detailed derivation in the proof of Lemma 2.8 of <a href="http://eprint.iacr.org/2010/076.pdf" rel="nofollow noreferrer">this paper</a>. </p>

CC BY-SA 3.0
2013-07-02T20:15:59.503Z
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 ?
NAg
CC BY-SA 3.0
2013-07-03T02:38:18.950Z
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
Sasho Nikolov
CC BY-SA 3.0
2013-07-03T04:58:29.460Z
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.
Sasho Nikolov
CC BY-SA 4.0
2013-07-02T16:48:40.020Z
2019-11-01T19:13:03.847Z
2019-11-01T19:13:03.847Z
Sasho Nikolov
<p>For the Laplace distribution, if you use the Bernoulli bound you can write</p>

<p>$$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</p>

<p>$$\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}}
.$$</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-08-16T17:42:01.110Z
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.
Warren Schudy
CC BY-SA 3.0
2017-08-16T17:47:29.803Z
@Warren Schudy, what would be your approach?
Thomas Ahle
CC BY-SA 3.0
2017-08-16T17:50:14.440Z
Two obvious approaches I see:

1. The second bound listed at https://en.wikipedia.org/wiki/Bernstein_inequalities_(probability_theory) looks like it should work.

2. Find a tighter bound on the moment generating function.
Warren Schudy
CC BY-SA 3.0
2017-09-02T20:31:39.470Z
@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.
Thomas Ahle
CC BY-SA 3.0
2017-09-04T17:00:13.047Z
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.
Warren Schudy
CC BY-SA 3.0
2017-07-26T18:09:04.593Z
2017-08-16T16:20:12.510Z
2017-08-16T16:20:12.510Z
Thomas Ahle
<p>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 &lt; x) = 1 - e^{-x/\lambda_i}$. Let $Z = \sum X_i$. Can we prove bounds of the form $Pr(|Z-\mu_Z|&gt;t) &lt; 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 ?  </p>

CC BY-SA 3.0
2013-06-29T02:27:56.627Z
just follow the proof of chernoff: it's easy to bound the exponential moment of exponential random variables.
Sasho Nikolov
CC BY-SA 3.0
2013-06-29T04:33:39.490Z
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 ?
NAg
CC BY-SA 3.0
2013-06-29T14:49:50.963Z
Check Lemma 2.8 here http://eprint.iacr.org/2010/076.pdf
Sasho Nikolov
CC BY-SA 3.0
2013-06-29T15:58:21.890Z
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.
NAg
CC BY-SA 3.0
2013-07-02T06:57:13.790Z
@SashoNikolov comment->answer ?
Suresh Venkat
CC BY-SA 3.0
2013-07-02T16:58:04.803Z
@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.
Sasho Nikolov
<pr.probability><randomness><chernoff-bound>
Sum of Independent Exponential Random Variables
NAg
# Sum of Independent Exponential Random Variables

(Asked by: username_0 on 2013-06-28)

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 ?

**Tags:** pr.probability, randomness, chernoff-bound

> **Comments:**
> **username_1**: just follow the proof of chernoff: it's easy to bound the exponential moment of exponential random variables.  
> **username_0**: 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 ?  
> **username_1**: Check Lemma 2.8 here http://eprint.iacr.org/2010/076.pdf  
> **username_0**: 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.  
> **username_2**: @SashoNikolov comment->answer ?  
> **username_1**: @SureshVenkat done. username_0, 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.  

---

## 2 answers

### Answer by username_1 on 2013-07-02. Score: 7 | Accepted answer

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](http://eprint.iacr.org/2010/076.pdf).

> **Comments:**
> **username_0**: 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 ?  
> **username_1**: 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  
> **username_1**: 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.  

---

### Answer by username_3 on 2017-07-26. Score: 3

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.

> **Comments:**
> **username_4**: 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.  
> **username_3**: @username_4, what would be your approach?  
> **username_4**: Two obvious approaches I see:  1. The second bound listed at https://en.wikipedia.org/wiki/Bernstein_inequalities_(probability_theory) looks like it should work.  2. Find a tighter bound on the moment generating function.  
> **username_3**: @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.  
> **username_4**: 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.  

---

