Question

Let $X$be a binomial random variable with parameters $n$and$p$. Show that, for$i>np$,

$\left(a\right)$the minimum $e^{-ti}E\left[e^{tX}\right]$occurs when $t$is such that$e^t=$$\frac{iq}{(n-i)p}$where$q=1-p.$

$\left(b\right)$$P\{X\ge i\}\le \frac{n^n}{i^2(n-i{)}^{n-i}}{p}^i(1-p{)}^{n-i}$

Short answer

$\left(a\right)$$\frac{d}{dt}\left[e^{-ti}E\left[e^{tX}\right]\right]=0\iff e^t=\frac{iq}{(n-i)p}$

$\left(b\right)$Use Chernoff's bounds and the result obtained in$\left(a\right)$.

Step-by-step solution

Given Information.

Let $X$be a binomial random variable with parameters $n$and$p$.

Explanation.

Let $X$be a binomial random variable with parameters$(n,p)$. In this task, we are going to use Chernoff's bounds. Specifically, it $Y$is a random variable with MGF (the moment generating function), and$i>0,t>0$, then

$P\{Y\ge i\}\le e^{-it}{M}_Y\left(t\right)$

Since $X$is a binomial random variable with parameters $n$&$p$, its MGF is

$M\left(t\right)\stackrel{\text{def}}{=}E\left[e^{tX}\right]={\left[(1-p)+p{e}^t\right]}^n={\left[q+p{e}^t\right]}^n$

Part (a) Explanation.

Let function $f$is defined as$f\left(t\right)=e^{-ti}E\left[e^{tX}\right],t>0$. So, we are looking for a minimum of this function. First, notice that $f\left(t\right)=e^{-ti}M\left(t\right)$and therefore we have:

$f\left(t\right)=e^{-ti}{\left[q+p{e}^t\right]}^n$

The first derivative of the function $f$is

$\frac{df}{dt}=\underset{>0}{\underbrace{e^{-it}{\left[q+p{e}^t\right]}^{n-1}}}\left[(n-i)p{e}^t-iq\right]$

Therefore we have:

$\frac{df}{dt}=0\iff (n-i)p{e}^t-iq=0\iff e^t=\frac{iq}{(n-i)p}$

It is given that$i>np$.

Therefore we have:

$\frac{df}{dt}=0\iff (n-i)p{e}^t-iq=0\iff e^t=\frac{iq}{(n-i)p}$

It is given that$i>np$. Notice that

$i>np\iff e^t>1.$

Part (b) Explanation.

Using Chernoff's bounds and the result we obtained in$\left(a\right)$, we get:

$$\begin{gathered} P\{X\ge i\}\le e^{-it}{\left[q+p{e}^t\right]}^n={\left(e^t\right)}^{-i}{\left[q+p{e}^t\right]}^n\stackrel{\left(\mathbf{a}\right)}{=}{\left(\frac{iq}{(n-i)p}\right)}^{-i}{\left(q+p\frac{iq}{(n-i)p}\right)}^n={\left(\frac{(n-i)p}{iq}\right)}^i{\left(\frac{npq}{(n-i)p}\right)}^n \\ =\frac{n^n{q}^{n-i}{p}^i}{i^i(n-i{)}^{n-i}}=\frac{n^n(1-p{)}^{n-i}{p}^i}{i^i(n-i{)}^{n-i}} \end{gathered}$$