Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Is there a combinatorial / information-theoretic intepretation of this, does anyone know? –  ShreevatsaR Apr 13 '13 at 11:30

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.