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

The entropy for the binomial distribution can be calculated (see linked question). However, for the multinomial distribution 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 closed form for the special case $p_i = \frac{1}{k} \hspace{0.5cm} \forall i$ ? (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?

Linked questions

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 $p_i=1/k=constant$ the sum is trivial,right? $\endgroup$ – tired Oct 5 '16 at 12:05
  • $\begingroup$ Sorry I had some mistakes in the definitions. Corrected now. $\endgroup$ – Yiteng Oct 5 '16 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.