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?
Best Answer
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.