# Sum of Independent Exponential Random Variables

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 ?

• just follow the proof of chernoff: it's easy to bound the exponential moment of exponential random variables. – Sasho Nikolov Jun 29 '13 at 2:27
• 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 Jun 29 '13 at 4:33
• Check Lemma 2.8 here eprint.iacr.org/2010/076.pdf – Sasho Nikolov Jun 29 '13 at 14:49
• 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 Jun 29 '13 at 15:58
• @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 Jul 2 '13 at 16:58

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.

• 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 Jul 2 '13 at 20:15
• 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 Jul 3 '13 at 2:38
• 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 Jul 3 '13 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.

• 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 Aug 16 '17 at 17:42
• @Warren Schudy, what would be your approach? – Thomas Ahle Aug 16 '17 at 17:47
• 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. – Warren Schudy Aug 16 '17 at 17:50
• @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 Sep 2 '17 at 20:31
• 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 Sep 4 '17 at 17:00