Entropy of the multinomial distribution

Question

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 [3] 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?

Links

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

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

[2]: L.A. Shepp, I. Olkin, Entropy of the Sum of Independent Bernoulli Random Variables and of the Multinomial Distribution, Technical Report, 1978, link (Wayback Machine).

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

Answer 1

I know this is an old question but I am pretty sure that many people, including myself, have similar questions to your own.

There is no known closed form for the entropy of the multinomial distribution even in the simple case of $p_i=\frac{1}{k}$ for all $i$.

However, there are interesting regimes one can look at to obtain interesting closed form limiting expressions.

Asymptotic expression for 'large' $n$

A common approximation consists in looking at the asymptotic behaviour when $n$ is large. It corresponds to the normal distribution limit of the Binomial distribution.

It states that for 'large' $n$

\begin{equation} H \approx \frac{k-1}{2}\ln(2\pi n e)+\frac{1}{2}\sum_{i=1}^k \ln p_i \end{equation}In the above expression I have used the natural logarithm for the entropy. Note that I am not looking for an upper bound or a lower bound here. Simply an approximate form for 'large' $n$.

In the case where the $p_i$ are uniform we simply get

\begin{equation} H \approx \frac{k-1}{2}\ln(2\pi n e) - \frac{k}{2} \ln k \end{equation}

I know that this is not an exact expression, but it does a very good job at giving an estimate of $H$.

See Figure below (plotted for $m=10$)

Approximate expression in the case where $k \gg n$

There is another possible regime that can be investigated. And I am personally interested in this one. It is when you have always $k \gg n$ but also a model for the probabilities $p_i$ which is a decreasing function of $k$. The uniform distribution is obviously such a model since $p_i = \frac{1}{k}$.

In that case, this corresponds more to the Poisson limit of the Binomial distribution as mentioned in a comment by @usul.

In that case, what happens is that $k$ is so large that essentially either $x_i = 0$ or $x_i = 1$. The probability to have any other number is dwarfed in comparison to these contributions. That also makes sense: if you have $n$ trials but $k \gg n$ -- say equally likely -- outcomes, the likelihood to land on the same outcome twice is very small. Anyway, the expression for $H$ simplifies and becomes in this regime:

\begin{equation} H \approx -\ln (n!) - n \sum_{i=1}^k p_i \ln p_i \end{equation}

Applies to the uniform case, it gives

\begin{equation} H \approx -\ln (n!) + n \ln k \end{equation}

This works incredibly well (this is maybe trivial I don't know).

See Figure below for $m = 20000$

The calculated points are literally on top of each other.

Of course, one can see that there is a linear trend because $k$ is so large that the $-\ln n!$ term barely plays any role.

The error one makes when using this approximation is of order $\mathcal{O}\left(\frac{n^2}{k}\right)$ so it will stop being so good when $n \simeq \sqrt{k}$.

Answer 2

I am not at all sure I understand the question, since the OP's reference [2] has a formula for the entropy, and has asymptotics in the equidistributed case (the latter on page 7, the former on page 5, I think).