7
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\begingroup$ Two Q's: 1) Where did $E[X_i]$ come from? 2) From eq. (1) to (2), where did everything before log go? $\endgroup$
    – user13985
    Commented Sep 16, 2019 at 0:49
  • 1
    $\begingroup$ @user13985 recall the definition of entropy is just $\text{E}[-\log(P(X))]$, so when the log breaks things up you just get a bunch of simpler expected values. The stuff before the log is just the probability distribution itself (multinomial pmf) and so it is just folded into the definition of expected value. $\endgroup$
    – Set
    Commented Sep 16, 2019 at 1:18
  • $\begingroup$ I see! I was trying to use this definition $H(X)=-\sum p(x) \log p(x)$. Instead, I should use this definition $H(X)=E[-\log(P(X))]$. I think that's the problem? $\endgroup$
    – user13985
    Commented Sep 16, 2019 at 1:31
  • $\begingroup$ @user13985, well the former definition is canon. I provided you with the alternative definition to help make the point that it can be interpreted as an expected value, and to emphasize that it's a common pattern to look out for in the future, since once you recognize that an expression can be interpreted as an expected value, it may allow you to better see how to solve the problem. $\endgroup$
    – Set
    Commented Sep 16, 2019 at 1:41
  • 1
    $\begingroup$ @user13985 I'm not sure I understand your concern, the definitions are equal to each other, you can switch back and forth between them at will. If you break things up with the log prior to interpreting it as an expected value, you can then at the next step just interpret each of the pieces as an expected value, they all have the appropriate form, i.e. $\sum_x p(x)f(x)$. $\endgroup$
    – Set
    Commented Sep 16, 2019 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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