Theorem. Let \(X\) be the number of heads in \(n\) coin tosses. Then \(\Pr[X=\left\lfloor \frac{n}{2}+c\sqrt{n} \right\rfloor] = \frac{1}{\sqrt{n}}e^{-\Theta(c^{2})}.\)
Proof.
\[\binom{n}{\frac{n}{2}+c\sqrt{n}} = \Theta(\frac{1}{\sqrt{n}}) 2^{nH(\frac{1}{2}+\frac{c}{\sqrt{n}})}.\]
\[H\left(\frac{1}{2}+\frac{c}{\sqrt{n}}\right) \approx (4(\frac{1}{2}+\frac{c}{\sqrt{n}})(\frac{1}{2}-\frac{c}{\sqrt{n}}))^{\frac{1}{\ln 4}} \approx 1-\frac{4}{\ln 4}\frac{c^{2}}{n}.\]
Combining these bounds we conclude the theorem.
The bounds used here are:
- \((1-x)^{\alpha}\approx 1-\alpha x\)
- \(H(x)\approx (4(x)(1-x))^{\frac{1}{\ln 4}}\)
These are pretty darn good for small \(x\).
Here’s another “proof” of the fact:
Proof. \[\int_{x}^{x+1}e^{-t^{2}}dt \approx e^{-x^{2}}.\] + central limit theorem
Proof. you can also prove these things with just stirlings approx + some taylor series. In particular you will need:
\[\sqrt{1-x} \approx 1-\frac{x}{2}\]
\[\frac{1}{1-\varepsilon}\approx 1+\varepsilon\]
\[(1-\varepsilon)^{\frac{1}{\varepsilon}}\approx \frac{1}{e}\]
\[e^{-x}\approx 1-x\]
again these are good when the parameters \(x,\varepsilon\) are small.
How does this compare with Chernoff Bound?
The Chernoff bound says,
\[\Pr[X > \frac{n}{2} + c\sqrt{n}] \le e^{-c^{2}}.\] or something like this
In fact we can conclude this from my bound in this blog post:
\[\frac{1}{\sqrt{n}}\sum_{k=-c\sqrt{n}}^{c\sqrt{n}}\binom{n}{k}\frac{1}{2^{n}} \approx \int_{-c}^{c}e^{-t^{2}}dt\] But \[\int_{c}^{\infty}e^{-t^{2}}dt \approx e^{-c^{2}}.\]
So \[\int_{-c}^{c}e^{-t^{2}}dt \approx 1- e^{-c^{2}}.\]