Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
2  
So, "entropy of chessboard" is not something meaningful since it is not a random variable. Did I get it right? –  nimcap Feb 25 '11 at 7:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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