Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

The multiplicative Chernoff Bound says for $X_i \in \{0,1\}$ that satisfies $\mathbb{E}[X_i] = p$,
$$ \mathbb P\left(\sum\limits_i^n{X_i} \geq np(1+\delta)\right) \leq e^{-\frac{1}{3} np\delta^2} \>. $$

The additive version says that $$ \mathbb P\left(\sum\limits_{i}^nX_i \geq np+n\epsilon \right) \leq e^{-2n\epsilon^2} \>. $$

I wonder if the multiplicative version could be stronger. Let $\epsilon = p \delta$, then the additive Chernoff bound is reduced to $$ \mathbb P\left(\sum\limits_{i}^{n}{X_i} \geq np(1+\delta)\right) \leq e^{-2np^2\delta^2} \>. $$ This is a much weaker bound when $p \ll 1$.

How can these two versions of Chernoff bounds have such a difference? I mean, which step in deriving these two bounds diverges, causing the fact I have illustrated?

share|cite|improve this question
up vote 1 down vote accepted

No version is stronger than the other. Look at the proofs of both statements and you'll notice (e.g. that one case uses $1+x\lt e^x$ while the other does not. This explains the divergence you mention.

share|cite|improve this answer

The addictive one is stronger than the multiplicative one, since the multiplicative one can be derived from the addictive one.You should see the derivation in this material‎ . The multiplicative one emerge as a corollary of the addictive one.

share|cite|improve this answer

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.