# Wellner Inequality

Working on an exercise from Shorack's Probability for Statisticians, Ex 4.6 (Wellner):

Suppose $T \simeq$ Binomial$(n,p)$. Then use the inequality $$\mu(|X| \ge \lambda) \le \frac{\textrm{E}g(X)}{g(\lambda)} \quad \textrm{for all } \lambda > 0$$ with $g(x) = e^{rx}$ and $r >0$, to show that $$P(\frac{T}{n} \ge p\epsilon) \le e^{-np\cdot h(\epsilon)}$$ where $h(\epsilon) \equiv \epsilon(\log(\epsilon)-1)+1)$.

Using binomial theorem, I can show that $$\textrm{E}g(T) = \sum_{t=0}^n e^{rt} {{n}\choose{t}} p^t (1-p)^{n-t} = (e^rp + 1-p)^n.$$ Using $\lambda = np\epsilon$, I therefore have: $$P(T\ge np\epsilon) \le \exp(n\log(e^rp+1-p) - np\epsilon)$$ and only need to prove that $$n\log(e^rp+1-p) - np\epsilon \le -np (\epsilon(\log(\epsilon) -1) +1)$$

However, I've written code in R to verify this inequality with actual values for $r$, $p$, and $\epsilon$ but it's not always true.

Can anybody give me tips or perhaps an alternative way to do this?

-
This kind of result is commonly needed in information theory and communication theory. I do not know the Wellner Inequality, but a common way of approaching questions like this is to use the Chernoff bound, a simple version of which says that for all $\lambda$, $$P\{X \geq a\} \leq E[\exp(\lambda(X-a))] = \exp(-\lambda a)M(\lambda)$$ where $M(\lambda)$ is the moment-generating function of $X$. Look at Chapter 2 of Principles of Communication Engineering by Wozencraft and Jacobs (Wiley 1964) to see how to get to bounds of the form you seek. –  Dilip Sarwate Oct 1 '12 at 15:26
@DilipSarwate Thank you very much! Will look into that. :) –  RVC Oct 1 '12 at 23:36

First of all, thanks to @DilipSarwate for the tip on Chernoff bounds. They key turns out to be $1+x \le e^x$ (proof below). Use this to show $$\textrm{E}g(T) = (1 + p(e^r-1))^n \le e^{p(e^r-1)n}$$ Therefore, $$P(T\ge np\epsilon) \le ( \frac{e^{e^r-1}}{e^{r\epsilon}} )^{np}$$ Use $r =\ln \epsilon$ to get $$P(T\ge np\epsilon) \le ( \frac{e^{\epsilon-1}}{\epsilon^{\epsilon}} )^{np}$$ Then apply exponents and logs to arrive at the result.
To prove $1+x \le e^x$, use Taylor series for $e^x = \sum_{n=0}^\infty \frac{x^n}{n!} = 1 + x + \frac{x^2}{2}+\ldots \ge 1 + x$.