Textbooks invariably seem to carry the proof that uses Markov’s inequality, moment-generating functions, and Taylor approximations. Here’s an easier way.

For , let be the KL divergence between a coin of bias and one of bias :

**Theorem:** Suppose you do independent tosses of a coin of bias . The probability of seeing heads or more, for , is at most . So is the probability of seeing heads or less, for .

*Remark:* By Pinsker’s inequality, .

**Proof** Let’s do the case; the other is identical.

Let be the distribution over induced by a coin of bias , and likewise for a coin of bias . Let be the set of all sequences of tosses which contain heads or more. We’d like to show that is unlikely under .

Pick any , with say heads. Then:

Since for every , we have and we’re done.

How do you justify the step where you replace k with qn?

Since q/p > 1 and k > qn, (q/p)^k >= (q/p)^(qn). The other factor is similar.

The other factor is similar, but doesn’t it give the wrong direction in inequality? I get 1-q ((1-q)/(1-p))^k<=((1-q)/(1-p))^qn

broken formatting, should be 1-q less than 1-p implies ((1-q)/(1-p))^k<=((1-q)/(1-p))^qn

you dropped the minus sign on k.

John, this is really nice!

Sanjoy, actually

Very cool! Thank you, Sanjoy. My students would be so happy to know that they don’t need to go through the lengthy proof that was given last week.

Isn’t this what they call the method of types in info theory books?

Is there a way to get Chernoff-type bound for more than 2 outcomes? Cover/Thomas use Sanov’s Theorem for that, but it seems much looser than Chernoff-type bound

This is similiar to the idea as that used by Impagliazzo and Kabanets in a recent paper on a combinatorial version of the CH-bound. In that paper, they also generalize this argument (as Yaroslav asks). Nice !

Excellent exposition! Would you please tell me where you found this proof since I assume that it predated the proof by Impapliazzo-Kabanets. Many thanks in advance!

I’m not sure which paper you are referring to.

My understanding is that this proof is new in origination, although I can’t swear it’s the first time it’s been discovered.

@jl: That’s excellent! I have no doubt about its originality, but I thought it was officially published somewhere else either by you or others. Such a nice and simple proof should be more well-known!

[…] the approach to types, summarized with this paper of Impagliazzo and Kabanets, in addition to this brief publish by Sanjoy Dasgupta. These latter proofs tend to be more “intuitive” for the reason that they supplies a […]