The additive Chernoff Bound says for $$X_i \in \{0,1\}$$ that satisfies $$\mathbb{E}[X_i] = p,$$ $$\mathbb P\left(\sum_{i=1}^nX_i \geq np+n\epsilon \right) \leq \exp\left(-\frac{(n\epsilon)^2}{2(np+\frac{n\epsilon}{3})}\right) .$$ This inequality given by my advisor. I don't understand what kind of additive chernoff? I don't see anywhere in the Wikipedia.

I know only this, the additive version says that $$\mathbb P\left(\sum_{i=1}^nX_i \geq np+n\epsilon \right) \leq e^{-2n\epsilon^2}.$$

Anybody help me how to get my advisor chernoff version.

• @GHfromMO he is very angry, we don't have audacity to ask. One thing I notice that it looks like Bernstein's inequality, but there's no $np$ term.
– HDD
Commented May 24 at 5:35
• I suggest that you switch advisor then. You don't want to be in an abusive relationship. Commented May 24 at 5:38
• Imagine getting angry at someone over bounds… Commented May 24 at 6:55

The multiplicative Chernoff bound (as given here) tells us that $$\mathbb P\left(\sum_{i=1}^nX_i \geq np+n\epsilon \right) \leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu,$$ where $$\mu:=np$$ and $$\delta:=\epsilon/p$$. We shall prove below that $$\frac{e^\delta}{(1+\delta)^{1+\delta}}\leq \exp\left(-\frac{\delta^2}{2\left(1+\frac{\delta}{3}\right)}\right).\tag{\ast}$$ This yields the required bound, because $$\frac{\delta^2\mu}{2\left(1+\frac{\delta}{3}\right)}=\frac{(n\epsilon)^2}{2(np+\frac{n\epsilon}{3})}.$$
Finally, we prove $$(\ast)$$. Taking the logarithm on both sides, we get the equivalent form $$f(\delta):=\frac{\delta^2}{2\left(1+\frac{\delta}{3}\right)}+\delta-(1+\delta)\log(1+\delta)\leq 0.$$ Now $$f(0)=f'(0)=0$$, hence it suffices to show that $$f''(\delta)\leq 0$$ for all $$\delta\geq 0$$. However, $$f''(\delta)=-\frac{\delta^2(9+\delta)}{(1+\delta)(3+\delta)^3}\leq 0,\qquad\delta\geq 0,$$ and we are done.
Remark. In $$(\ast)$$ the denominator $$3$$ cannot be increased.
• @David The words "multiplicative" and "additive" are just convenient labels, they are not part of the mathematics. What is important is that the inequality is true, and I provided the proof. I have now explained $(\ast)$ in detail as well. Commented May 24 at 6:29