2
$\begingroup$

I am reading the proof of Chernoff bound ,there's one step here : $$\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\leq e^{-\delta^2/3}$$ where $0<\delta<1$

the book prove that by using the second order dervative analysis of

$$f(\delta)=\delta -(1+\delta)log(1+\delta)+\frac{\delta^2}{3}$$

but how to see this upper bound for$\frac{e^{\delta}}{(1+\delta)^{1+\delta}}$ or is there any straight inequality manipulation to get there?

$\endgroup$
  • 1
    $\begingroup$ The inequality is false for $\delta=2$. Do you have a restricted range of $\delta$ in mind? $\endgroup$ – Greg Martin Sep 8 '18 at 0:45
  • $\begingroup$ @GregMartin thank you are right , I already fixed it $\endgroup$ – ShaoyuPei Sep 8 '18 at 0:47
1
$\begingroup$

Instead of comparing $$\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\leq e^{-\delta^2/3}$$ take logarithms and prove that $$\delta -(1+\delta ) \log (1+\delta ) < -\frac{\delta^2}3$$ Expanded as series built around $\delta=0$, the lhs is $$-\frac{\delta ^2}{2}+\frac{\delta ^3}{6}-\frac{\delta ^4}{12}+O\left(\delta ^5\right)$$ Now, use the fact that $\delta<1$ making $$-\frac{\delta ^2}{2}+\frac{\delta ^3}{6} \le -\frac{\delta ^2}{2}+\frac{\delta ^2}{6}=-\frac{\delta ^2}{3}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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