How Did Claude Shannon Define Information Entropy?

Claude Shannon defined information entropy in his 1948 paper A Mathematical Theory of Communication as a measure of the average uncertainty or information content produced by a stochastic data source. By quantifying how unpredictable a source's symbols are, Shannon's entropy establishes the exact theoretical lower bound on the average number of bits per symbol required to losslessly encode and transmit messages from that source in classical computing.

Measuring Surprise and Information Content

To measure the information of a source, Shannon first needed a way to quantify the information gained from observing a single event or symbol \(x_i\) that occurs with probability \(p_i\). Intuitively, a rare event carries more information (or "surprise") than a common one, and the information from two independent events should add together.

Shannon showed that the only function satisfying these requirements is the logarithm of the inverse probability, known as self-information \(I(x_i)\):

\[I(x_i) = \log_2 \left( \frac{1}{p_i} \right) = -\log_2(p_i)\]

Using base \(2\) for the logarithm expresses the result in bits. If a symbol is certain to occur (\(p_i = 1\)), it carries \(0\) bits of information. If a symbol occurs with probability \(p_i = \frac{1}{8}\), observing it yields \(-\log_2(\frac{1}{8}) = 3\) bits of information.

The Shannon Entropy Formula

A classical information source emits a sequence of symbols from a finite alphabet \(X = \{x_1, x_2, \dots, x_n\}\), where each symbol \(x_i\) has probability \(p(x_i)\). Shannon defined the information entropy \(H(X)\) as the expected value (weighted average) of the self-information across all possible symbols:

\[H(X) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i)\]

By convention, if \(p(x_i) = 0\), the term \(0 \log_2 0\) is treated as \(0\), since an impossible symbol contributes nothing to the average.

Entropy reaches its maximum value of \(\log_2(n)\) bits per symbol when all \(n\) symbols are equally likely (\(p(x_i) = \frac{1}{n}\)). Conversely, entropy drops toward \(0\) when the distribution is heavily skewed and one symbol dominates, because the output becomes highly predictable.

Connecting Entropy to Minimum Bits

Shannon's Source Coding Theorem (also known as the noiseless coding theorem) proves why \(H(X)\) represents the theoretical minimum number of bits needed to encode a source.

If we compress a sequence of \(N\) independent and identically distributed symbols from source \(X\) into binary strings, any lossless compression scheme must use at least \(H(X)\) bits per symbol on average as \(N\) grows large. Attempting to encode the source using fewer than \(H(X)\) bits per symbol inevitably causes information loss, making exact reconstruction impossible.

On the other hand, Shannon proved that we can get arbitrarily close to \(H(X)\) bits per symbol by grouping symbols into long blocks and assigning shorter binary codes to more probable blocks and longer codes to rarer ones. In classical computing, practical algorithms such as Huffman coding and arithmetic coding approximate this limit, demonstrating how Shannon's entropy serves as the fundamental benchmark for data compression.