# Entropy of the multinomial distribution

What is the entropy of the multinomial distribution? To fix notation, let us define $n > 0$ as the number of trials, $p_1, \ldots, p_k$ as the probabilities of each of the $k$ possible outcomes and $X_1, \ldots, X_n$ as the outcomes. Recall that the pmf of the multinomial distribution is given by

$f(x; n,p) \equiv f(x_1,\ldots, x_k; n, p_1, \ldots, p_k) = \cases{ \frac{n!}{x_1! \ldots x_k!} p_1^{x_1} \ldots p_k^{x_k} \hspace{1cm} \text{if }\sum_{i=1}^{k} x_i = 1 \\ 0 \hspace{4cm} \text{otherwise} }$

The (Shannon) entropy of a distribution measures the amount of stored information or the uncertainty and for this distribution takes the form

$H = - \sum f(x; n,p) \log{f(x; n,p)} = E[-\log{f(x; n,p)}]$,

where the sum is over all $x = (x_1, \ldots, x_n)$ for which $\sum_{i=1}^{n} x_i = n$.

It has only been shown that the entropy is maximized when $p_i = \frac{1}{k}$ for all $i$ [1, 2]. There is a recent paper  which sets upper and lower bounds on the entropy. However, a closed-form expression for the entropy seems not to have been derived yet.

My questions are: (A) Is there a simplified expression for $p_i = \frac{1}{k} \hspace{0.5cm} \forall i$ that does not involve sums? (B) Are there other special cases for which the entropy can be calculated? (C) Why is it so difficult to obtain a closed-form solution for this?

There is an asymptotic form for the entropy for the binomial distribution in the large $n$ limit: Math.stackexchange question: Entropy of a binomial distribution

References

: P. Mateev, On the entropy of a multinomial distribution, Teor. Veroyatnost. i Primenen., 1978, Volume 23, Issue 1, 196–198, link.

: L.A. Shepp, I. Olkin, Entropy of the Sum of Independent Bernoulli Random Variables and of the Multinomial Distribution, Technical Report, 1978, link.

: Yuichi Kaji, Bounds on the entropy of multinomial distribution, 2015 IEEE International Symposium on Information Theory (ISIT), link.

• For one point, I think it's actually pretty difficult to give very good bounds on the binomial's entropy. (I'm not satisfied with those in your link.) For another, you can think of the entropy of the multinomial as a recursive formula, which is the entropy $x_1$ plus the entropy of $x_2,\dots,x_k$ conditioned on $x_1$, which for any fixed $x_1$ is another case of the multinomial and the base case is the not-that-tractable binomial. Finally, I think different regimes become important, i.e. how does $n$ relate to each $1/p_i$ matters a lot (do the $x_i$ look more like Binomials or Poissons?). – usul Oct 5 '16 at 18:46

• The asymptotics is for $n \rightarrow \infty$, which happens to be not what I'm interested in. The formula for the entropy on page 5 is just the definition of the entropy written out in terms of the multinomial distribution which I called $f(x; n,p)$ above. I'm looking for a simplification of this definition that does not involve the sums. So actually I'm looking for more than a closed-form expression, sorry for the confusion. – Yiteng Oct 5 '16 at 15:51