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.

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?

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

1 Answer 1

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$.

share|improve this answer
add comment

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.