## 6.2.3 Chernoff Bounds

Chernoff Bounds:

$P(X \geq a)\leq e^{-sa}M_X(s),$ | $\textrm{ for all }s>0$, |

$P(X \leq a)\leq e^{-sa}M_X(s),$ | $ \textrm{ for all }s<0$ |

Since Chernoff bounds are valid for all values of $s>0$ and $s<0$, we can choose $s$ in a way to obtain the best bound, that is we can write \begin{align}%\label{} P(X \geq a)& \leq \min_{s>0} e^{-sa}M_X(s), \\ P(X \leq a)&\leq \min_{s<0} e^{-sa}M_X(s). \end{align} Let us look at an example to see how we can use Chernoff bounds.

Example

Let $X \sim Binomial(n,p)$. Using Chernoff bounds, find an upper bound on $P(X \geq \alpha n)$, where $p< \alpha<1$. Evaluate the bound for $p=\frac{1}{2}$ and $\alpha=\frac{3}{4}$.

**Solution**- For $X \sim Binomial(n,p)$, we have \begin{align}%\label{} M_X(s)=(pe^s+q)^n, &\qquad \textrm{ where }q=1-p. \end{align} Thus, the Chernoff bound for $P(X \geq a)$ can be written as \begin{align}\label{eq:cher-1} P(X \geq \alpha n)& \leq \min_{s>0} e^{-sa}M_X(s)\\ \ &= \min_{s>0} e^{-sa}(pe^s+q)^n. \end{align} To find the minimizing value of $s$, we can write \begin{align}%\label{} \frac{d}{ds} e^{-sa}(pe^s+q)^n=0, \end{align} which results in \begin{align}%\label{} e^{s}=\frac{aq}{np(1-\alpha)}. \end{align} By using this value of $s$ in Equation 6.3 and some algebra, we obtain \begin{align}%\label{} P(X \geq \alpha n)& \leq \big( \frac{1-p}{1-\alpha}\big)^{(1-\alpha)n} \big(\frac{p}{\alpha}\big)^{\alpha n}. \end{align} For $p=\frac{1}{2}$ and $\alpha=\frac{3}{4}$, we obtain \begin{align}%\label{} P(X \geq \frac{3}{4} n)& \leq \big(\frac{16}{27}\big)^{\frac{n}{4}}. \end{align}

**Comparison between Markov, Chebyshev, and Chernoff Bounds:**

Above, we found upper bounds on $P(X \geq \alpha n)$ for $X \sim Binomial(n,p)$. It is interesting to compare them. Here are the results that we obtain for $p=\frac{1}{4}$ and $\alpha=\frac{3}{4}$: \begin{align}%\label{} &P(X \geq \frac{3n}{4})\leq \frac{2}{3} \hspace{58pt} \textrm{Markov}, \\ &P(X \geq \frac{3n}{4})\leq \frac{4}{n} \hspace{57pt} \textrm{Chebyshev}, \\ &P(X \geq \frac{3n}{4})\leq \big(\frac{16}{27}\big)^{\frac{n}{4}} \hspace{35pt} \textrm{Chernoff}. \end{align} The bound given by Markov is the "weakest" one. It is constant and does not change as $n$ increases. The bound given by Chebyshev's inequality is "stronger" than the one given by Markov's inequality. In particular, note that $\frac{4}{n}$ goes to zero as $n$ goes to infinity. The strongest bound is the Chernoff bound. It goes to zero exponentially fast.