Joel French

Answered

2022-07-08

An approximation by Stirling's formula

Let $0<\alpha <1$ be a real number and αn be $\alpha n$ integer. I want to prove the following fact

$(}\genfrac{}{}{0ex}{}{n}{\alpha n}{\textstyle )}=\frac{1+o(1)}{\sqrt{2\pi \alpha (1-\alpha )n}}{2}^{nH(\alpha )},$

where $H(\alpha )=-\alpha {\mathrm{log}}_{2}\alpha -(1-\alpha ){\mathrm{log}}_{2}(1-\alpha )$. To do this, I've used the Stirling's formula for the factorial:

$n!=(\frac{n}{e}{)}^{n}\sqrt{2\pi n}{e}^{r(n)},$,

where $1/(12n+1)<r(n)<1/12n$.

What I've tried:

$(}\genfrac{}{}{0ex}{}{n}{\alpha n}{\textstyle )}=\frac{n!}{(\alpha n)!((1-\alpha )n)!}=\frac{(\frac{n}{e}{)}^{n}\sqrt{2\pi n}{e}^{r(n)}}{(\frac{\alpha n}{e}{)}^{\alpha n}\sqrt{2\pi \alpha n}{e}^{r(\alpha n)}(\frac{(1-\alpha )n}{e}{)}^{(1-\alpha )n}\sqrt{2\pi (1-\alpha )n}{e}^{r((1-\alpha )n)}}\phantom{\rule{0ex}{0ex}}\frac{{e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}}{({\alpha}^{\alpha}(1-\alpha {)}^{(1-\alpha )}{)}^{n}\sqrt{2\pi \alpha (1-\alpha )n}}=\frac{{e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}}{\sqrt{2\pi \alpha (1-\alpha )n}}{2}^{nH(\alpha )}.$

Now how can I show that ${e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}=1+o(1)$?

Let $0<\alpha <1$ be a real number and αn be $\alpha n$ integer. I want to prove the following fact

$(}\genfrac{}{}{0ex}{}{n}{\alpha n}{\textstyle )}=\frac{1+o(1)}{\sqrt{2\pi \alpha (1-\alpha )n}}{2}^{nH(\alpha )},$

where $H(\alpha )=-\alpha {\mathrm{log}}_{2}\alpha -(1-\alpha ){\mathrm{log}}_{2}(1-\alpha )$. To do this, I've used the Stirling's formula for the factorial:

$n!=(\frac{n}{e}{)}^{n}\sqrt{2\pi n}{e}^{r(n)},$,

where $1/(12n+1)<r(n)<1/12n$.

What I've tried:

$(}\genfrac{}{}{0ex}{}{n}{\alpha n}{\textstyle )}=\frac{n!}{(\alpha n)!((1-\alpha )n)!}=\frac{(\frac{n}{e}{)}^{n}\sqrt{2\pi n}{e}^{r(n)}}{(\frac{\alpha n}{e}{)}^{\alpha n}\sqrt{2\pi \alpha n}{e}^{r(\alpha n)}(\frac{(1-\alpha )n}{e}{)}^{(1-\alpha )n}\sqrt{2\pi (1-\alpha )n}{e}^{r((1-\alpha )n)}}\phantom{\rule{0ex}{0ex}}\frac{{e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}}{({\alpha}^{\alpha}(1-\alpha {)}^{(1-\alpha )}{)}^{n}\sqrt{2\pi \alpha (1-\alpha )n}}=\frac{{e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}}{\sqrt{2\pi \alpha (1-\alpha )n}}{2}^{nH(\alpha )}.$

Now how can I show that ${e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}=1+o(1)$?

Answer & Explanation

poquetahr

Expert

2022-07-09Added 18 answers

Step 1

You are only having difficulty because the version of Stirling you're using is too precise. Instead, use $n!=(1+o(1))\sqrt{2\pi n}(\frac{n}{e}{)}^{n}$ - replacing all of your ${e}^{r(n)}$ factors by $1+o(1)$.

Step 2

The step you're stuck on, where you're trying to show that ${e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}=1+o(1)$, becomes $\frac{1+o(1)}{(1+o(1))(1+o(1))}=1+o(1)$, which is straightforward.

(Technically, the $1+o(1)$ factor we get from Stirling's approximation is $1+{o}_{n\to \mathrm{\infty}}(1)$, so we also have to observe that $1+{o}_{\alpha n\to \mathrm{\infty}}(1)$ and $1+{o}_{(1-\alpha )n\to \mathrm{\infty}}(1)$ are the same asymptotically. This is fine as long as $\alpha $ is a constant, or even more generally than that.)

You are only having difficulty because the version of Stirling you're using is too precise. Instead, use $n!=(1+o(1))\sqrt{2\pi n}(\frac{n}{e}{)}^{n}$ - replacing all of your ${e}^{r(n)}$ factors by $1+o(1)$.

Step 2

The step you're stuck on, where you're trying to show that ${e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}=1+o(1)$, becomes $\frac{1+o(1)}{(1+o(1))(1+o(1))}=1+o(1)$, which is straightforward.

(Technically, the $1+o(1)$ factor we get from Stirling's approximation is $1+{o}_{n\to \mathrm{\infty}}(1)$, so we also have to observe that $1+{o}_{\alpha n\to \mathrm{\infty}}(1)$ and $1+{o}_{(1-\alpha )n\to \mathrm{\infty}}(1)$ are the same asymptotically. This is fine as long as $\alpha $ is a constant, or even more generally than that.)

Waldronjw

Expert

2022-07-10Added 2 answers

Step 1

Since $f(n)=o(1)$ just means $\frac{f(n)}{1}\to 0$ as $n\to \mathrm{\infty}$ (i.e. $f(n)=1+o(1)$ means $f(n)\to 1$), our goal is to show that ${e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}\to 1$, which can be done by showing $r(n)-r(\alpha n)-r((1-\alpha )n)\to 0$. We can use the bounds on r(n) to show that $r(n)-r(\alpha n)-r((1-\alpha )n)<\frac{1}{12n}-\frac{1}{12\alpha n+1}-\frac{1}{12(1-\alpha )n+1}\underset{n\to \mathrm{\infty}}{\to}0$ and $r(n)-r(\alpha n)-r((1-\alpha )n)>\frac{1}{12n+1}-\frac{1}{12\alpha n}-\frac{1}{12(1-\alpha )n}\underset{n\to \mathrm{\infty}}{\to}0$

Step 2

So since $r(n)-r(\alpha n)-r((1-\alpha )n)$ is squeezed between 0 on both sides asymptotically, indeed we have $r(n)-r(\alpha n)-r((1-\alpha )n)\to 0$, and we are done.

Since $f(n)=o(1)$ just means $\frac{f(n)}{1}\to 0$ as $n\to \mathrm{\infty}$ (i.e. $f(n)=1+o(1)$ means $f(n)\to 1$), our goal is to show that ${e}^{r(n)-r(\alpha n)-r((1-\alpha )n)}\to 1$, which can be done by showing $r(n)-r(\alpha n)-r((1-\alpha )n)\to 0$. We can use the bounds on r(n) to show that $r(n)-r(\alpha n)-r((1-\alpha )n)<\frac{1}{12n}-\frac{1}{12\alpha n+1}-\frac{1}{12(1-\alpha )n+1}\underset{n\to \mathrm{\infty}}{\to}0$ and $r(n)-r(\alpha n)-r((1-\alpha )n)>\frac{1}{12n+1}-\frac{1}{12\alpha n}-\frac{1}{12(1-\alpha )n}\underset{n\to \mathrm{\infty}}{\to}0$

Step 2

So since $r(n)-r(\alpha n)-r((1-\alpha )n)$ is squeezed between 0 on both sides asymptotically, indeed we have $r(n)-r(\alpha n)-r((1-\alpha )n)\to 0$, and we are done.

Most Popular Questions