Stirling's formula and binary entropy to get binomial coefficient asymptotic

207 Views Asked by At

I am trying to prove the following $${n \choose an} \sim \frac{1}{\sqrt{2\pi a (1-a)n}}2^{nH(a)}$$

I have this so far but it seems like I made an error somewhere and I am unable to identify where.

Let $q = 1-a$

$${n \choose an} \sim \frac{n!}{(qn)!(an)!}$$

$$\sim \frac{({\frac{n}{e}})^n}{({\frac{an}{e}})^{an}({\frac{qn}{e}})^{qn}} \frac{\sqrt{2\pi n}}{\sqrt{2\pi an} \sqrt{2\pi qn}}$$

Taking the log of both sides: $$\log_2 {n \choose an} \sim -n(a\log_2 a + q \log_2 q) - \log_2(2\pi naq)/2$$ $$ \frac{1}{n}\log_2 {n \choose an} \sim -(a\log_2 a + q \log_2 q) - \log_2(2\pi naq)/2n$$

By the definition of binary entropy function $H(a)$:

as $ n\to \inf$ $$\frac{1}{n}\log_2{n \choose an} = H(a)$$ $${n \choose an} = 2^{nH(a)}$$

I am missing this part: $\frac{1}{\sqrt{2\pi a (1-a)n}}$

1

There are 1 best solutions below

0
On

Recall $f(n)\sim g(n)$ (as $n\to\infty$) means $\lim\limits_{n\to\infty}f(n)/g(n)=1$, and $\lg$ means $\log_2$.

It is true that $f(n)\sim g(n)$ implies $\lg|f(n)|\sim\lg|g(n)|$ (assuming $f(n),g(n)\not\to1$), though notice the intermediate step to get to this, namely $\lg|f(n)|=\lg |g(n)|+o(1)$, is much stronger (that is, this $o(1)$ equality implies but is not implied by the weaker statement $\lg|f(n)\sim\lg|g(n)|$). The $o(1)$ equality follows from simply taking $\lg$s of both sides of $\lim\limits_{n\to\infty}f(g)/g(n)=1$.

But, the converse is not true: that is, for positive-valued functions $f$ and $g$, $\lg f(n)\sim\lg g(n)$ does not imply $f(n)\sim g(n)$. Indeed $f(n)/g(n)$ could tend to $0$ or $+\infty$ or anything in between at any rate you want. So you want to be careful about just "taking logs of both sides."

It is true that $\lg\binom{n}{an}\sim nH(a)$, but this does not imply $\binom{n}{an}\sim2^{nH(a)}$, which is false.

If you simplify what you got before taking logs, you have

$$ \binom{n}{an}\sim \frac{1}{a^{an}(1-a)^{(1-a)n}}\cdot\frac{1}{\sqrt{2\pi a(1-a)n}} \tag{$\circ$}$$

The correct way of taking logs, then dividing by $n$ reveals

$$ \frac{1}{n}\lg\binom{n}{an}=-a \lg a-(1-a)\lg(1-a)+o(1) $$

(the $\mathrm{stuff}/n$ term gets subsumed into the $o(1)$ error). Taking $n\to\infty$ yields

$$ H(a)=-a\lg a-(1-a)\lg(1-a). $$

Now if we go back to $(\circ)$, we can rewrite the first fraction as a power:

$$ \binom{n}{an}\sim 2^{n\,[\,(-a\lg a-(1-a)\lg(1-a)\,]}\cdot\frac{1}{\sqrt{2\pi a(1-a)n}} \tag{$\bullet$} $$

which simply becomes $\binom{n}{an}\sim 2^{nH(a)}/\sqrt{2\pi a(1-a)n}$.