Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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
great, thanks, I understand now. – Alex Sep 15 '12 at 4:51
That's nice. $ $ – Did Sep 16 '12 at 12:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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