# Bennett's Inequality to Bernstein's Inequality

Bennett's Inequality is stated with a rather unintuitive function,

$$h(u) = (1+u) \log(1+u) - u$$

See here. I have seen in multiple places that Bernstein's Inequality, while slightly weaker, can be obtained by bounding $h(u)$ from below,

$$h(u) \ge \frac{ u^2 }{ 2 + \frac{2}{3} u}$$

and plugging it back into Bennett's Inequality. However, I can't see where this expression comes from. Could someone point me in the right direction?

-
Have you tried using a Taylor expansion for $\log(1 + u)$? –  TMM Feb 29 '12 at 13:29
Which expression are you asking about? That of $h(u)$ or that of the lower bound for $h(u)$? –  Willie Wong Feb 29 '12 at 13:31
I am concerned with how to get the lower bound. –  duckworthd Mar 1 '12 at 5:40

Here is how the approximation could be derived.

\begin{align} h(u) &=(1+u)\log(1+u)−u\\ &=(1+u)\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}u^n}{n}−u\\ &=\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}u^n}{n} +u\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}u^n}{n}−u\\ &=\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}u^n}{n} +\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}u^{n+1}}{n}−u\\ &=\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}u^n}{n} +\sum_{n=2}^{\infty} \dfrac{(-1)^{n}u^{n}}{n-1}−u\\ &=u+\sum_{n=2}^{\infty} \dfrac{(-1)^{n-1}u^n}{n} +\sum_{n=2}^{\infty} \dfrac{(-1)^{n}u^{n}}{n-1}−u\\ &=\sum_{n=2}^{\infty} u^n\left(\dfrac{(-1)^{n-1}}{n} +\dfrac{(-1)^{n}}{n-1}\right)\\ &=\sum_{n=2}^{\infty} (-1)^{n}u^n\left(\dfrac{-1}{n} +\dfrac{1}{n-1}\right)\\ &=\sum_{n=2}^{\infty} (-1)^{n}u^n\left(\dfrac{1}{(n-1)n}\right)\\ &=\sum_{n=2}^{\infty} \dfrac{(-1)^{n}u^n}{(n-1)n}\\ &= \dfrac{u^2}{2}-\dfrac{u^3}{6}+\dfrac{u^4}{12} -\dfrac{u^5}{20}\pm ...\\ \end{align}

If we just look at the first two terms,

$\dfrac{u^2}{2}-\dfrac{u^3}{6} =\dfrac{u^2}{2}(1-\dfrac{u}{3})$, and since $\dfrac1{1+z} =1-z+z^2 \pm ...$, $1-\dfrac{u}{3} \sim \dfrac1{1+u/3}$.

Therefore $h(u) \sim \dfrac{u^2}{2}\dfrac1{1+u/3} = \dfrac{u^2}{2+2u/3}$.

This shows how the approximation could be derived. The next step is to see how accurate the approximation is. Let $h^*(u) = \dfrac{u^2}{2}\dfrac1{1+u/3} = \dfrac{u^2}{2+2u/3}$.

Expanding the approximation,

\begin{align} h^*(u) &\sim \dfrac{u^2}{2}\dfrac1{1+u/3}\\ &=\dfrac{u^2}{2}(1-\dfrac{u}{3}+\dfrac{u^2}{9} -\dfrac{u^3}{27}\pm ...)\\ &=\dfrac{u^2}{2}-\dfrac{u^3}{6}+\dfrac{u^4}{18} -\dfrac{u^5}{54}\pm ... \\ \end{align}

Therefore

\begin{align} h(u)-h^*(u) &=(\dfrac{u^4}{12} -\dfrac{u^5}{20}\pm ...) -(\dfrac{u^4}{18} -\dfrac{u^5}{54}\pm ...)\\ &=u^4(\dfrac{1}{12}-\dfrac{1}{18}) -u^5(\dfrac{1}{20}-\dfrac{1}{54})\pm ...\\ &=\dfrac{u^4}{36} -\dfrac{17u^5}{540}\pm ... \\ \end{align}

It certainly looks like $h(u) > h^*(u)$. Once you have this conjecture, you can try to prove it. In this case, a proof can be developed by looking at the successive terms in the difference and showing that the terms are decreasing and alternating in sign.

Note that if we let $h^{**}(u) = \dfrac{u^2}{2}-\dfrac{u^3}{6}$, $h(u)-h^{**}(u) =\dfrac{u^4}{12} -\dfrac{u^5}{20}\pm ...$, and this appears to have an error about three times as large.

-

This is more like a comment. Define $f(x)=(1+x) \log(1+x) - x- \frac{ x^2 }{ 2 + \frac{2}{3} x}$. You can see that $f(0)=f'(0)=f''(0)=0$. However $f''(x)$ is ratio of some polynomials and it can be seen that for $x>0$, $f''(x)>0$. Hence $f'(x)>0$ and $f(x)>0$ too.

This is an ugly way to prove it but I do not see another way for the moment.

-