# Entropy of the multinomial distribution

In my work I've found myself in the position of needing to calculate the entropy of the multinomial distribution:

$$\text{Multinomial}({\bf x};\; n,{\bf p})$$

I imagine it would be too much to expect a closed-form formula for this value, but what is the current standard method for efficiently calculating/approximating the entropy of a multinomial distribution?

Also my situation is for small $n$, so asymptotic approximations probably aren't the best for me unless they converge extremely quickly.

## 1 Answer

Ok so I guess I should have done a bit of experimentation before posting this question. I just assumed that since the Wikipedia article for the multinomial distribution didn't mention entropy, and since I couldn't find anything about it on google, that it was very difficult to compute.

Let $${\bf X}\sim \text{Multinomial}(n,{\bf p})$$

The entropy for $$\bf X$$ is given by: $$\text{H}({\bf X})=-\hspace{-4mm}\sum_{\substack{ {\bf x}\geq0\\\\\\ \sum_ix_i=n}}\frac{n!}{x_1!\cdots x_k!}p_1^{x_1}\cdots p_k^{x_k}\log\Big[\frac{n!}{x_1!\cdots x_k!}p_1^{x_1}\cdots p_k^{x_k}\Big].$$

Using the logarithm to break this up we obtain: \begin{align} \text{H}({\bf X}) &= -\log n! - \sum_{i=1}^k\log p_i\text{E}[X_i]+\sum_{i=1}^k\text{E}[\log X_i!]\notag\\ &=-\log n! - n\sum_{i=1}^kp_i\log p_i+\sum_{i=1}^k\text{E}[\log X_i!]\notag\\ &=-\log n! - n\sum_{i=1}^kp_i\log p_i+\sum_{i=1}^k\sum_{x_i=0}^n\binom{n}{x_i}p_i^{x_i}(1-p_i)^{n-x_i}\log x_i!.\notag \end{align}

Thus we see that instead of summing over all distinct permutations of the partitions of $$n$$, which scales exponentially with both the size of $$n$$ and $$k$$, the derived form scales as $$O((n+1)k)$$, which is linear in both $$n$$ and $$k$$.