Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

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. http://en.wikipedia.org/wiki/Chernoff_bound) that one case uses $1+x\lt e^x$ while the other does not. This explains the divergence you mention.

share|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 www.cs.berkeley.edu/~sinclair/cs271/n13.pdf‎ . The multiplicative one emerge as a corollary of the addictive one.

share|improve this answer

Your Answer

 
discard

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.