12
$\begingroup$

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 ?

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

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.

$\endgroup$
  • $\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 Jul 2 '13 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$ – Sasho Nikolov Jul 3 '13 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$ – Sasho Nikolov Jul 3 '13 at 4:58
3
$\begingroup$

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.

$\endgroup$
  • $\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$ – Warren Schudy Aug 16 '17 at 17:42
  • $\begingroup$ @Warren Schudy, what would be your approach? $\endgroup$ – Thomas Ahle Aug 16 '17 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$ – Warren Schudy Aug 16 '17 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$ – Thomas Ahle Sep 2 '17 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$ – Warren Schudy Sep 4 '17 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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