Section 6.2.2: Binary Tree Searching

Exercise 34. [HM21] [HM21] Show that the asymptotic value of the multinomial coefficient

(1, pe, spa)

piN, paN, ..., PrN

as N - oo is related to the entropy H(p1,p2,..., Dn).

Verified: yes
Solve time: 1m21s

---

Solution

Let $p_1,\dots,p_r$ satisfy $p_i \ge 0$ and $\sum_{i=1}^r p_i = 1$, and let $n_i = p_i N$ with integers $n_i$ such that $\sum_{i=1}^r n_i = N$. The multinomial coefficient is

$$ \binom{N}{n_1,\dots,n_r} = \frac{N!}{n_1!\cdots n_r!}. $$

Stirling’s formula in the form

$$ m! = \sqrt{2\pi m}, m^m e^{-m},(1+o(1)) $$

is applied to each factorial. Substituting $m=N$ and $m=n_i$ gives

$$ N! = \sqrt{2\pi N}, N^N e^{-N}(1+o(1)), $$

and

$$ n_i! = \sqrt{2\pi n_i}, n_i^{n_i} e^{-n_i}(1+o(1)). $$

Forming the quotient yields

$$ \binom{N}{n_1,\dots,n_r}

\frac{\sqrt{2\pi N}, N^N e^{-N}(1+o(1))} {\prod_{i=1}^r \left(\sqrt{2\pi n_i}, n_i^{n_i} e^{-n_i}(1+o(1))\right)}. $$

The exponential factors satisfy

$$ e^{-N} \Big/ \prod_{i=1}^r e^{-n_i} = 1 $$

since $\sum_{i=1}^r n_i = N$. Hence the exponential terms cancel exactly.

The power terms give

$$ \frac{N^N}{\prod_{i=1}^r n_i^{n_i}}

\frac{N^N}{\prod_{i=1}^r (p_i N)^{p_i N}}

\frac{N^N}{N^N \prod_{i=1}^r p_i^{p_i N}}

\prod_{i=1}^r p_i^{-p_i N}. $$

The square-root factors give

$$ \frac{\sqrt{2\pi N}}{\prod_{i=1}^r \sqrt{2\pi n_i}}

(2\pi N)^{(1-r)/2}\prod_{i=1}^r p_i^{-1/2}. $$

Combining all factors,

$$ \binom{N}{n_1,\dots,n_r}

(2\pi N)^{(1-r)/2} \left(\prod_{i=1}^r p_i^{-1/2}\right) \left(\prod_{i=1}^r p_i^{-p_i N}\right) (1+o(1)). $$

Taking logarithms gives

$$ \log \binom{N}{n_1,\dots,n_r}

-N\sum_{i=1}^r p_i \log p_i

• O(\log N). $$

The quantity

$$ H(p_1,\dots,p_r) = -\sum_{i=1}^r p_i \log p_i $$

is the entropy. Hence

$$ \log \binom{N}{n_1,\dots,n_r}

N H(p_1,\dots,p_r) + O(\log N). $$

Exponentiating,

$$ \binom{N}{n_1,\dots,n_r}

\exp!\big(N H(p_1,\dots,p_r)\big), N^{O(1)}. $$

Thus the multinomial coefficient grows exponentially like $e^{N H(p_1,\dots,p_r)}$, up to polynomial factors in $N$.

This completes the proof. ∎