# Asymptotics of binomial coefficients and the entropy function

I found a question while I was trying to practice Combinatorics and Probabilistic methods.I tried to solve it with no success.. this is the question:

Use the Stirling approximation of the factorial to show that for every $0\leq p \leq 1$ there holds

$$\lim _{n\to \infty}\frac{1}{n}\log\binom{n}{pn}=H(p)$$ where $H(p)=-p\log(p) -(1-p)\log(1-p)$ is the binary entropy function.

Any help?

-
Is there a combinatorial / information-theoretic intepretation of this, does anyone know? – ShreevatsaR Apr 13 '13 at 11:30
@ShreevatsaR yes, it says that coding a uniform subset, $pn$ of $n$ (lhs), asymptotically requires as many bits as coding a sampling from $n$ elements where each element is picked with change $p$ (rhs). – Thomas Ahle Dec 14 '15 at 14:31

Let $q=1-p$.

The Stirling approximation asserts $n! \sim (\frac{n}{e})^{n} \sqrt{2\pi n}$. This gives:

$$\binom{n}{pn} \sim \frac{(n/e)^{n}}{(np/e)^{np}(nq/e)^{nq}}\frac{\sqrt{2\pi n}}{\sqrt{2\pi np}\sqrt{2\pi nq}}$$

The $(n/e)^n$ cancels with $(n/e)^{np}(n/e)^{nq}$, so this simplifies to:

$$\binom{n}{pn} \sim \frac{1}{p^{np}q^{nq}}\frac{1}{\sqrt{2\pi npq}}$$ Upon taking logarithm in base 2, we get:

$$\log_2\binom{n}{pn} \sim -n (p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/2$$ Dividing by $n$, it transforms to:

$$\frac{1}{n}\log_2\binom{n}{pn} \sim -(p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/(2n) = H(p) + O(\ln n/ n)$$ And when $n$ tends to infinity, we get the desired limit.

EDIT: You don't need the full strength of Stirling approximation. $n! = (n/e)^{n} g(n)$ where $n^{\alpha} \le g \le n^{\beta}$ is enough.

-
It is not by chance that taking the sum of independant bernoulli, we converge to the exponentiated entropy of such bernoulli..... – nicolas Oct 26 '13 at 21:04