In an English text, how much information is obtained per letter? If we had a random sequence of letters, each appearing with probability 1/26, then the entropy would be ${log}_2(26)=4.70$; so each letter would contain 4.7 bits of information. If we include spaces, we get ${log}_2(27)=4.75$. But the letters are not equally likely: $a$ has frequency .082, $b$ has frequency .015, etc. (see Section 2.3). Therefore, we consider

However, this doesn’t tell the whole story. Suppose we have the sequence of letters we are studyin. There is very little uncertainty as to what the last letter is; it is easy to guess that it is $g$. Similarly, if we see the letter $q$, it is extremely likely that the next letter is $u$. Therefore, the existing letters often give information about the next letter, which means that there is not as much additional information carried by that letter. This says that the entropy calculated previously is still too high. If we use tables of the frequencies of the ${26}^2=676$ digrams (a digram is a two-letter combination), we can calculate the conditional entropy of one letter, given the preceding letter, to be 3.56. Using trigram frequencies, we find that the conditional entropy of a letter, given the preceding two letters, is approximately 3.3. This means that, on the average, if we know two consecutive letters in a text, the following letter carries 3.3 bits of additional information. Therefore, if we have a long text, we should expect to be able to compress it at least by a factor of around $3.3/4.7=\mathrm{.7.}$

Let $L$ represent the letters of English. Let $L^N$ denote the $N$-gram combinations. Define the entropy of English to be

where $H(L^N)$ denotes the entropy of $N$-grams. This gives the average amount of information per letter in a long text, and it also represents the average amount of uncertainty in guessing the next letter, if we already know a lot of the text. If the letters were all independent of each other, so the probability of the digram $qu$ equaled the probability of $q$ times the probability of $u$, then we would have $H(L^N)=N\cdot H(L)$, and the limit would be $H(L)$, which is the entropy for one-letter frequencies. But the interactions of letters, as noticed in the frequencies for digrams and trigrams, lower the value of $H(L^N)$.

How do we compute $H(L^N)$? Calculating 100-gram frequencies is impossible. Even tabulating the most common of them and getting an approximation would be difficult. Shannon proposed the following idea.

Suppose we have a machine that is an optimal predictor, in the sense that, given a long string of text, it can calculate the probabilities for the letter that will occur next. It then guesses the letter with highest probability. If correct, it notes the letter and writes down a 1. If incorrect, it guesses the second most likely letter. If correct, it writes down a 2, etc. In this way, we obtain a sequence of numbers. For example, consider the text $itissunnytoday$. Suppose the predictor says that $t$ is the most likely for the 1st letter, and it is wrong; its second guess is $i$, which is correct, so we write the $i$ and put 2 below it. The predictor then predicts that $t$ is the next letter, which is correct. We put 1 beneath the $t$. Continuing, suppose it finds $i$ on its 1st guess, etc. We obtain a situation like the following:

Using the prediction machine, we can reconstruct the text. The prediction machine says that its second guess for the first letter will be $i$, so we know the 1st letter is $i$. The predictor says that its first guess for the next letter is $t$, so we know that’s next. The first guess for the next is $i$, etc.

What this means is that if we have a machine for predicting, we can change a text into a string of numbers without losing any information, because we can reconstruct the text. Of course, we could attempt to write a computer program to do the predicting, but Shannon suggested that the best predictor is a person who speaks English. Of course, a person is unlikely to be as deterministic as a machine, and repeating the experiment (assuming the person forgets the text from the first time) might not yield an identical result. So reconstructing the text might present a slight difficulty. But it is still a reasonable assumption that a person approximates an optimal predictor.

Given a sequence of integers corresponding to a text, we can count the frequency of each number. Let

Since the text and the sequence of numbers can be reconstructed from each other, their entropies must be the same. The largest the entropy can be for the sequence of numbers is when these numbers are independent. In this case, the entropy is $-\sum _{i=1}^{26}{q}_i{log}_2(q_i)$. However, the numbers are probably not independent. For example, if there are a couple consecutive 1s, then perhaps the predictor has guessed the rest of the word, which means that there will be a few more 1s. However, we get an upper bound for the entropy, which is usually better than the one we obtain using frequencies of letters. Moreover, Shannon also found a lower bound for the entropy. His results are

Actually, these are only approximate upper and lower bounds, since there is experimental error, and we are really considering a limit as $N\to \mathrm{\infty }$.

These results allow an experimental estimation of the entropy of English. Alice chooses a text and Bob guesses the first letter, continuing until the correct guess is made. Alice records the number of guesses. Bob then tries to guess the second letter, and the number of guesses is again recorded. Continuing in this way, Bob tries to guess each letter. When he is correct, Alice tells him and records the number of guesses. Shannon gave Table 20.1 as a typical result of an experiment. Note that he included spaces, but ignored punctuation, so he had 27 possibilities: There are 102 symbols. There are seventy-nine 1s, eight 2s, three 3s, etc. This gives

Table 20.1 Shannon’s Experiment on the Entropy of English

The upper bound for the entropy is therefore

Note that since we are using $0{log}_{2}0=0$, the terms with $q_i=0$ can be omitted. The lower bound is

A reasonable estimate is therefore that the entropy of English is near 1, maybe slightly more than 1.

If we want to send a long English text, we could write each letter (and the space) as a string of five bits. This would mean that a text of length 102, such as the preceding, would require 510 bits. It would be necessary to use something like this method if the letters were independent and equally likely. However, suppose we do a Huffman encoding of the message $1\text{,}1\text{,}1\text{,}5\text{,}1\text{,}1\text{,}2\text{,}\dots$ from Table 20.1. Let

All other numbers up to 27 can be represented by various combinations of six or more bits. To send the message requires

which is 1.68 bits per letter.

Note that five bits per letter is only slightly more than the “random” entropy 4.75, and 1.68 bits per letter is slightly more than our estimate of the entropy of English. These agree with the result that entropy differs from the average length of a Huffman encoding by at most 1.

One way to look at the preceding entropy calculations is to say that English is around 75% redundant. Namely, if we send a long message in standard written English, compared to the optimally compressed text, the ratio is approximately 4 to 1 (that is, the random entropy 4.75 divided by the entropy of English, which is around 1). In our example, we were close, obtaining a ratio near 3 to 1 (namely 4.75/1.68).

Define the redundancy of English to be

Then $R$ is approximately $0.75$, which is the 75% redundancy mentioned previously.