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.

up vote 4 down vote accepted

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$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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