Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 37 ยท Applications

Entropy of Text, DNA and Real Data

Estimate entropy rates of English text and DNA with n-gram models, learn why plug-in estimates are biased on small samples, and use compression as an entropy meter.

So far entropy was computed from probabilities that someone handed us. Real data does not come with a probability table. A text file, a genome or a sensor log is just a long sequence, and we must estimate its entropy from the sequence itself. This is where information theory meets statistics, and it has a classic trap: estimates are biased downward when the sample is small.

This lesson estimates the entropy rate of text and DNA with n-gram models, shows the small-sample bias with a shuffle test, and uses a compressor as a practical entropy meter. It uses ideas from source coding and the compression chapter.

Entropy rate

For a sequence of symbols, the entropy rate is the average information per symbol when you take dependencies into account:

TEXT
h = lim (1/n) H(X1, ..., Xn) = lim H(Xn | X1, ..., X(n-1))

A model of order k predicts each symbol from the previous k symbols. The conditional entropy H(X | previous k symbols) goes down as k grows, because more context removes more uncertainty, and tends to h. Shannon himself estimated the entropy of English at about 1 bit per letter by asking people to guess the next letter, much less than the log2(27) = 4.75 bits of uniformly random letters.

The plug-in estimate counts how often each context and symbol occur, and treats the counts as probabilities.

Python Order-k entropy estimates for 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.

The estimates keep dropping as the order grows, which looks like we are discovering ever more structure. But look carefully: this text has only about 700 characters.

The small-sample trap

With order 4 there are many more possible contexts than we have characters. Most contexts appear once, and after seeing a context once the plug-in estimate is certain what comes next: entropy zero. The estimate falls not because the text is predictable, but because the sample is too small. A shuffle test reveals it: scramble the characters, destroying all real structure, and see what the estimator says.

Python The shuffle test exposes the bias

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.

At order 0 the two agree (same letter counts). At orders 1 and 2 the real text is clearly lower (2.9 against 3.6, and 1.4 against 1.5), which is genuine structure. At orders 3 and 4 the shuffled text, which has no structure, falls to 0.2 and then 0.02 bits: that is pure artefact, and the real-text values of 0.47 and 0.20 are mostly artefact too. Only the low orders are meaningful here. The remedy is more data, a bias-corrected estimator, or a smoothed model evaluated on held-out text, which is also how real language models are judged.

Always test an entropy estimator on shuffled or random data of the same size. If it reports low entropy for noise, the estimate for real data is not trustworthy.

DNA: four letters, almost two bits

DNA is a string over A, C, G, T, so the maximum is 2 bits per base. Real genomes are slightly compressible: base frequencies are uneven, and neighbouring bases correlate (for example, the dinucleotide CG is rare in vertebrate genomes). Typical entropy estimates for large genomes are about 1.9 bits per base with simple models and lower with long-range models that exploit repeats, which is why specialized genome compressors beat general ones.

The following sequence is synthetic: a Markov chain with a made-up transition table that mimics "CG is rare". It is not real genome data, but shows how a model captures such structure.

Python A synthetic genome with rare CG

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.

With 100,000 bases and only a handful of contexts, the order-1 estimate is within 0.001 bits of the true rate, and higher orders do not improve it, because the source really is first-order Markov. Here the sample is large relative to the number of contexts, so the plug-in estimator is reliable.

Compression as an entropy meter

A lossless compressor gives an upper bound on entropy: if a file compresses to m bits for n symbols, the source's entropy rate is probably at most m/n bits per symbol, since a code exists that achieves it. Better compressors give tighter bounds. This lets you measure the complexity of things that have no obvious probability model.

Python Measuring complexity with zlib

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.

For uniform 4-letter data the true entropy is 2 bits per symbol, but zlib reports a bit more, since it is a general-purpose tool with headers and a byte-oriented model. For the biased source the entropy is about 1.72 bits and zlib is above it. Uniform bytes cost 8 bits, plus a little overhead. The ordering of the numbers is right, even if the absolute values are only upper bounds.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a plug-in entropy estimate do?

    It substitutes empirical frequencies for probabilities. That is accurate for large samples but biased downward for small ones.
  2. 2. Why can an order-4 estimate on a 700-character text be misleading?

    With many more contexts than samples, each context is seen once, so its estimated conditional entropy is zero regardless of the real predictability.
  3. 3. What is the maximum entropy of a DNA base sequence per base?

    There are four possible bases, and log2(4) = 2 bits.
  4. 4. What does the compressed size of a file give you?

    A code of that length exists, so the entropy rate cannot be much higher; better compressors give tighter bounds.

Summary

  • Entropy rate is the per-symbol information of a source with dependencies.
  • n-gram models estimate it by conditioning on the previous k symbols.
  • Plug-in estimates are biased low when contexts are rare; test on shuffled data.
  • DNA has at most 2 bits per base and real genomes are only slightly below that.
  • Compression ratios are practical upper bounds on entropy.

Next: Project: A Byte-Entropy Analyzer