Information Theory

Beyond the bits: measuring information

Data compression distinguishes lossless and lossy techniques. Lossless methods preserve all data by using redundancy, while lossy methods reduce size by permanently discarding selected information. This raises two questions: how can we measure information in data, and how can we define a limit for lossless compression?

These tools come from information theory, developed in part through Claude E. Shannon's work. In his 1948 paper, Shannon described a mathematical model of communication and measures of information. In this setting, information is related to the unpredictability of an event, or its surprise.

Self-information: measuring the surprise of a single event

Before we can measure the information in an entire file or message, we need to start with the smallest component: a single event or symbol. The measure for this is called .

Probability and surprise

Consider two illustrative statements about tomorrow's weather:

The sun will rise in the east.
A rare tropical storm will form and bring record snowfall.

The first statement describes an event with probability close to 1, so it provides little new information. The second describes a rare event, so observing it would be more informative. Self-information grows as probability decreases, with a logarithmic relationship: rare events have higher self-information, while common events have lower self-information.

The mathematical formulation

The self-information $I(x)$ of an event $x$ with probability $P(x)$ is defined as:

I(x) = \log_2\left(\frac{1}{P(x)}\right) = -\log_2(P(x))

The formula can be read in several steps:

$P(x)$ : This is the probability of event $x$ . For this formula, $0 < P(x) \le 1$ . A value of 1 denotes a certain event, while a value of 0 denotes an impossible event whose self-information has no finite value.
$\frac{1}{P(x)}$ : The reciprocal probability grows for rare events. For $P(x) = 0.99$ it is about 1.01, while for $P(x) = 0.0001$ it is 10,000.
$\log_2$ : The base-2 logarithm measures information in bits. For independent events, the information of their joint outcome is the sum of their individual self-information values.
The negative sign ( $-$ ): For $0 < P(x) \le 1$ , the logarithm is negative or zero. The negative sign makes self-information non-negative.

Example 1: the fair coin toss

Apply the formula to a single toss of a fair coin.

There are two possible outcomes: Heads (H) and Tails (T).
The probability of getting heads is $P(H) = 0.5$ .
The probability of getting tails is $P(T) = 0.5$ .

Now, let's calculate the self-information for observing heads:

I(H) = -\log_2(P(H)) = -\log_2(0.5) = -\log_2\left(\frac{1}{2}\right) = -(-1) = 1 \text{ bit}

The self-information for tails is also 1 bit. Resolving the uncertainty of an event with two equally probable outcomes provides exactly one bit of information.

Example 2: the biased coin toss

Consider a biased or "unfair" coin, where one outcome is more likely than the other.

Let's say the coin is weighted to land on Tails most of the time.
Probability of Heads: $P(H) = 0.125$ (or 1/8).
Probability of Tails: $P(T) = 0.875$ (or 7/8).

Let's calculate the self-information for each outcome:

I(H) = -\log_2(0.125) = -\log_2\left(\frac{1}{8}\right) = -(-3) = 3 \text{ bits}

I(T) = -\log_2(0.875) \approx -(-0.1926) \approx 0.1926 \text{ bits}

This example shows information as a measure of surprise. The rare outcome, Heads, provides 3 bits, while the predictable outcome, Tails, provides about 0.19 bits. Confirming a high-probability outcome provides less information.

: the average information of a data source

Self-information describes one event. A data file, such as a text document or image, is a sequence of many symbols, including characters or pixel values. To assess the compression potential of the file, we need the average information per symbol. This measure is called entropy.

Entropy is the expected self-information of a source. It answers the question: "How much information does a symbol generated by this source carry on average?"

The mathematical formulation of entropy

The entropy of a data source $X$ , which produces a set of symbols $\{x_1, x_2, \ldots, x_n\}$ with corresponding probabilities $P(x_i)$ , is denoted by $H(X)$ and calculated by summing the self-information of each symbol, weighted by its probability of occurrence:

H(X) = \sum_{i=1}^{n} P(x_i) \cdot I(x_i) = -\sum_{i=1}^{n} P(x_i) \cdot \log_2(P(x_i))

Entropy describes a source distribution, not one particular file. When symbols depend on context, a conditional source model can be used and conditional entropy can be analyzed. A fixed independent distribution is a simpler approximation.

The base of the logarithm selects the unit: base 2 gives bits, while other bases give different units.

The unit of entropy is bits per symbol. The value describes the source's average unpredictability under the selected probability distribution.

For an alphabet with $n$ symbols, entropy satisfies $0 \le H(X) \le \log_2 n$ . It is zero when the source always emits the same symbol. The upper bound is reached when all symbols have equal probabilities.

Example 1: the entropy of a fair coin

Using our fair coin example, where $P(H)=0.5$ , $I(H)=1$ bit, and $P(T)=0.5$ , $I(T)=1$ bit:

H(X) = (P(H) \cdot I(H)) + (P(T) \cdot I(T)) = (0.5 \cdot 1) + (0.5 \cdot 1) = 1 \text{ bit/symbol}

The entropy is 1 bit per symbol. This is the maximum value for a source with two outcomes. Under this model, both outcomes are equally likely, so there is no frequency imbalance to exploit.

Example 2: the entropy of a biased coin

For our biased coin, with $P(H)=0.125$ , $I(H)=3$ bits, and $P(T)=0.875$ , $I(T) \\approx 0.1926$ bits:

H(X) = (P(H) \cdot I(H)) + (P(T) \cdot I(T)) = (0.125 \cdot 3) + (0.875 \cdot 0.1926) \approx 0.375 + 0.1685 \approx 0.544 \text{ bits/symbol}

The entropy is about half a bit per symbol. This value describes the source's predictability. A rare event carries much information, but occurs infrequently, so the source's average information remains low. Such a distribution contains redundancy that lossless compression can use.

Entropy as a limit for lossless compression

Shannon's Source Coding Theorem gives an asymptotic limit for long sequences from a source with a specified model. The entropy $H(X)$ is the lower bound on the average number of bits per symbol for lossless coding.

For long blocks from source

X

, lossless coding cannot achieve an average below

H(X)

bits per symbol. Average coding rates above

H(X)

are achievable asymptotically with suitable coding.

Entropy describes average information under a selected model, while redundancy also depends on the representation. A character may use 8 storage bits in a byte-oriented representation, but ASCII defines 7 bits and UTF-8 uses 1 to 4 bytes per code point. Ranges such as 1 to 1.5 bits per character for English or 1.5 to 2.5 bits for Polish depend on the corpus and model; they are not universal limits. ZIP with Deflate can remove part of the representation redundancy, while the limit follows from the entropy of the selected model.

Practical codes operate on finite blocks, so rounding, headers, and model descriptions can make the result exceed the entropy. Context models can achieve a lower average than a model that assigns one fixed independent distribution to every symbol.

The bound describes an average over long sequences. Individual messages can be shorter or longer, and storing metadata increases the output size.