Chapter 10
RANDOM NUMBERS
Johanna Davidson’s fascination with randomness dated back to her first course in probability and statistics. What she had found most intriguing was the fact that the teacher could not provide a satisfactory definition of “random” (or of “probability,” for that matter), even though notions such as “random variable” and “random sample” lie at the heart of the theory. She would later learn that this was not due to the lecturer’s imperfect knowledge of the subject, but rather to the difficulty of specifying what, for example, a random sequence of 0s and 1s precisely is. In fact, this question has a long history and no definitive answer.
A simple—if not very practical—way of generating a string of 0s and 1s in a random fashion is to repeatedly flip a perfectly balanced (or “fair”) coin and to write down the outcomes as “1” for heads, and “0” for tails. Thus, after ten tosses of the coin, we may have obtained the sequence
0100110010
whose binary digits (or bits) are totally unpredictable: the eleventh bit is equally likely to be 0 or 1, and the same is true for any subsequent bit. On the other hand, sequences that exhibit some kind of pattern or regularity, such as
0101010101 . . . or 011011100101 . . .
would not be considered random, for we can predict what the next bit will be. In the first sequence on page 69, 0s and 1s alternate, so the eleventh bit will certainly be 0, the twelfth will be 1, and so on. The other sequence is constructed by writing the numbers 0, 1, 2, 3, 4, 5, . . . in base 2, one after the other, that is, 0, 1, 10, 11, 100, 101, etc., so that we can tell what bit must appear in position n + 1 by looking at the first n bits.
Two fundamental questions regarding binary sequences are (1) deciding whether a given sequence of 0s and 1s is random or not, and (2) determining how to generate random sequences. Answers to these questions have become increasingly important with the pervasive use of computers to simulate complex phenomena, such as the interactions of subatomic particles, the evolution of galaxies, and the consequences of the malfunction of a nuclear reactor. Such simulations may require millions of random numbers a minute, and having a reliable source of these is crucial for the validity of the final results.
In 1992, Alan Ferrenberg and David Landau, physicists at the University of Georgia, and Joanna Wong from IBM were using a computer simulation to study the property of certain materials to suddenly enter into a magnetic state when cooled below some critical temperature. The atoms in a single layer are simulated by points on a grid, whose color represents the atom’s magnetic moment orientation (north or south). The simulation chooses atoms at random and decides whether they should remain in the same magnetic state or switch to the opposite state. The probability of a particular atom changing state depends on the state of its neighbors and the temperature. The computer program calculates this probability and then compares it with a random number between 0 and 1. If the random number is larger than the probability, the atom remains in its current state; otherwise it flips to the opposite state.
The program seemed to be working smoothly, except for one problem: the computer model consistently predicted the wrong temperature for the transition of the material to a magnetic state. The researchers finally tracked down the culprit: the program’s new random number generator. This generator was faster and used more advanced mathematics than conventional ones, and it had passed tests indicating that it produced sequences of numbers that were closer to genuine randomness than those obtained from standard generators. But, as they discovered, the new generator behaved worse in practice.
Johanna had read a report of the incident in Physical Review Letters. It was a confirmation of her own concerns about the possibility of hidden flaws in the random number generators on which most simulation programs rely. Her line of work as a systems analyst was not directly related to random numbers but dealt instead with network security—how to prevent intruders from breaking in and stealing or corrupting data stored in the network computers or otherwise disrupting their normal operation. But since randomly generated encoding keys are the most secure way to protect encrypted information, there might be a connection after all.
She had gotten in touch with Ferrenberg, who had told her that other scientists had contacted him with worries about their own simulations. “This is a warning bell,” Ferrenberg had said. “Unfortunately, it appears that ostensibly high-quality random number generators may lead to subtle but dramatic errors in some algorithms.”
Ferrenberg and his colleagues’ work in the physics of solids was mainly theoretical. But computer simulations were confidently and routinely applied to a variety of fields and situations, resulting in decisions that had practical implications well beyond the laboratory. Computer models were used to predict the consequences of global warming, to anticipate the force and the path of tornadoes, and to study the progression of epidemics; advanced computer programs could now simulate the detonation of a nuclear device on a supercomputer—a much more economical and safer alternative to an actual nuclear test.
Most of these computer simulations rely at some stage or another on the automatic generation of random numbers in order to incorporate the elements of chance and uncertainty present in the very fabric of physical phenomena. When billions of those random numbers are employed to simulate the evolution of a complex system, the accuracy of the final results may directly depend on the quality of the “randomness” built into the program. To make matters worse, as the incident reported by Ferrenberg illustrates, random number generators which seem to work well in test runs may turn out to be unreliable in practice or when used over long periods of time, and there may be no way of knowing in advance that the results of the simulation might be flawed. But what is a true random sequence, and how can we manufacture one?
Several definitions of “random sequence” were proposed in the first half of the twentieth century,* but none of these captured the essence of the concept. Finally, in 1965, Per Martin-Löf, a young Swedish mathematician, came up with a sophisticated definition that appears to be the right one. His definition can be better understood through its connection with a concept developed by the Russian mathematician Andrej Kolmogorov. In the 1970s, Kolmogorov defined the “complexity” of a finite binary sequence as the length of the shortest computer program that can print it. For example, a sequence of one million 1s has very small complexity, for there are very short programs that can be used to print it—for instance, in many computer languages, something of the form: “for i = 1 to 1,000,000, print ‘1.’ ” Such a program may be considered a “compressed” version of the given sequence. On the other hand, a sequence of 1,000,000 bits whose Kolmogorov complexity is 1,000,000 is totally “incompressible”: there is no shorter way of describing it than listing all its one million bits.
Now, “randomness” and “incompressibility” turned out to be equivalent concepts, that is: an infinite binary sequence is random (in Martin-Löf’s sense) precisely if it is incompressible. An immediate practical consequence of this result is that no computer program can generate a truly random binary sequence. The reason is simple: any sequence s whose bits are obtained by executing a computer program is automatically compressible (for the program is a compressed version of s) and hence it is nonrandom. It follows that all random number algorithms being used in computer programs are in fact only pseudo random, and not simply for lack of ingenuity on the part of the mathematicians who created them but due to the existence of an essential barrier inherent in the concept of “randomness” itself.
Johanna was aware of this theoretical obstacle, but had always felt that there might be a way to circumvent it. The situation was made even more puzzling by the fact that, even if “almost all” binary sequences are random, no algorithm or computer program could produce a single one of them. Randomness is everywhere and yet it is out of reach!
There was another aspect of reality, as Johanna knew well, where randomness was pervasive: the realm of quantum mechanics. In classical physics, determinism and causality reign, while probability is only a convenient way to make up for our incomplete knowledge of the acting causes. Even the outcome of a coin toss is in principle predictable: if we knew all the variables involved and their initial conditions, the final position of the coin would be completely determined by the equations of motion. In the quantum world, on the other hand, events occur at random, and probability is no longer a substitute for our imperfect knowledge of the underlying causes. There is no “cause” behind the decay of an atom from an excited state, only chance; and the “laws” governing the process merely express the probability of the event taking place at some particular moment. This was Max Born’s idea in the 1920s, fully confirmed by innumerable experiments since, but rejected at the time by Einstein. In a letter to Born he wrote that quantum mechanics was very imposing, but he was convinced that God did not throw dice.
On a bitterly cold morning in February 1998, Johanna Davidson woke up with a mild headache. A few minutes passed before she reluctantly crawled out of bed, pulled up the blinds, and looked out the window. Snow had been falling steadily over Boston since the day before, leaving the city half buried under a soft white mantle. In the street below, traffic was barely moving, while pedestrians struggled to walk in the fifteen-inch-deep snow that had accumulated on the sidewalks.
Johanna lived alone in a one-bedroom apartment on the second floor of a century-old brownstone building located in the fashionable Back Bay district of the city. A spacious kitchen with exposed brick walls, a fully equipped bathroom, and an oversized living room made up the rest of the unit.
Her morning headache was probably the result of a bit of alcohol overindulging the night before, but it could equally well have been due to the stormy and abrupt end of her evening out with Kevin—and of her having to face the prospect of yet another relationship hitting the rocks.
At thirty-four years old, Johanna was still in her prime. She had a graceful figure of medium height, curly brown hair, and a bright, intelligent face with a delicate nose and engaging gray eyes. Professionally, she was a successful computer consultant, traveled extensively on business, and had no financial worries, but in her sentimental life the “downs” largely outnumbered the “ups.” Not that she was really looking to get married and start a family. She wasn’t necessarily looking for that, but she would have preferred it to be her decision, instead of the choice being forced on her by default, for lack of a suitable partner.
She showered, fixed herself a bowl of cereal with plenty of milk, and took it with her into the living room. A good half of the spacious room was arranged as an office. The furniture included an old oak desk, two file cabinets, and a huge bookcase overflowing with books. On a large, sturdy table along one wall were two computers with wide-screen monitors, a laptop, a printer, and various other peripherals.
She sat down at one of the computers and logged on to a bulletin board on virus alert she had been running; she wanted to see if it was still up. Hackers had managed to shut it down a couple of times but this morning the site was working smoothly; the extra protection she had added seemed to be keeping intruders at bay. Then she checked her e-mail. There were five new messages—none of them from Kevin. Her face lit up when she saw the message from Andrew Stone. Andy, as he urged everyone to call him, was her former PhD thesis supervisor and lifelong mentor. Now a retired professor of computer science from McGill University, in Montreal, he was still as active as ever. Released from teaching and administrative duties, his seemingly inexhaustible energy now manifested itself through other channels.
She clicked the message open. Hi, Jo. Where are you this time? I thought you’d be interested to know that Norton Thorp has accepted my invitation to give a talk at our joint Math-Computer Sci. seminar. Hope to see you there. Love, Andy. Details of time and place followed.
Of course she was interested. Norton Thorp needed no introduction, and Johanna wondered how Andy had managed, even taking into account his considerable persuasive powers, to entice such a scientific superstar, a mathematician in a class of his own, to give a talk at McGill. To be sure, the university had an excellent reputation, and its department of mathematics probably ranked among the top twenty in North America. But Thorp enjoyed such an international celebrity standing that he was sought after by universities, research institutes, and scientific laboratories all over the world. Invitations to give a lecture, chair a conference, or deliver an opening address—not to mention requests for interviews and television appearances—would be bombarding him as steadily as spam e-mail. And yet, against all reasonable expectations, Thorp had decided to accept Andy’s invitation to come to Montreal.
Johanna was not about to miss the opportunity to hear him lecture and perhaps learn a thing or two about random number generation—a field, like so many others, to which Thorp had made significant contributions.
Her thoughts drifted toward her twin brother Jule, who was also a mathematician. She had been thinking of him often lately. Not that she was really worried, but Jule had been behaving in a strange way, beginning with his taking leave from the university for what he called “a special assignment” in Chicago. At first he was evasive as to the nature of his assignment, but when finally, at her insistence, he told her all about it, she couldn’t believe it. She thought the whole thing was crazy.