Mathematics for Computer Science

Chapter 18 Deviation from the Mean640

18.7.5 Proof of the Chernoff Bound

The proof of the Chernoff bound is somewhat involved. Heck, evenChernoffdidn’t
come up with it! His friend, Herman Rubin, showed him the argument. Thinking
the bound not very significant, Chernoff did not credit Rubin in print. He felt pretty
bad when it became famous!^6

Proof. (of Theorem 18.7.1)
For clarity, we’ll go through the proof “top down.” That is, we’ll use facts that
are proved immediately afterward.

The key step is to exponentiate both sides of the inequalityT cExŒTçand

then apply the Markov bound:

PrŒTcExŒTççDPrŒcTccExŒTçç



ExŒcTç

ccExŒTç

(by Markov)



e.c1/ExŒTç

ccExŒTç

(by Lemma 18.7.2 below)

D

e.c1/ExŒTç

ecln.c/ExŒTç

De.cln.c/cC1/ExŒTç:



Algebra aside, there is a brilliant idea in this proof: in this context, exponenti-
ating somehow supercharges the Markov bound. This is not true in general! One
unfortunate side-effect is that we have to bound some nasty expectations involving
exponentials in order to complete the proof. This is done in the two lemmas below,
where variables take on values as in Theorem 18.7.1.

Lemma 18.7.2.
Ex

h

cT

i

e.c1/ExŒTç:

(^6) See “A Conversation with Herman Chernoff,”Statistical Science1996, Vol. 11, No. 4, pp 335–
350.