3
$\begingroup$

I am looking for an interpretation of Stirling's formula using information theory.

Suppose you have $n$ different objects and $n$ different labels. There are $n!$ different ways of assigning the labels to the objects, provided that no two different objects get assigned the same label. The corresponding entropy is thus $\log_2(n!)$.

This entropy is less than or equal to the sum of the entropies of each object. Fixing an object, there are $n$ possible labels, each occurring with equal probability. So each object has entropy $\log_2(n)$.

We thus get $\log_2(n!) \leq n\log_2(n)$.

My question is how to get the next term in Stirling's formula ($-n\log_2(e)$) at least intuitively, and using information theory, when $n$ is large?

$\endgroup$
3
$\begingroup$

Just for fun: it is enough to exploit the prime number theorem $\pi(n)\sim\frac{n}{\log n}$. Legendre's theorem on $\nu_p(n!)$ ensures

$$ n! = \prod_{p\leq n} p^{\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\ldots}\leq \prod_{p\leq n}p^{\frac{n}{p-1}} $$ which is a rather crude bound, but already sufficient:

$$ \log(n!) \leq n\sum_{p\leq n}\frac{\log(p)}{p-1}=n\sum_{m\leq n}\mathbb{1}_p(m)\frac{\log m}{m-1}\stackrel{\text{SBP}}{=}\underbrace{n\pi(n)\frac{\log n}{n-1}}_{O(n)}+n\sum_{m\leq n-1}\pi(m)\left[\frac{\log m}{m-1}-\frac{\log(m+1)}{m}\right].$$ Here $\mathbb{1}_p$ is the characteristic function of primes, $\pi$ is the prime-counting function and $\text{SBP}$ stands for summation by parts. In the last sum the main term behaves like $\frac{1}{m}+O\left(\frac{\log m}{m^2}\right)$, hence $$\log(n!) = O(n)+n\sum_{m\leq n-1}\frac{1}{m} =n\log(n)+O(n).$$ Of course this is extreme cheating: historically speaking, weak forms of the PNT were derived from the asymptotics for $n!$ or $\binom{2n}{n}$, while here we performed just the opposite. A more elementary approach is to consider that $$ \frac{4^n}{\sqrt{n+1}}<\binom{2n}{n}=\frac{(2n)!}{n!^2}<4^n $$ where the inequality on the right is trivial and the inequality on the left follows from $\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2$ and Cauchy-Schwarz. By the theory of moments, the previous inequality holds for non-integer values of $n$, too, so by letting $L(n)=\log(n!)$ we have

$$ L(n)-2 L(n/2) < n\log(2), $$ $$ 2L(n/2)- 4L(n/4) < n\log(2), $$ $$ 4L(n/4)- 8 L(n/8) < n\log(2), $$ $$ \ldots $$

and

$$ L(n) - 2^k L\left(\frac{n}{2^k}\right) \leq kn\log(2). $$ By picking $k\approx \log_2(n)=\frac{\log(n)}{\log(2)}$ the claim $L(n)\sim n\log n$ is proved.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you. I shall read carefully your answer soon. It would be nice to absorb it. But I still would like a more information-theoretic approach. Your answer is very informative though (no pun intended -- I just noticed the pun)! $\endgroup$ – Malkoun Sep 29 '19 at 17:06
  • $\begingroup$ @Malkoun: the main argument here is that asymptotics for $n!$ can be derived from asymptotics for $\binom{2n}{n}$. Since $$ \frac{1}{4^n}\binom{2n}{n}=\frac{2}{\pi}\int_{0}^{\pi/2}(\cos\theta)^{2n}\,d\theta$$ and the RHS is a moment, to prove $\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi\left(n+\frac{1}{4}\right)}}$ is fairly simple. A behaviour of the $\frac{4^n}{\sqrt{\pi n}}$ kind is also justified by the central limit theorem. $\endgroup$ – Jack D'Aurizio Sep 29 '19 at 17:17
  • $\begingroup$ Here there are elementary but very accurate approximations for $\binom{2n}{n}$: math.stackexchange.com/a/2549434/44121 $\endgroup$ – Jack D'Aurizio Sep 29 '19 at 17:21
  • $\begingroup$ I read the first proof. That was nice. Thank you. In particular, I have learned about Legendre's theorem. $\endgroup$ – Malkoun Oct 3 '19 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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