Lesson 2

Theorem (Local CLT of de Moivre — Laplace). Let \(\alpha \sim \operatorname{Binomial}(n,p)\), where \(0<p<1\). Then for all \(k \in [np-\Delta, np+\Delta]\), where \(\Delta=o(n^{2/3})\), it holds that \[\Pr[\alpha=k]=\frac{1}{\sqrt{2\pi np(1-p)}}\exp\left(-\frac{(k-np)^2}{2np(1-p)}\right)(1+o(1)) \ .\]

Proof. We use Stirling's formula \[n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \ ,\] to estimate the required probability: \[\begin{align*}\Pr[\alpha=k]&=\binom{n}{k}p^{k}(1-p)^{n-k}=\\&=\frac{n!}{k!(n-k)!}p^{k}(1-p)^{n-k}\sim \\&\sim \frac{\sqrt{2\pi n}}{\sqrt{2\pi k} \sqrt{2\pi(n-k)}}\frac{n^ne^ke^{n-k}}{e^nk^k(n-k)^{n-k}}p^{k}(1-p)^{n-k}\sim \\&\sim \frac{1}{\sqrt{2\pi p(1-p)n}}\frac{n^n}{k^k(n-k)^{n-k}}p^{k}(1-p)^{n-k}= \\&\sim \frac{1}{\sqrt{2\pi p(1-p)n}}\frac{(np)^k}{k^k}\frac{(n(1-p))^{n-k}}{(n-k)^{n-k}}\ .\end{align*}\] Now let \(\delta=k-np=o(n^{2/3})\). Then \(n-k=n(1-p)-\delta\). For further estimation, we use the Taylor series of the function \(\ln(1+x)\) (Mercator series): \[\ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\dotsb = \sum_{i=1}^{\infty}\frac{(-1)^{i+1}}{i}x^{i}\] (the series converges for \(|x|<1\)).

\[\begin{align*}\ln\left(\frac{k^k}{(np)^k}\right)&=k\ln\left(1+\frac{\delta}{np}\right)=\\&=(np+\delta)\left(\frac{\delta}{np}-\frac{\delta^2}{2(np)^2}+\frac{\delta^3}{3(np)^3}-\dotsb\right)=\\&=\delta+\frac{\delta^2}{2np}+o(1) \ .\end{align*}\] Similarly, \[\ln\left(\frac{(n-k)^{n-k}}{(n(1-p))^{n-k}}\right)=-\delta+\frac{\delta^2}{2n(1-p)}+o(1) \ .\] Adding these two estimates, we get \[\begin{align*}\ln\left( \frac{(np)^k}{k^k}\frac{(n(1-p))^{n-k}}{(n-k)^{n-k}}\right)&=-\frac{\delta^2}{2np}-\frac{\delta^2}{2n(1-p)}+o(1)=\\&=-\frac{\delta^2}{2np(1-p)}+o(1)=\\&=-\frac{(k-np)^2}{2np(1-p)}+o(1) \ .\end{align*}\] ◼