5
$\begingroup$

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.

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

$\endgroup$
  • $\begingroup$ 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?). $\endgroup$ – usul Oct 5 '16 at 18:46
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yiteng Oct 5 '16 at 15:51

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.