$S \sim Binomial(n, p)$. $\forall a > p$, find large deviation bound for $P( S \geq an)$
In the book, the large deviation bound definition is as follows:
$\phi(t)$ is finite for some $t > 0$, $\forall a > \mu$, $P(S_n \geq an) \leq e^{-nI(a)}$, where $I(a) = sup\left \{at – log \phi(t): t > 0\right \} > 0$
My attempt at solving the problem:
$P( S\geq an)$
$= P(e^{tS} \geq e^{tan})$
$ \leq \frac{E(e^{tS})}{e^{tan}}$ (by Markov inequality)
$= \frac{e^{n log\phi_x(t))}}{e^{tan}}$
$= e^{[-n(at – log \phi_x(t)]}$
I know that $I(a) = sup\left \{at – log \phi_x(t): t > 0\right \} > 0$, and the answer key says that $I(a) = a log \frac{a}{p} + (1-a) log \frac{1-a}{1-p}$, but I have no idea how it arrived at that. I think I have to do something with the bernoulli mgf?
Best Answer
We just have to maximize $f(t)=at-\log \phi_x(t)$ where $\phi_x(t)=1+p(e^t-1)=q+pe^t$ where $q=1-p$.
One possible way is to use calculus to maximize $f(t)=at-\log (q+pe^t)$.
We know that the function is concave. Hence it suffices to differentiate it and equate it to zero, we have
$$a-{pe^t}/({q+pe^t})=0$$
or equivalently $$a-\left(1+\frac{q}{p}e^{-t}\right)^{-1}=0,$$
$$1+\frac{q}{p}e^{-t}=\frac{1}{a},$$
$$e^t=\frac{a}{1-a}\frac{q}{p}.$$ and $$t=\log\left(\frac{a}{p}\right)-\log\left(\frac{1-a}{q}\right)$$
Hence
\begin{align*} I(a)&=a\log\left(\frac{a}{p}\right)-a\log\left(\frac{1-a}{q}\right)-\log \left( q+p\frac{a}{1-a}\frac{q}{p}\right)\\ &=a\log\left(\frac{a}{p}\right)-a\log\left(\frac{1-a}{q}\right)-\log \left( \frac{q}{1-a}\right)\\ &=a\log\left(\frac{a}{p}\right)-a\log\left(\frac{1-a}{q}\right)+\log \left( \frac{1-a}{q}\right) \\ &= a\log\left(\frac{a}{p}\right)+(1-a)\log\left(\frac{1-a}{q}\right)\\ &= a\log\left(\frac{a}{p}\right)+(1-a)\log\left(\frac{1-a}{1-p}\right) \end{align*}