2
$\begingroup$

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.

$\endgroup$
4
  • 5
    $\begingroup$ Why don't you ask your advisor? $\endgroup$
    – GH from MO
    Commented May 24 at 5:31
  • $\begingroup$ @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. $\endgroup$
    – HDD
    Commented May 24 at 5:35
  • 7
    $\begingroup$ I suggest that you switch advisor then. You don't want to be in an abusive relationship. $\endgroup$
    – GH from MO
    Commented May 24 at 5:38
  • 3
    $\begingroup$ Imagine getting angry at someone over bounds… $\endgroup$
    – Nate River
    Commented May 24 at 6:55

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ One little question, you derived it from multiplicative Chernoff but it's also true additive? $\endgroup$
    – HDD
    Commented May 24 at 6:09
  • 2
    $\begingroup$ @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. $\endgroup$
    – GH from MO
    Commented May 24 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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