21

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?

Community
  • 1
user844541
  • 1,573
  • 3
  • 14
  • 28
  • Is there a combinatorial / information-theoretic intepretation of this, does anyone know? – ShreevatsaR Apr 13 '13 at 11:30
  • 2
    @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

2 Answers2

15

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.

Ofir
  • 6,245
  • 1
    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
  • @Ofir would very much appreciate a textbook / reference for this fact, if possible? thanks – BD107 Oct 24 '21 at 23:27
0

Sorry, I know this is 11 years later, but here's an 'elementary' proof using only

  1. The Binomial Theorem
  2. If $n+1$ numbers sum to 1, the largest must be at least $\frac{1}{n+1}$
  3. $\log_2(n+1)/n\to 0$ as $n\to\infty$.

Let $p=\frac{k}{n}$ and $q=\frac{n-k}{n}$. Then $1=\sum_{i=0}^{n}\binom{n}{i}p^iq^{n-i}$ by the Binomial Theorem.

Further, the following are equivalent: \begin{align*} \binom{n}{i}p^iq^{n-i}&\le\binom{n}{i+1}p^{i+1}q^{n-i-1}\\ \frac{q}{p}&\le\frac{n-i}{i+1}\\ \frac{1}{p}&\le\frac{n+1}{i+1}\\ \frac{i+1}{n+1}&\le\frac{k}{n}\\ i+1&\le k+\frac{k}{n}\\ i+1&\le k. \end{align*}

This shows that the terms $\binom{n}{i}p^iq^{n-i}$ are increasing up to $i=k$ and decreasing thereafter, so the largest is $\binom{n}{k}p^kq^{n-k}$. By a continuous analogue of the Pigeonhole Principle, $\binom{n}{k}p^kq^{n-k}\ge\frac{1}{n+1}$.

It follows that: \begin{align*} \frac{1}{n+1}&\le\binom{n}{k}p^kq^{n-k}&&\le1\\ -\log_2(n+1)&\le\log_2\binom{n}{k}+k\log_2(\frac{k}{n})+(n-k)\log_2(1-\frac{k}{n})&&\le 0\\ -\frac{\log_2(n+1)}{n}+H(\frac{k}{n})&\le\frac{1}{n}\log_2\binom{n}{k}&&\le H(\frac{k}{n}), \end{align*}

so $H(\frac kn)-\frac{1}{n}\log_2\binom{n}{k}\to 0$ from above, with a bound that is independent of $k$.

linguo
  • 113