Textbooks invariably seem to carry the proof that uses Markov’s inequality, moment-generating functions, and Taylor approximations. Here’s an easier way.<\/p>\n
For $latex p,q \\in (0,1)$, let $latex K(p,q)$ be the KL divergence between a coin of bias $latex p$ and one of bias $latex q$: $latex K(p,q) = p \\ln \\frac{p}{q} + (1-p) \\ln \\frac{1-p}{1-q}.$<\/p>\n
Theorem:<\/strong> Suppose you do $latex n$ independent tosses of a coin of bias $latex p$. The probability of seeing $latex qn$ heads or more, for $latex q > p$, is at most $latex \\exp(-nK(q,p))$. So is the probability of seeing $latex qn$ heads or less, for $latex q < p$.<\/p>\n Remark:<\/em> By Pinsker’s inequality, $latex K(q,p) \\geq 2(p-q)^2$.<\/p>\n Proof<\/strong> Let’s do the $latex q > p$ case; the other is identical.<\/p>\n Let $latex \\theta_p$ be the distribution over $latex \\{0,1\\}^n$ induced by a coin of bias $latex p$, and likewise $latex \\theta_q$ for a coin of bias $latex q$. Let $latex S$ be the set of all sequences of $latex n$ tosses which contain $latex qn$ heads or more. We’d like to show that $latex S$ is unlikely under $latex \\theta_p$.<\/p>\n Pick any $latex \\bar{x} \\in S$, with say $latex k \\geq qn$ heads. Then: Since $latex \\theta_p(\\bar{x}) \\leq \\exp(-nK(q,p)) \\theta_q(\\bar{x})$ for every $latex \\bar{x} \\in S$, we have [latex]\\theta_p(S) \\leq \\exp(-nK(q,p)) \\theta_q(S) \\leq \\exp(-nK(q,p))[\/latex] and we’re done.<\/p>\n","protected":false},"excerpt":{"rendered":" Textbooks invariably seem to carry the proof that uses Markov’s inequality, moment-generating functions, and Taylor approximations. Here’s an easier way. For $latex p,q \\in (0,1)$, let $latex K(p,q)$ be the KL divergence between a coin of bias $latex p$ and one of bias $latex q$: $latex K(p,q) = p \\ln \\frac{p}{q} + (1-p) \\ln \\frac{1-p}{1-q}.$ … <\/p>\n
\n[latex size=”2″] \\frac{\\theta_q(\\bar{x})}{\\theta_p(\\bar{x})} = \\frac{q^k(1-q)^{n-k}}{p^k(1-p)^{n-k}} \\geq \\frac{q^{qn}(1-q)^{n-qn}}{p^{qn}(1-p)^{n-qn}} = \\left( \\frac{q}{p} \\right)^{qn} \\left( \\frac{1-q}{1-p}\\right)^{(1-q)n} = e^{n K(q,p)}.[\/latex]<\/p>\n