Information Theory and Entropy Explained

How much information is in a coin toss, a text message or a photograph? In 1948 Claude Shannon, a mathematician at Bell Labs, gave a precise answer and founded the field of information theory. His ideas now sit inside every ZIP file, mobile network and machine learning model, and the mathematics needs nothing more than logarithms and probability.

Information as Surprise

Shannon's key insight was that information is about surprise. If someone tells you the sun rose this morning, you learn almost nothing, because you expected it. If they tell you it snowed in Karachi, you learn a lot, because it was very unlikely.

So the information carried by an event should be large when its probability \( p \) is small. Shannon defined the self-information as

$$ I(p) = -\log_2 p \quad \text{bits} $$

This formula has exactly the properties we want:

• A certain event (\( p = 1 \)) carries \( -\log_2 1 = 0 \) bits.
• A fair coin toss (\( p = \tfrac12 \)) carries \( -\log_2 \tfrac12 = 1 \) bit.
• Independent events add: since \( \log(p_1 p_2) = \log p_1 + \log p_2 \), two coin tosses give 2 bits.

Using base 2 gives answers in bits; using natural logarithms gives nats, which machine learning libraries often use.

Entropy: Average Information

A source, such as a stream of letters or a sequence of weather reports, produces many symbols. Entropy \( H \) is the average information per symbol:

$$ H(X) = -\sum_{i} p_i \log_2 p_i $$

Entropy measures uncertainty. It is largest when all outcomes are equally likely and zero when one outcome is certain. For \( n \) equally likely outcomes, \( H = \log_2 n \). A fair six-sided die therefore has \( \log_2 6 \approx 2.585 \) bits of entropy.

Worked Example 1: A Biased Coin

A coin lands heads with probability 0.9 and tails with probability 0.1. Find its entropy.

Step 1. Compute each logarithm.

• \( \log_2 0.9 = \dfrac{\ln 0.9}{\ln 2} = \dfrac{-0.10536}{0.69315} \approx -0.1520 \)
• \( \log_2 0.1 = \dfrac{\ln 0.1}{\ln 2} = \dfrac{-2.30259}{0.69315} \approx -3.3219 \)

Step 2. Substitute.

$$ H = -\big[0.9(-0.1520) + 0.1(-3.3219)\big] = 0.1368 + 0.3322 = 0.469 \text{ bits} $$

Step 3. Interpret. A fair coin gives 1 bit per toss, but this biased coin gives under half a bit, because you can usually guess the outcome. In principle, a long sequence of these tosses could be compressed to about 47% of its raw size.

Entropy and Compression

Shannon's source coding theorem says that no lossless code can use fewer than \( H \) bits per symbol on average, and that codes can get arbitrarily close to \( H \). Entropy is the absolute limit of compression.

The practical way to approach this limit is to give short codes to common symbols and longer codes to rare ones, just as Morse code gives "E" a single dot. David Huffman, a student at MIT, found the optimal method for this in 1952.

Worked Example 2: Entropy Meets Huffman Coding

A source emits A, B, C, D with probabilities \( \tfrac12, \tfrac14, \tfrac18, \tfrac18 \).

Step 1. Entropy.

$$ H = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 \text{ bits} $$

(Each term is \( p_i \cdot (-\log_2 p_i) \); for example \( -\log_2 \tfrac18 = 3 \).)

Step 2. Build a Huffman code. Merge the two least likely symbols repeatedly:

1. Merge C and D (\( \tfrac18 + \tfrac18 = \tfrac14 \)).
2. Merge B with the CD node (\( \tfrac14 + \tfrac14 = \tfrac12 \)).
3. Merge A with that node (\( \tfrac12 + \tfrac12 = 1 \)).

Reading the branches gives the codes A = 0, B = 10, C = 110, D = 111.

Step 3. Average code length.

$$ \bar{L} = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 \text{ bits} $$

Step 4. Compare. A naive fixed-length code needs 2 bits per symbol. Huffman uses exactly 1.75 bits, matching the entropy, a 12.5% saving. It matches perfectly here because every probability is a power of \( \tfrac12 \); otherwise Huffman comes within 1 bit of \( H \).

Channel Capacity: Information Through Noise

Shannon's second great result, the noisy channel coding theorem, says every communication channel has a capacity \( C \), a maximum rate of reliable communication. Below \( C \), clever error-correcting codes can make errors as rare as you like; above it, reliable communication is impossible. For a channel with bandwidth \( B \) and signal-to-noise ratio \( S/N \), the Shannon-Hartley formula gives

$$ C = B \log_2\!\left(1 + \frac{S}{N}\right) $$

For instance, a 3000 Hz telephone line with \( S/N = 1000 \) has capacity \( 3000 \log_2 1001 \approx 3000 \times 9.967 \approx 29{,}900 \) bits per second, which is why old dial-up modems topped out around that speed before compression tricks and digital lines.

Entropy in Machine Learning

Information theory is everywhere in modern AI.

Cross-Entropy Loss

When a classifier predicts a probability distribution \( q \) but the true distribution is \( p \), the cross-entropy is

$$ H(p, q) = -\sum_i p_i \log q_i $$

For a single example whose true class has predicted probability \( q \), this becomes \( -\log q \).

Worked Example 3: Cross-Entropy for One Prediction

An image is truly a cat. Model A predicts "cat" with probability 0.8; Model B predicts 0.2.

Step 1. Model A. \( -\ln 0.8 \approx 0.223 \) nats.

Step 2. Model B. \( -\ln 0.2 \approx 1.609 \) nats.

Step 3. Interpret. Model B's loss is about seven times larger, so training pushes it hard to raise its probability for the correct class. Confident wrong answers are punished most: as \( q \to 0 \), \( -\ln q \to \infty \).

Decision Trees and Information Gain

Decision tree algorithms such as ID3 choose the question that most reduces entropy. The information gain of a split is the entropy before the split minus the weighted average entropy after it. The best split is the one that leaves the groups "purest".

Did You Know?

• The word "bit", short for "binary digit", first appeared in print in Shannon's 1948 paper, which credited the term to his colleague John Tukey.
• Shannon reportedly took the name "entropy" on the advice of John von Neumann, who joked that since nobody really understands entropy, Shannon would always win an argument.
• Shannon estimated that English text carries only about 1 bit per letter once context is used, which is why English compresses so well.

Key Takeaways

• Information measures surprise: an event of probability \( p \) carries \( -\log_2 p \) bits.
• Entropy \( H = -\sum p_i \log_2 p_i \) is the average information and measures uncertainty.
• Entropy is the lower limit for lossless compression, and Huffman coding gets close to it.
• Channel capacity sets the maximum reliable data rate through a noisy channel.
• Cross-entropy and information gain bring these ideas directly into machine learning.

Need step-by-step help with entropy, logarithms or an information theory assignment? Amathify's subject experts and PhD scholars are a WhatsApp message or an Ask a Question form away.