7
$\begingroup$

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?

  • 0
    I am concerned with how to get the lower bound.2012-03-01

2 Answers 2

2

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.

1

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.