Probability - The Chernoff Bound

The Chernoff Bound

The Chernoff bound is like a genericized trademark: it refers not to a particular inequality, but rather a technique for obtaining exponentially decreasing bounds on tail probabilities.

Much of this material comes from my CS 365 textbook,Randomized Algorithms by Motwani and Raghavan.

Let $X1,\dots ,XN$ be independent random variables where $Xi$ takes the value $1$ with probability $pi$ and $0$ otherwise (a Bernoulli distribution). Suppose at least one of the $pi$ is nonzero. Let $X=\sum i=1NXi$ , and let $\mu =E[X]=\sum i=1Npi$ .

Multiplicative Chernoff Bound

We bound $Pr[X>(1+\delta )\mu ]$ for $\delta >0$ via Markov’s inequality and a Taylor series approximation of the exponential function.

We have $Pr[X>(1+\delta )\mu ]=Pr[etX>et(1+\delta )\mu ]$ for all $t>0$ . We’ll later select an optimal value for $t$ . By Markov’s inequality, we have:

$$Pr[etX>et(1+\delta )\mu ]\le E[etX]/et(1+\delta )\mu$$

My textbook stated this inequality is in fact strict if we assume none of the $pi$ are 0 or 1, but I’m not sure this is required, due to a strict inequality later on.

Then since the $Xi$ are independent:

$$E[etX]=E[et(X1+\dots +Xn)]=E[\prod i=1NetXi]=\prod i=1NE[etXi]$$

We can compute $E[etXi]$ explicitly: this random variable is $et$ with probability $pi$ , and $1$ otherwise, that is, with probability $1-pi$ , thus this is equal to:

$$\prod i=1NE[etXi]=\prod i=1N(1+pi(et-1))$$

We have $1+x<ex$ for all $x>0$ . As long as at least one $pi>0$ :

$$\prod i=1N(1+pi(et-1))<\prod i=1Nepi(et-1)=e(p1+...+pn)(et-1)=e(et-1)\mu$$

Whence:

$$Pr[X>(1+\delta )\mu ]<e(et-1)\mu /et(1+\delta )\mu$$

It is time to choose $t$ . Differentiating the right-hand side shows we attain the minimum at $t=ln(1+\delta )$ , which is positive when $\delta$ is. This value of $t$ yields the Chernoff bound:

$$Pr[X>(1+\delta )\mu ]<(e\delta (1+\delta )1+\delta )\mu$$

Below Expectations

We use the same technique to bound $Pr[X<(1-\delta )\mu ]$ for $\delta >0$ . We have:

$$Pr[X<(1-\delta )\mu ]=Pr[-X>-(1-\delta )\mu ]=Pr[e-tX>e-(1-\delta )\mu ]$$

for any $t>0$ . If we proceed as before, that is, apply Markov’s inequality, use the approximation $1+x<ex$ , then pick $t$ to minimize the bound, we have:

$$Pr[X<(1-\delta )\mu ]<(e-\delta (1-\delta )1-\delta )\mu$$

Bounding the bounds

Unfortunately, the above bounds are difficult to use, so in practice we use cruder but friendlier approximations.

Recall $ln(1-x)=-x-x2/2-x3/3-\dots$ . Thus if $\delta \le 1$ , we have:

$$ln(1-\delta )>-\delta -\delta 2/2$$

Exponentiating both sides, raising to the power of $1-\delta$ and dropping the highest order term yields:

$$(1-\delta )1-\delta >e-\delta +\delta 2/2$$

Thus for $0<\delta <1$ :

$$Pr[X<(1-\delta )\mu ]<e-\delta 2\mu /2,0<\delta <1$$

As for the other Chernoff bound,Wikipedia states:

$$Pr[X>(1+\delta )\mu ]<e-\delta 2\mu /3,0<\delta <1$$

but my textbook quotes a better bound:

$$Pr[X>(1+\delta )\mu ]<e-\delta 2\mu /4,0<\delta <2e-1$$

An Additive Chernoff Bound

Due to Hoeffding, this Chernoff bound appears as Problem 4.6 in Motwani and Raghavan. It was also mentioned in a cryptography class I took long ago.

For $i=1,\dots ,n$ , let $Xi$ be a random variable that takes $1$ with probability $p$ and $0$ otherwise, and suppose they are independent. Let $X=\sum i=1nXi$ . Then:

$$Pr[|X-E[X]|\ge n\delta ]\le 2e-2\delta 2$$

---

Ben Lynn blynn@cs.stanford.edu 💡