2
$\begingroup$

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?

  • 0
    @DilipSarwate Thank you very $m$uch! Will look into that. :)2012-10-01

1 Answers 1

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