Ivars Peterson - The Jungles of Randomness: A Mathematical Safari

Copyright 1998

ISBN 0-471-16449-6

To my mother,

Zelma Peterson,

for her fascination with the way things work.

Preface: Infinite Possibility, ix

The Die Is Cast 1

Sea of Life 21

Shell Game 45

Call of the Firefly 67

Different Drums 87

Noise Police 109

Complete Chaos 127

Trails of a Wanderer 147

Gambling with Numbers 167

Appendix, 205 Bibliography, 209

All mimsy were the borogoves, And the mome raths outgrabe.

-Lewis Carroll (1832-1898), "Jabberwocky"

An ape sits hunched over a keyboard. A long hairy finger bangs a key, and the letter a appears on the computer screen. Another random stab produces n, then a space, then a, p, and e. That an ape would generate this particular sequence of characters is, of course, highly improbable. In the realm of random processes, however, any conceivable sequence of characters is possible, from utter gibberish to the full text of this book.

The seemingly infinite possibilities offered by randomness have long intrigued me. Years ago when I was a high school student, I came across a provocative statement by Arthur Stanley Eddington (1882-1944), a prominent astronomer and physicist. "If an army of monkeys were strumming on typewriters, they might write all the books in the British Museum," he noted.

Eddington wanted to emphasize the improbability of such an outcome, and his remark was meant as an example of something that could happen in principle but never in practice. I was left with the indelible image of a horde of monkeys forever pecking away at typewriters, generating the world's literature.

The preface that you are now reading contains nearly two thousand words, or roughly ten thousand characters, including spaces. An

ape at a keyboard can choose among twenty-six letters and about fourteen other keys for punctuation, numbers, and spaces. Thus, it has one chance in forty of hitting a as the first letter, one chance in forty of picking n next, and so on. To write the entire preface, the ape would have to make the correct choice again and again. The probability of such an occurrence is one in forty multiplied by itself ten thousand times, or one in 4010,000. That figure is overwhelmingly larger than the estimated number of atoms in the universe, which is a mere 1080.

One would have to wait an exceedingly long time before a member of a troop of apes happened to compose this book by chance, let alone the millions of volumes in the Library of Congress and the British Museum.

Sifting through the troop's vast output to find the flawless gems, including original works of significant merit, would itself be a notably frustrating, unrewarding task. By eschewing randomness, a human author, on the other hand, can generate a meaningful string of characters far more efficiently than an ape, and the output generally requires considerably less editing.

Most people, including mathematicians and scientists, would say that they have a good idea of what the word random means. They can readily give all sorts of examples of random processes, from the flipping of a coin to the decay of a radioactive atomic nucleus. They can also list phenomena in which chance doesn't appear to play a role, from the motion of Earth around the sun to the ricochets of a ball between the cushions of a billiard table and the steady vibrations of a violin's plucked string.

Often, we use the word random loosely to describe something that is disordered, irregular, patternless, or unpredictable. We link it with chance, probability, luck, and coincidence. However, when we examine what we mean by random in various contexts, ambiguities and uncertainties inevitably arise. Tackling the subtleties of randomness allows us to go to the root of what we can understand of the universe we inhabit and helps us to define the limits of what we can know with certainty.

We think of flipping a coin as a way of making a blind choice, yet in the hands of a skilled magician the outcome may be perfectly predictable. Moreover, a process governed entirely by chance can lead to a completely ordered result, whether in the domain of monkeys pounding on keyboards or atoms locking into place to form a crystal. At the same time, a deterministic process can produce an unpredictable outcome, as seen in the waywardness of a ball rebounding

within the confines of a stadium-shaped billiard table or heard in the screeches of an irregularly vibrating violin string. We can even invent mathematical formulas to generate predictable sequences of numbers that computers can then use to simulate the haphazard wanderings of perfume molecules drifting through the air.

It's useful to distinguish between a random process and the results of such a process. For example, we think of typing monkeys as generators of random strings of characters. If we know that such a random process is responsible for a given string, we may be justified in labeling or interpreting the string itself as random.

However, if we don't know the source of a given string, we are forced to turn to other methods to determine what, if anything, the string means. Indeed, reading itself involves just such a search for meaning among the lines of characters printed on a page or displayed on a computer screen.

Consider the passage from Lewis Carroll's poem "Jabberwocky" that starts off the preface. From the presence of a few familiar words, the pattern of spaces, and the vowel-consonant structure of the remaining words, we would surmise that the author intended those lines to mean something, even though we don't understand many of the words. If the same passage were to come from typing monkeys, however, we might very well reject it as gibberish, despite the fragments of structure and pattern.

Similarly, in flipping a coin we know from experience (or theory) that we're likely to obtain an equal number of heads and tails in a long sequence of tosses. So if we see twenty-five heads in a row, it might be the legitimate though improbable result of a random process. However, it might also be advisable to check whether the coin is fair and to find out something about the fellow who's doing the flipping. The context determines how we interpret the data.

At the same time, just because we happen to see a sequence of roughly equal numbers of heads and tails doesn't mean that the results arise from tosses of a fair coin. It's possible to program a computer with a numerical recipe that involves no randomness yet gives the same distribution of heads and tails. Thus, given an arbitrary sequence of heads and tails, there's really no way to tell with confidence whether it's the result of a random process or it's been generated by a formula based on simple arithmetic.

"From a purely operational point of view... the concept of randomness is so elusive as to cease to be viable," the mathematician Mark Kac said in a 1983 essay on the nature of randomness. Kac also took a critical look at the different ways in which we sometimes interpret randomness in different contexts.

For example, in the book Chance and Necessity, the biologist Jacques Monod (1910-1976) suggested that a distinction be made between "disciplined" chance, as used in physics to describe, say, radioactive decay, and

"blind" chance. As an example of the latter, he cited the death of a doctor who, on his way to see a patient, was killed by a brick that fell from the roof of a building.