Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 37 ยท Entropy and Information

Properties and Inequalities

The tools that make information theory proofs work: Jensen's inequality, the log-sum inequality, the data processing inequality, Markov chains and Fano's inequality, checked numerically.

A handful of inequalities do most of the heavy lifting in information theory. You have already used some without naming them: entropy is non-negative, conditioning reduces entropy, KL divergence is non-negative. This lesson collects the key ones, explains why they hold, and tests each numerically so you can trust them.

A summary table

Fact Statement
Non-negativity H(X) >= 0, I(X; Y) >= 0, D(p || q) >= 0
Upper bound H(X) <= log2 n
Conditioning H(Y | X) <= H(Y)
Subadditivity H(X, Y) <= H(X) + H(Y)
Data processing If X -> Y -> Z, then I(X; Z) <= I(X; Y)
Fano Error probability bounds the remaining uncertainty

Jensen's inequality

A function f is convex if the chord between two points lies above the graph (like x^2 or -log x). Jensen's inequality says E[f(X)] >= f(E[X]) for convex f, and the reverse for concave f. Since log is concave:

TEXT
E[log2 Z] <= log2 E[Z]

This is how entropy's upper bound is proved. Take Z = 1/p(X): then H(X) = E[log2(1/p(X))] <= log2 E[1/p(X)] = log2 n, because E[1/p(X)] = sum over x of p(x)/p(x) = n.

Python Jensen's inequality for log

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every row prints True. The gap between the two sides measures how spread out the values are.

The log-sum inequality

For positive numbers a_1..a_n and b_1..b_n:

TEXT
sum a_i log(a_i / b_i)  >=  (sum a_i) log( (sum a_i) / (sum b_i) )

It is a close relative of Jensen and proves that KL divergence is convex in the pair (p, q), among other things. For distributions (both sums equal to 1) the right side is log 1 = 0, which is exactly Gibbs' inequality D(p || q) >= 0.

Python Check the log-sum inequality

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Markov chains and the data processing inequality

Write X -> Y -> Z when Z depends on X only through Y: given Y, Z is independent of X. Think of X as the original, Y as a measurement and Z as a computation performed on the measurement.

The data processing inequality says that no processing of Y can create information about X:

TEXT
I(X; Z) <= I(X; Y)

Compression, filtering, quantizing and feature extraction can only lose information about the source. They can still be useful (they discard what you do not need), but they never add what was not there.

flowchart LR
    X["X (source)"] --> Y["Y (measurement)"] --> Z["Z (processed)"]
    X -. "I(X;Z) <= I(X;Y)" .-> Z

Processing cannot increase information about X.

Python Data processing inequality in action

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Merging four values into two throws away detail, so I(X; Z) is smaller than I(X; Y).

Fano's inequality

Suppose you want to guess X from Y and your guess is wrong with probability P_e. If you could be wrong only rarely, then knowing Y must leave little uncertainty about X. Fano's inequality makes this precise:

TEXT
H(X | Y) <= h(P_e) + P_e log2(|X| - 1)

where h is the binary entropy function. It is the main tool for proving that error-free communication above capacity is impossible: a large remaining uncertainty H(X | Y) forces a large error probability.

Python Fano's inequality for the best guesser

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bound always holds. In coding theory, if a code makes P_e tiny, Fano says the decoder's remaining uncertainty H(X | Y) must be tiny too, so enough information must have passed through the channel.

You rarely need to prove these from scratch. The habit worth building is to recognize which one is at work: Jensen for averages inside a log, data processing for chains of transformations, Fano for "small error implies small uncertainty".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Jensen's inequality for the concave log function says

    For concave functions, the average of the function is at most the function of the average.
  2. 2. In a Markov chain X -> Y -> Z, which is true?

    Processing Y cannot increase what it reveals about X (the data processing inequality).
  3. 3. What does Fano's inequality connect?

    A small probability of error forces H(X | Y) to be small, and vice versa.
  4. 4. Which of these is the Gibbs inequality?

    KL divergence is non-negative, with equality only when p = q.

Summary

  • Jensen's inequality on the concave log gives H(X) <= log2 n and Gibbs' inequality.
  • The log-sum inequality underlies convexity of KL divergence.
  • Data processing: functions and noisy processing of a measurement cannot increase information about the source.
  • Fano's inequality ties error probability to remaining uncertainty and is the standard converse tool.

Next: Codes and Prefix Codes