Sum of Independent Exponential Random Variables

Question

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 ?

Answer 1

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.

Answer 2

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.