Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 37 ยท Entropy and Information

Entropy

Define Shannon entropy as expected surprise, compute it in Python, see why the fair coin and uniform distribution maximize it, and estimate entropy from real text.

Entropy is the average surprise of a random variable. If a source emits symbols drawn from a distribution p, then

TEXT
H(X) = - sum over x of p(x) log2 p(x)  = E[ -log2 p(X) ]      (bits)

It is the central quantity of the whole subject: the length, in bits per symbol, of the best possible lossless description of the source (proved in the source coding theorem). A coin that is almost always heads has low entropy; a fair die has high entropy; a source with one certain outcome has zero.

Computing entropy

Terms with p = 0 contribute nothing, by the convention 0 * log 0 = 0 (because p log p tends to 0 as p tends to 0). Code must skip those entries to avoid nan.

Python Entropy from scratch

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 skewed four-symbol source has H = 1.75 bits, less than the 2 bits a fixed-length code would spend. The uniform distribution over 256 values (a random byte) gives exactly 8 bits.

The binary entropy function

For a two-outcome source with probabilities p and 1 - p, entropy is the binary entropy function

TEXT
h(p) = -p log2 p - (1 - p) log2 (1 - p)

It is 0 at p = 0 and p = 1, rises symmetrically, and peaks at exactly 1 bit at p = 1/2. This single curve shows up again in channel capacity.

Python The shape of h(p)

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 printed bars form a hill: a nearly deterministic coin (p = 0.01) has entropy 0.081, about 8% of a bit. You could compress a long run of such tosses by roughly a factor of 12.

Bounds on entropy

For an alphabet of size n:

  • H(X) >= 0, with equality only when one outcome has probability 1.
  • H(X) <= log2 n, with equality only for the uniform distribution.

So the uniform distribution is the hardest to compress: it is the "most random" one. The upper bound follows from Jensen's inequality, which you will use in Properties and Inequalities.

Python Uniform maximizes entropy

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.

No random distribution beats the uniform one, and the best random draw approaches 3.0 from below.

Entropy as the cost of guessing

There is a second reading: H(X) is roughly the average number of yes/no questions needed to identify the outcome, if each question is chosen well. With probabilities 1/2, 1/4, 1/8, 1/8, ask "is it A?" first (half the time you are done after one question), then "is it B?", and so on. The expected number of questions is 1*(1/2) + 2*(1/4) + 3*(1/8) + 3*(1/8) = 1.75, which equals H. When all probabilities are powers of 1/2, the match is exact; in general entropy is a lower bound.

Estimating entropy from data

Real sources do not come with a distribution. A simple estimate counts frequencies and plugs them in: the empirical (plug-in) entropy. It describes the symbol-level statistics only; it says nothing about structure such as which letter tends to follow which.

Python Empirical entropy of text

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.

Look at abababababab. Its plug-in entropy is exactly 1 bit per character, yet the string is perfectly predictable if you know the pattern. The plug-in estimate only sees single-symbol frequencies; capturing order needs longer contexts and the entropy rate (see The Source Coding Theorem).

Plug-in entropy computed from a small sample is biased low: rare symbols may not appear at all. With few samples, treat the number as a rough lower estimate, not the truth.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the entropy of a fair coin?

    H = -(1/2)log2(1/2) - (1/2)log2(1/2) = 1 bit.
  2. 2. Over an alphabet of 16 symbols, which distribution has maximum entropy?

    Entropy is maximized by the uniform distribution, equal to log2(16) = 4 bits.
  3. 3. How is a term with p = 0 treated in the entropy sum?

    By the convention 0 log 0 = 0, because p log p tends to 0 as p tends to 0.
  4. 4. Why does the string 'abababab' have plug-in entropy of 1 bit per character even though it is fully predictable?

    Plug-in entropy sees each symbol as independent; modelling context (the previous character) would reveal the pattern.

Summary

  • H(X) = -sum p log2 p is the expected surprise, in bits per symbol.
  • 0 <= H <= log2 n, with the uniform distribution as maximum.
  • The binary entropy h(p) peaks at 1 bit when p = 1/2.
  • Entropy measures the cost of identifying an outcome and, as you will see, the limit of lossless compression.
  • Plug-in estimates from data ignore symbol order and are biased for small samples.

Next: Joint and Conditional Entropy