Additive Congruential Random Number Generators | Source code for programmers who wish to test the randomness of a random number generator | |||

## index |
||||

## Back to Deley's Homepage |

In the previous sections of this chapter, we have defined a model of an information source, and brought out some simple properties of our model. It is of some interest to investigate how closely such a model approximates the physical process of information generation. A particularly important case of information generation is the generation of a message composed of English words. In this section we show how the generation of such a message may be approximated by a sequence of successively more and more complicated information sources.

Let us restrict ourselves to a set of 27 symbols—the 26 English
letters and a space. The simplest possible source using this alphabet
is a zero-memory source with all 27 symbols equally probable.
The entropy of this source is easily calculated.

H(S) | = | log 27 |

= | 4.75 bits/symbol |

A typical sequence of symbols emitted by such a source is shown
in Figure 2-6. We refer to this sequence as the zeroth approximation to English.

| ||

Figure 2-6. Zeroth approximation to English. |

Note that there is no perceptible structure to this sequence and
it is not possible to identify it as coming from any particular
language using the same alphabet. A better approximation to
English may be obtained by employing the actual probabilities
of the symbols used (Table 2-2). The entropy of a zero-memory
source with probabilities given in Table 2-2 is

H(S) | = | |

= | 4.03 bits/symbol |

Symbol | Probability | Symbol | Probability |
---|---|---|---|

Space | 0.1859 | N | 0.0574 |

A | 0.0642 | O | 0.0632 |

B | 0.0127 | P | 0.0152 |

C | 0.0218 | Q | 0.0008 |

D | 0.0317 | R | 0.0484 |

E | 0.1031 | S | 0.0514 |

F | 0.0208 | T | 0.0796 |

G | 0.0152 | U | 0.0228 |

H | 0.0467 | V | 0.0083 |

I | 0.0575 | W | 0.0175 |

J | 0.0008 | X | 0.0013 |

K | 0.0049 | Y | 0.0164 |

L | 0.0321 | Z | 0.0005 |

M | 0.0198 |

A typical sequence of symbols emitted by this source is given in
Figure 2-7.

| |||

Figure 2-7. First approximation to English. |

Though the sequence shown here cannot qualify as good English,
it does exhibit some of the structure of the language. (Compare
this with our zeroth approximation.) The "words" of this approximation
are, for the most part, of reasonable length, and the proportion
of vowels to consonants seems more realistic. We may
improve upon the source which generated the first approximation
by using a first-order Markov source with the appropriate conditional
symbol probabilities. These probabilities are given by Pratt (1942).

H(S) | = | |

= | 3.32 bits/symbol |

It is possible to generate a typical sequence of symbols out of such
a first-order Markov source by using the probabilities given in Pratt.
Shannon, however, has pointed out a much cleverer method. Ordinary
English text has the probabilities we seek contained in it.
We therefore open a book and select a letter at random, say U.
Next, we skip a few lines, read until we come to the first U and
select the first letter after the U—in this case it was R. Again we
skip a few lines, read until we come to an R, and select the next
letter. Using this procedure, we constructed a second approximation to English (Figure 2-8).

| |||

Figure 2-8. Second approximation to English. |

Note how the English flavor of the sequence makes itself felt in the second approximation. We would have little trouble in identifying this sequence as an approximation to English rather than, say, French.

We can apply Shannon's method to construct even better approximations
to English. By selecting letters from a book according to
the two preceding letters we can construct a typical sequence from a
second-order Markov source approximating English.

| |||

Figure 2-9. Third approximation to English. |

Shannon (1951) has estimated the entropy of the source corresponding to the sequence shown in Figure 2-9 as 3.1 bits per symbol. Using other methods, he has estimated that the entropy of English, taking into account all the preceding text, is between 0.6 and 1.3 bits per symbol.

It is possible to extend the process used above to generate
typical sequences out of *m*th-order (*m* ≥ 3) Markov sources having
the symbol probabilities of English. The construction of such
sequences, however, becomes impractical for *m* greater than 2.
Instead Shannon jumped to a zero-memory information source
with the English *words* rather than the English letters as the output
symbols. The probabilities of occurrence of the various words are
approximately the same as in English text. Shannon (1948)
obtained the approximation shown in Figure 2-10.

| |||||

Figure 2-10. Fourth approximation to English. |

An even more complicated approximation to English can be
constructed by letting the probability that a given word is selected
depend upon one preceding word. The source corresponding to
this approximation is a first-order Markov source with the English
words as symbols. Shannon (1948) also constructed a typical
sequence from this type of source (Figure 2-11).

| |||||

Figure 2-11. Fifth approximation to English. |

It is interesting to note that this sequence is a reasonable approximation to the sort of output one might expect from a very excited and quite incoherent speaker. The fact that we can approximate (at least to some extent), as complicated an information source as an English speaker by the simple models of zero-memory and Markov sources is encouraging. Many information sources found in realistic communication problems are of a much simpler nature, and we may expect that our models provide better approximations to reality in those cases.

For more on creating random English sentences see
The Language Instinct: How the Mind Creates Langauge
by Steven Pinker, chapter 4: **How Language Works.**

A striking illustration of the differences in several Western
languages may be obtained by constructing sequences using the
statistics of these languages. We have done this for three languages,
and the sequences obtained are given in Figures 2-12 to 2-14. As
before, the first approximation corresponds to a sequence out of a
zero-memory source; the second approximation from a first-order
Markov source; and the third approximation from a second-order
Markov source.

| |||

(a) First approximation to French | |||

| |||

(b) Second approximation to French | |||

| |||

(c) Third approximation to French | |||

Figure 2-12. A series of approximations to French. |

| |||

(a) First approximation to German | |||

| |||

(b) Second approximation to German | |||

| |||

(c) Third approximation to German | |||

Figure 2-13. A series of approximations to German. |

| |||

(a) First approximation to Spanish | |||

| |||

(b) Second approximation to Spanish | |||

| |||

(c) Third approximation to Spanish | |||

Figure 2-14. A series of approximations to Spanish. |

As a final example in this series, we present a series of approximations (Figure 2-15)
to another Western language and leave it to the reader to determine which language.

| |||

(a) First approximation to ? | |||

| |||

(b) Second approximation to ? | |||

| |||

(c) Third approximation to ? | |||

Figure 2-15. A series of approximations to ? |

*Note* 4. In addition to generating words of a language from an artificial
source, as illustrated in Section 2-8, it is possible to generate musical compositions.
Pinkerton (1956) has used this method of musical composition. Pierce (1961)
devotes several pages to the generation of such music; perhaps the ultimate
in artistic information theory is displayed in some passages from the
"Illiac Suite for String Quartet" reproduced in Pierce (1957, p. 260).

Pinkerton, R. C. (1956):Information Theory and Melody,

Pratt, F. (1942): "Secret and Urgent," Doubleday & Company, Inc., Garden City, N.Y.

Reza, F. M. (1961): "An Introduction to Information Theory," McGraw-Hill Book Company, Inc., New York.

The above is section 2-8, pp 33-40, from the book INFORMATION THEORY AND CODING by Norman Abramson, Associate Professor of Electrical Engineering, Stanford University. McGraw-Hill Book Company, Inc. 1963 McGraw-Hill electronic Sciences Series.

Additive Congruential Random Number Generators | Source code for programmers who wish to test the randomness of a random number generator | |||

## index |
||||

## Back to Deley's Homepage |