25
$\begingroup$

In the definition of jointly typical sets (in "Elements of Information Theory", ch. 7.6, p. 195), we use

$$-\frac{1}{n} \log{p(x^n)}$$ as the empirical entropy of an $n$-sequence with $p(x^n) = \prod_{i=1}^{n}{p(x_i)}$. I never came across this terminology before. It is not defined explicitly anywhere according to the index of the book.

My question basically is: Why is empirical entropy not $-\sum_{x}{\hat p (x) \log(\hat p(x))}$ where $\hat p(x)$ is the empirical distribution?

What are the most interesting differences and similarities between these two formulas? (in terms of properties they share/do not share).

Improve this question
$\endgroup$
6
  • $\begingroup$ Aren't the two expressions algebraically equal? $\endgroup$
    – whuber ♦
    May 10, 2012 at 15:08
  • 3
    $\begingroup$ @whuber: No, they are different quantities, with different purposes, I believe. Note that the first uses the true measure $p$ assumed known a priori. The second does not. $\endgroup$
    – cardinal
    May 10, 2012 at 16:05
  • 4
    $\begingroup$ The former is concerned with the accumulation of entropy over time and how it compares to the true entropy of the system. The SLLN and CLT tell one a lot about how it behaves. The second is concerned with estimating the entropy from data and some of its properties can also be obtained via the same two tools just mentioned. But, whereas the first is unbiased, the second is not under any $p$. I can fill in some details if it would be helpful. $\endgroup$
    – cardinal
    May 10, 2012 at 16:09
  • 1
    $\begingroup$ @cardinal: If you'd provide the above comment as an answer (maybe also explain what SLLN and CLT are? - I don't know these) I'd gladly upvote... $\endgroup$
    – blubb
    May 10, 2012 at 17:35
  • $\begingroup$ Ok, I will try to post more later. In the meantime, SLLN="Strong law of large numbers" and CLT="Central limit theorem". These are fairly standard abbreviations that you'll likely encounter again. Cheers. :) $\endgroup$
    – cardinal
    May 10, 2012 at 17:58

2 Answers 2

Reset to default
22
$\begingroup$

If the data is $x^n = x_1 \ldots x_n$, that is, an $n$-sequence from a sample space $\mathcal{X}$, the empirical point probabilities are $$\hat{p}(x) = \frac{1}{n}|\{ i \mid x_i = x\}| = \frac{1}{n} \sum_{i=1}^n \delta_x(x_i)$$ for $x \in \mathcal{X}$. Here $\delta_x(x_i)$ is one if $x_i = x$ and zero otherwise. That is, $\hat{p}(x)$ is the relative frequency of $x$ in the observed sequence. The entropy of the probability distribution given by the empirical point probabilities is $$H(\hat{p}) = - \sum_{x \in \mathcal{X}} \hat{p}(x) \log \hat{p}(x) = - \sum_{x \in \mathcal{X}} \frac{1}{n} \sum_{i=1}^n \delta_x(x_i) \log \hat{p}(x) = -\frac{1}{n} \sum_{i=1}^n \log\hat{p}(x_i).$$ The latter identity follows by interchanging the two sums and noting that $$\sum_{x \in \mathcal{X}} \delta_x(x_i) \log\hat{p}(x) = \log\hat{p}(x_i).$$ From this we see that $$H(\hat{p}) = - \frac{1}{n} \log \hat{p}(x^n)$$ with $\hat{p}(x^n) = \prod_{i=1}^n \hat{p}(x_i)$ and using the terminology from the question this is the empirical entropy of the empirical probability distribution. As pointed out by @cardinal in a comment, $- \frac{1}{n} \log p(x^n)$ is the empirical entropy of a given probability distribution with point probabilities $p$.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ (+1) This provides a nice illustration of what Cover and Thomas refer to as the "strange self-referential character" of the entropy. However, I'm not sure the answer actually addresses (directly) the OP's apparent concerns. :) $\endgroup$
    – cardinal
    May 11, 2012 at 13:00
  • $\begingroup$ @cardinal, I know, and the answer was just a long comment to make this particular point. I did not want to repeat your points. $\endgroup$
    – NRH
    May 11, 2012 at 17:47
  • 1
    $\begingroup$ You should not feel bad or hesitate to post your own answer including expansion on my comments or those of others. I'm particularly slow and bad about posting answers, and will never take offense if you or others post answers that incorporate aspects of things I may have previously commented briefly on. Quite the contrary, in fact. Cheers. $\endgroup$
    – cardinal
    May 11, 2012 at 18:11
  • $\begingroup$ One useful fact to keep in mind: the entropy of the empirical distribution defined this way can never exceed $\log n$. $\endgroup$
    – Yibo Yang
    Mar 21 at 4:33
8
$\begingroup$

Entropy is defined for probability distributions. When you do not have one, but only data, and plug in a naive estimator of the probability distribution, you get empirical entropy. This is easiest for discrete (multinomial) distributions, as shown in another answer, but can also be done for other distributions by binning, etc.

A problem with empirical entropy is that it is biased for small samples. The naive estimate of the probability distribution shows extra variation due to sampling noise. Of course one can use a better estimator, e.g., a suitable prior for the multinomial parameters, but getting it really unbiased is not easy.

The above applies to conditional distributions as well. In addition, everything is relative to binning (or kernelization), so you actually have a kind of differential entropy.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ We should be careful with what we are referring to as the empirical entropy here. Note that the plug-in estimator is always biased low for all sample sizes, though the bias will decrease as the sample size increases. It's not only difficult to get unbiased estimators for the entropy, but rather impossible in the general case. There has been fairly intense research in this area over the last several years, particularly in the neuroscience literature. Lots of negative results exist, in fact. $\endgroup$
    – cardinal
    May 11, 2012 at 12:41

Your Answer

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

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