Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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