Mathematics for Computer Science

Chapter 19 Deviation from the Mean812

that the first server is overloaded, by the Union Bound in Section 16.5.2. So

PrŒsome server is overloadedç

Xm

iD 1

PrŒserveriis overloadedç

DmPrŒthe first server is overloadedç

me.cln.c/cC1/
6000=m;

wherecDm=10. Some values of this upper bound are tabulated below:

m D 11 W 0:784:::

m D 12 W 0:000999:::

m D 13 W 0:0000000760::::

These values suggest that a system withmD 11 machines might suffer immediate
overload,mD 12 machines could fail in a few days, butmD 13 should be fine for
a century or two!

19.6.6 Proof of the Chernoff Bound

The proof of the Chernoff bound is somewhat involved. In fact,Chernoff himself
couldn’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!^7

Proof. (of Theorem 19.6.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ç

(Markov Bound)



e.c1/ExŒTç

ccExŒTç

(Lemma 19.6.2 below)

D

e.c1/ExŒTç

ecln.c/ExŒTç

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



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