Chernoff Bounds

---

6.2.3 Chernoff Bounds

If $X$ is a random variable, then for any $a\in R$ , we can write

$$P(X\ge a)=P(esX\ge esa),fors>0,P(X\le a)=P(esX\ge esa),fors<0.$$

Now, note that $esX$ is always a positive random variable for all $s\in R$ . Thus, we can apply Markov’s inequality. So for $s>0$ , we can write

$$P(X\ge a)=P(esX\ge esa)\le E[esX]esa,byMarko{v}^{\prime }sinequality.$$

Similarly, for $s<0$ , we can write

$$P(X\le a)=P(esX\ge esa)\le E[esX]esa.$$

Note that $E[esX]$ is in fact the moment generating function, $MX(s)$ . Thus, we conclude

Chernoff Bounds:

$P(X\ge a)\le e-saMX(s),$	$foralls>0$ ,
$P(X\le a)\le e-saMX(s),$	$foralls<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

$$P(X\ge a)\le mins>0e-saMX(s),P(X\le a)\le mins<0e-saMX(s).$$

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\ge \alpha n)$ , where $p<\alpha <1$ . Evaluate the bound for $p=12$ and $\alpha =34$ .

• Solution
  • For $X\sim Binomial(n,p)$ , we have $$MX(s)=(pes+q)n,whereq=1-p.$$ Thus, the Chernoff bound for $P(X\ge a)$ can be written as $$P(X\ge \alpha n)\le mins>0e-saMX(s)=mins>0e-sa(pes+q)n.$$ To find the minimizing value of $s$ , we can write $$ddse-sa(pes+q)n=0,$$ which results in $$es=aqnp(1-\alpha ).$$ By using this value of $s$ in Equation 6.3 and some algebra, we obtain $$P(X\ge \alpha n)\le (1-p1-\alpha )(1-\alpha )n(p\alpha )\alpha n.$$ For $p=12$ and $\alpha =34$ , we obtain $$P(X\ge 34n)\le (1627)n4.$$

---

Comparison between Markov, Chebyshev, and Chernoff Bounds:

Above, we found upper bounds on $P(X\ge \alpha n)$ for $X\sim Binomial(n,p)$ . It is interesting to compare them. Here are the results that we obtain for $p=14$ and $\alpha =34$ :

$$P(X\ge 3n4)\le 23Markov,P(X\ge 3n4)\le 4nChebyshev,P(X\ge 3n4)\le (1627)n4Chernoff.$$

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 $4n$ goes to zero as $n$ goes to infinity. The strongest bound is the Chernoff bound. It goes to zero exponentially fast.

← previous

next →

---

The print version of the book is available on Amazon.
**Practical uncertainty:**Useful Ideas in Decision-Making, Risk, Randomness, & AI