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?

  • 0
    Is there a combinatorial / information-theoretic intepretation of this, does anyone know?2013-04-13
  • 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