Shannon entropy

What is a bit of information?

In 1948, Claude Shannon gave a mathematical definition of information. His idea: the information contained in a message is measured by the surprise it causes. A certain event brings no information; a rare event brings a lot. The unit is the bit: the amount of information in a choice between two equally likely possibilities (heads or tails).

From probability to information

The more probable a message, the less informative it is. The amount of information of an event with probability p is log2(1/p) bits. An event with probability 1/2 brings 1 bit; one with probability 1/8 brings 3.

probability p      information = log2(1/p)
1     (certain)    0 bits    (no surprise)
1/2                1 bit
1/4                2 bits
1/8                3 bits    (the rarer, the more informative)

Entropy: the average information of a source

The entropy H of a source is the average amount of information per symbol it emits. For a source emitting symbols with probabilities p1, p2..., you add up, for each symbol, its probability multiplied by its information. Entropy is measured in bits per symbol.

A source that always emits the same letter has an entropy of 0 (no surprise). A source that emits 4 equally likely letters has an entropy of 2 bits per letter. Entropy is maximal when all symbols are equally likely.

The limit of compression

Shannon's central result: you cannot encode a source with fewer bits per symbol than its entropy without losing information. Entropy therefore sets the absolute limit of lossless compression. No algorithm, however clever, can beat it.

Classic pitfall

An already well-compressed file has an entropy close to the maximum: its bits look random, and there is no redundancy left to exploit. Trying to compress it again gains nothing, and may even make it slightly larger (because of the added headers). Believing you can compress indefinitely is the illusion that entropy forbids.