Complexity Explorer Santa Few Institute

Which of these distributions has the highest entropy?

A. A coin toss, where the coin can come up either heads or tails, with 50% probability.

B. A coin toss where the coin is heads on both sides.

C. A computer program that spits out one of the 26 letters in the English language uniformly at random.

D. Sticking your hand in Jane Austen's Pride and Prejudice and pulling out a  letter (ignoring whether it is upper or lower-case).

 

Answer: (C). (B) has zero uncertainty; (A) has more uncertainty than (B) because the coin could come up either way, and we have to go look (gather information) to find out. (C) has more information than (B) because instead of a choice between two options, there's a choice among 26 (another way to see it is that we could get the same randomness in a coin toss by coarse-gaining (C): take a random letter and then asking whether it fell in the first or second half of the alphabet). Finally, (D) has less entropy than (C) because English is biased in favor of some letters (like vowels), and away from others (like z and j); I'm more certain about a letter from an English-language word than I am about a completely uniform distribution. You can also compute the entropy of (A), (B) and (C) exactly, using Shannon's formula; and you can estimate (D) using the original text of Pride and Prejudice (I get around 4.18 bits).