# Chernoff inequalities for the sum of Exponential RVs

These two well-known Chernoff bounds for the sum of RVs $X=\sum_{k=1}^{n}X_k$ in mulitplicative form,

$\mathbf{P}(X \leq (1- \delta)\mathbf{E}X) \leq e^{-\frac{\delta^2 \mathbf{E}X}{2}}\\ \mathbf{P}(X \geq (1+ \delta)\mathbf{E}X) \leq \big(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}} \big)^{\mu}$

apply in the case when $X_k$ take values 0 and 1. I'm wondering if and how these results can extend in a more general case, e.g. when $X_k$ are exponentially distributed iid.

-
Yes, start from the same exponential inequality and optimize over $t$. –  Did Sep 13 '12 at 5:21
Thanks, could you give more details or explain this approach? –  Alex Sep 13 '12 at 5:52
Show what you tried in this direction (the beginning merely copies the approach in the Bernoulli case explained on the WP page) and we will talk. –  Did Sep 13 '12 at 7:52
If $\mathbf{E} X_k = \frac{1}{\mu}$, then $\mathbf{E}X= \frac{n}{\mu}$ and MGF of X is $\varphi_{X}(t) = \bigg(\frac{\mu}{\mu-t} \bigg)^{n}$, so te upper bound using Markov inequality is $\mathbf{P}(X>(1+\delta)\mathbf{E}X) < \bigg(\frac{\mu}{\mu-t} \bigg)^{n}e^{-t(1+\delta)\mathbf{E}X}$, but I do not understand the whole optimization part. –  Alex Sep 14 '12 at 5:17

As explained by the OP in a comment, Markov inequality yields $$P(X\gt(1+\delta)n/\mu)\leqslant \exp(-nI(t/\mu,\delta)),$$ for every $t\gt0$, where $$I(s,\delta)=s(1+\delta)+\log(1-s).$$ The derivative is $\partial_sI(s,\delta)=1+\delta-1/(1-s)$ hence the optimal choice is $s_\delta=\delta/(1+\delta)$, which yields $I(s_\delta,\delta)=\delta-\log(1+\delta)$, and finally, $$P(X\gt(1+\delta)n/\mu)\leqslant\left(\frac{1+\delta}{\mathrm e^\delta}\right)^n.$$ To sum up, Markov (exponential) inequality yields a family of upper bounds, indexed by $t$ (or by $s$), and one chooses the value of $s$ (or of $t$) which minimizes this upper bound.
Thanks my only concern is that $\frac{\partial^2 I}{\partial s^2} = -\frac{1}{(1-s)^2}$, so $s_{\delta}$ is the maximum point when we want this point to be a minimum. What's wrong with this logic? –  Alex Sep 15 '12 at 2:34
The upper bound is $\exp(-nI)$, with a minus sign, hence the most powerful upper bound is when $I$ is maximum. Let me suggest to draw the graph of $s\mapsto I(s,\delta)$. –  Did Sep 15 '12 at 4:29
That's nice.  –  Did Sep 16 '12 at 12:09