Information Theory: Entropy and Information Gain

Why does one message tell you more than another?

Suppose two texts land on your phone on the same July morning. The first says: "It rained in Mumbai today." The second says: "It rained in the Thar desert today." Both sentences have the same length, the same grammar, and describe the same kind of event. Yet the second one makes you sit up. Why?

Because Mumbai in July is expected to be wet — during the monsoon, rain on any given July day is close to a certainty, so being told "it rained" barely changes what you already believed. The Thar desert, on the other hand, sees rain on only a tiny fraction of its days even in a good year. Being told it rained there overturns your expectation. It is a genuinely surprising message, and a surprising message carries more information than an expected one.

This is the seed of an entire mathematical theory. In 1948, Claude Shannon, working at Bell Labs, asked a very practical engineering question: if I want to transmit messages from a source with known statistics, what is the minimum number of bits I need, on average, per message? To answer it, he first had to answer a smaller question that we're about to answer ourselves: how do you turn "surprise" into a number?

Measuring surprise: self-information

Let's say an event x occurs with probability p(x). We want a function I(x) — called the self-information or surprisal of x — that behaves the way "surprise" should behave. Three requirements are non-negotiable:

• If p(x) = 1 (the event was certain), then I(x) = 0. A message telling you something you already knew for sure carries zero information.
• As p(x) decreases, I(x) should increase. Rarer events are more surprising.
• For two independent events x and y, the surprise of learning both should simply add up: I(x and y) = I(x) + I(y). Learning that two unrelated coin tosses both landed heads should feel like exactly twice the surprise of learning one did.

The third condition is the strict one. We need a function that turns multiplication of probabilities (since independent probabilities multiply: p(x and y) = p(x)·p(y)) into addition of outputs. There is essentially one family of functions that does this: the logarithm, because log(a·b) = log(a) + log(b). Combined with the requirement that probability 1 gives zero surprise (and log(1) = 0 for any log base) and that smaller probabilities give larger surprise (so we need a minus sign, since probabilities are ≤1 and their logs are ≤0), we arrive at:

I(x) = -log(p(x)) = log(1 / p(x))

Why base 2? Because Shannon was counting bits — binary yes/no questions. With base 2, an event with probability exactly 1/2 (like a fair coin landing heads) carries exactly -log2(0.5) = 1 bit of information — one yes/no question's worth, which matches intuition perfectly. This is why the unit of information is called the "bit" when log base 2 is used. (If you use the natural log instead, the unit is called a "nat"; CBSE and most ML contexts use base 2, and so will we.)

Let's check the additivity property numerically. Two independent fair coin tosses both landing heads: p(HH) = 0.5 × 0.5 = 0.25. Directly, I(HH) = -log2(0.25) = 2 bits. Via addition: I(H) + I(H) = 1 + 1 = 2 bits. They match, exactly as the theory demands, because log2(0.5 × 0.5) = log2(0.5) + log2(0.5).

Now the Mumbai/Thar example, worked out. Suppose, hypothetically, that during Mumbai's monsoon it rains on about 90% of July days, so p = 0.9. Then I = -log2(0.9) ≈ 0.152 bits — barely any information, because you expected it. Now suppose in the Thar desert in May, rain occurs on roughly 1% of days, so p = 0.01. Then I = -log2(0.01) ≈ 6.644 bits — over 40 times more informative, because the event defied your expectation. This confirms the intuition we started with, now backed by an exact number.

From surprise to entropy: the expected number of bits

Self-information measures the surprise of one specific outcome. But before an experiment happens, we usually want to know: how surprised should I expect to be, on average, across all the outcomes that could occur? That average is called entropy, written H(X) for a random variable X, and it is nothing more than the expected value of self-information, weighted by how often each outcome happens:

H(X) = sum over all outcomes x of  p(x) * I(x)
     = -sum over all outcomes x of  p(x) * log2(p(x))

This single formula is the heart of information theory. It answers Shannon's original question directly: H(X) is the minimum average number of bits needed to communicate the outcome of X, given how the probabilities are distributed.

Three worked cases, from simplest to most instructive:

A fair coin. p(Heads) = p(Tails) = 0.5. H = -(0.5·log2 0.5 + 0.5·log2 0.5) = -(0.5×(-1) + 0.5×(-1)) = 1 bit. You genuinely need one full yes/no question to pin down the outcome — matches intuition exactly.

A biased coin with p(Heads) = 0.9, p(Tails) = 0.1. H = -(0.9·log2 0.9 + 0.1·log2 0.1) = -(0.9×(-0.152) + 0.1×(-3.322)) ≈ 0.469 bits. Notice this is less than 1 bit — because the outcome is more predictable (you'd usually guess Heads and be right), there's less to be surprised about on average, so less information is needed to describe it.

A two-headed coin (a certain outcome): p(Heads) = 1, p(Tails) = 0. H = -(1·log2 1 + 0) = 0 bits. Zero uncertainty, zero information needed — you already know the answer.

Properties of entropy, proved not asserted

Entropy is never negative. Every probability p(x) lies in (0, 1], so log2(p(x)) ≤ 0, so -p(x)·log2(p(x)) ≥ 0 for every single term. A sum of non-negative terms cannot be negative. So H(X) ≥ 0 always, with equality only when the outcome is certain (as we just saw).

Entropy is maximised when all outcomes are equally likely. For n equally likely outcomes, each with probability 1/n, entropy equals exactly log2(n) — and this is the largest value entropy can take for that many outcomes. Compare a fair six-sided die against a loaded one:

Fair die: each face has p = 1/6, so H = log2(6) ≈ 2.585 bits.

Loaded die, weighted toward six: suppose faces 1–5 each have p = 0.1 and face 6 has p = 0.5. Then H = 5×(-0.1·log2 0.1) + (-0.5·log2 0.5) = 5×0.332 + 0.5 = 2.161 bits — noticeably lower than 2.585, because the loaded die is more predictable (you'd bet on six and often be right). This is the general pattern: spreading probability mass evenly maximises uncertainty; concentrating it (even partially) reduces it. Look at the curve below for the two-outcome case — it makes this property visible at a glance.

The two green points on the curve are not decoration — they are the exact entropy values (≈0.722 bits) of the two branches you'll see in the worked classification example just below, so you can see directly how "far from 0.5" a split's probabilities are translates into "how much lower than the 1-bit peak" its entropy sits.

Entropy of a dataset: the target variable's uncertainty

In machine learning, we usually don't compute the entropy of a coin — we compute the entropy of a column of labels in a dataset, because that tells us how hard the classification problem is before we've looked at any features. Consider ten days recorded by a school's sports committee, tracking whether cricket practice happened outdoors:

Day   Sky     Weekend?   PlayCricket?
1     Sunny   Yes        Yes
2     Sunny   No         Yes
3     Sunny   Yes        Yes
4     Sunny   No         No
5     Sunny   No         Yes
6     Rainy   Yes        No
7     Rainy   No         No
8     Rainy   No         No
9     Rainy   Yes        Yes
10    Rainy   No         No

Out of 10 days, PlayCricket is "Yes" on 5 days and "No" on 5 days. Before looking at any feature, the entropy of the target is:

H(PlayCricket) = -(5/10)·log2(5/10) - (5/10)·log2(5/10) = 1 bit

This is the worst case — a perfectly balanced 50/50 split is maximum uncertainty for a binary label, exactly the peak of the curve above. Any feature that helps us classify these days should reduce this entropy. The question is: by how much, and which feature reduces it the most?

Conditional entropy: uncertainty that remains after knowing a feature

Suppose we're told the value of Sky for a given day. Does that reduce our uncertainty about PlayCricket? To find out, we split the dataset by the feature's values and compute the entropy within each branch, then average those entropies weighted by how many records fall into each branch. This is conditional entropy:

H(Y | X) = sum over each value v of X of  (|S_v| / |S|) * H(Y | X=v)

where S_v is the subset of records with X = v, and |S_v|/|S| is the fraction of the data that falls into that branch — the weight makes sense because a branch containing more records should count for more in the average.

For Sky = Sunny: 5 records, of which 4 are "Yes" and 1 is "No". H(Sunny) = -(4/5)log2(4/5) - (1/5)log2(1/5) ≈ 0.722 bits.

For Sky = Rainy: 5 records, of which 1 is "Yes" and 4 are "No". By the same arithmetic (just the labels swapped), H(Rainy) ≈ 0.722 bits.

H(PlayCricket | Sky) = (5/10)×0.722 + (5/10)×0.722 = 0.722 bits.

Information gain: how much a feature actually helps

Information gain is simply how much the entropy dropped once we knew the feature — the uncertainty we removed by asking about it:

IG(S, A) = H(S) - H(S | A)

For Sky: IG(Sky) = 1 - 0.722 = 0.278 bits. Knowing whether the sky was sunny or rainy removes about 0.278 bits of our uncertainty about whether cricket practice happened — a meaningful, though not total, reduction.

Let's compare this against a second candidate feature, Weekend?, computed from the same table. Weekend = Yes covers days 1, 3, 6, 9 (3 "Yes", 1 "No" → entropy ≈0.811 bits). Weekend = No covers days 2, 4, 5, 7, 8, 10 (2 "Yes", 4 "No" → entropy ≈0.918 bits).

H(PlayCricket | Weekend) = (4/10)×0.811 + (6/10)×0.918 ≈ 0.875 bits
IG(Weekend) = 1 - 0.875 ≈ 0.125 bits

Here's the code that produced every number above, traced and verified — running it prints exactly the values quoted in the text:

import math

def entropy(counts):
    total = sum(counts)
    ent = 0
    for c in counts:
        if c == 0:
            continue
        p = c / total
        ent -= p * math.log2(p)
    return ent

H_parent = entropy([5, 5])                 # 1.0

H_sky = 0.5 * entropy([4, 1]) + 0.5 * entropy([1, 4])
IG_sky = H_parent - H_sky                  # H_sky = 0.7219, IG_sky = 0.2781

H_weekend = 0.4 * entropy([3, 1]) + 0.6 * entropy([2, 4])
IG_weekend = H_parent - H_weekend          # H_weekend = 0.8755, IG_weekend = 0.1245

print(round(IG_sky, 4), round(IG_weekend, 4))   # 0.2781 0.1245

IG(Sky) ≈ 0.278 bits is larger than IG(Weekend) ≈ 0.125 bits. Sky is the more informative feature — it splits the data into branches that are, on average, closer to being pure (all-Yes or all-No) than the branches produced by Weekend.

Why this matters: building a decision tree

This is precisely the machinery inside the classic ID3 algorithm for building decision trees. At the root node, ID3 computes information gain for every available feature and picks the one with the highest gain as the first question the tree asks — here, that would be Sky, not Weekend. It then repeats the entire process independently within each branch (e.g., separately re-examining only the five Sunny days, and separately the five Rainy days) using whatever features remain, splitting again on whichever gives the highest gain in that subset, and recursing until a branch is pure (entropy 0) or no useful features remain.

Two related concepts worth knowing for exams: C4.5, ID3's successor, normalises information gain by a term called split information to correct a bias — plain information gain unfairly favours features with many distinct values (like a "Day number" column with ten unique values, which could split the data into ten singleton, zero-entropy branches while carrying almost no genuine predictive meaning). The normalised version is called gain ratio. CART, the algorithm behind scikit-learn's default `DecisionTreeClassifier`, typically uses a different but related impurity measure called the Gini index instead of entropy — both measure node impurity and both are used to choose splits, but Gini avoids computing logarithms and is slightly faster to compute at scale.

Two misconceptions, corrected

Misconception 1: "Entropy just means disorder, like in physics." The word was borrowed from thermodynamics, and Shannon himself is said to have picked it partly because a colleague joked that "nobody knows what entropy really is anyway," which would give him an advantage in every argument. But information-theoretic entropy is a precisely defined number computed from a probability distribution: H(X) = -Σp(x)log2p(x). It measures the expected number of bits needed to describe the outcome of a random variable — not physical messiness, not chaos in any loose sense. When you see "entropy" in a decision-tree context, always mentally translate it to "average surprise, in bits, given this exact distribution of labels" — nothing more mystical than that.

Misconception 2: "Information gain is computed per row, not as a weighted split." A very common calculation error is to compute the entropy of each branch and simply average them with equal weight, ignoring how many records fall into each branch. If Sky = Sunny had contained 9 records and Sky = Rainy only 1, an unweighted average would treat both branches as equally important, which is wrong — a branch with 9 records genuinely tells you more about the overall dataset than a branch with 1. The formula H(Y|X) = Σ(|S_v|/|S|)·H(Y|X=v) weights each branch's entropy by how much of the data it represents. Always weight by branch size; never average branch entropies unweighted.

Where this fits in your exams

Entropy and information gain are core, explicitly examined content in CBSE's Artificial Intelligence curriculum's data science and machine learning units, almost always in the context of building and evaluating decision trees — exactly the worked example above is the standard exam pattern: given a small labelled table, compute the target entropy, then the information gain of each candidate feature, then state which feature a decision-tree algorithm would split on first. This is not part of the core IIT-JEE Main/Advanced syllabus (which stays within physics, chemistry, and mathematics), so don't expect it there — but it is squarely GATE-foundation material once you reach the Machine Learning and Data Mining portions of GATE Computer Science / AI-ML papers, where entropy, information gain, and Gini index are standard short-answer and numerical-computation topics. It also underlies Huffman coding, the optimal prefix-code construction algorithm that occasionally appears in informatics-olympiad-style problems on data compression — the same entropy formula tells you the theoretical lower bound on how short your compressed code can possibly get.

Check yourself: active recall

• A weather sensor reports "Foggy" or "Clear" each morning in Delhi's winter. Suppose P(Foggy) = 0.7. Compute H for this variable, and state without recomputing whether it is above or below 1 bit, and why.
• A four-outcome spinner has probabilities 0.4, 0.3, 0.2, 0.1. Compute its entropy, and compare it to the maximum possible entropy for four equally likely outcomes. Which is larger, and why must it be?
• Using the ten-day PlayCricket table above, a third feature Humidity splits into "High" (6 records: 2 Yes, 4 No) and "Normal" (4 records: 3 Yes, 1 No). Compute H(PlayCricket | Humidity) and IG(Humidity), and state whether ID3 would prefer Humidity or Sky as the root split.
• Explain, in one or two sentences and without using the word "disorder," what it means for a decision tree branch to have entropy exactly 0.
• A feature has 10 distinct values, one per record, so splitting on it creates 10 branches each with a single record. Its information gain will be very high — explain why this is misleading, and name the exam-relevant technique designed to correct for it.

Hint for question 3: entropy([2,4]) ≈ 0.918 bits, entropy([3,1]) ≈ 0.811 bits — combine with the correct branch weights (6/10 and 4/10) to get H(PlayCricket|Humidity), then subtract from 1 to get the gain, and compare against 0.278 (Sky's gain from earlier).

Summary

Self-information I(x) = -log2 p(x) quantifies the surprise of a single outcome — the logarithm is forced on us by the requirement that independent surprises add. Entropy H(X) = -Σp(x)log2p(x) is the probability-weighted average surprise across an entire random variable — equivalently, the minimum average number of bits needed to describe its outcomes. Entropy is always non-negative, is zero exactly when the outcome is certain, and is maximised at log2(n) when all n outcomes are equally likely. Conditional entropy H(Y|X) measures how much uncertainty about Y remains, on average, once you know a feature X — computed by weighting each branch's entropy by the fraction of data it contains. Information gain IG(S,A) = H(S) - H(S|A) is the resulting drop in uncertainty, and it is exactly the quantity decision-tree algorithms like ID3 maximise, feature by feature, node by node, to decide which question to ask next.

Think About It

Think about this: How would you explain information theory: entropy and information gain to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.