16
$\begingroup$

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?

  • 1
    @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).2015-12-14

1 Answers 1

11

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.

  • 1
    It is not by chance that taking the sum of independant bernoulli, we converge to the exponentiated entropy of such bernoulli.....2013-10-26