3
$\begingroup$

In many places I see the entropy definition as:

$H(X) = \sum_{i=1}^n {p(x_i)\,I(x_i)} = -\sum_{i=1}^n {p(x_i) \log_b p(x_i)}$

In Wikipedia I saw: $H(X) = \operatorname{E}(I(X))$ where E is expected value and I is information content.

Today I was discussing an issue with my friends and couldn't decide if chessboard's entropy is high or low. Because I can define chessboard as "1 black, 1 white square tiled into $8\times8$ grid". I don't need to send all the cell values. The difference is more distinct if the board size is large, say $1000\times1000$. I think the second definition is better since it includes definition of information content, it is more intuitive for people who comes from different backgrounds. I cannot utilize the first definition for the chessboard case.

The same thing goes for lots of things. Take digits of $\pi$. It takes too much resource to send the first 1M digits compared to sending just the $\pi$ generating formula. Is the entropy of $\pi$ high or low?

Edit: Because I don't know the terms in the field, my title may not be very descriptive. Any title suggestions are welcome.

1 Answers 1

8

Entropy is defined for a probability distribution; it measures how much information must be provided, on average, to identify a randomly chosen element from that distribution. To measure the information required to generate a specific string, on the other hand, one can use the Kolmogorov complexity or a related complexity measure. The colors of the $10^6 \times 10^6$ chessboard and the first trillion digits of $\pi$ can be expressed using far less than a trillion bits, and this is a consequence of the low complexity of those objects.

  • 2
    So, "entropy of chessboard" is not something meaningful since it is not a random variable. Did I get it right?2011-02-25