COMPUTING SCIENCE

# Randomness as a Resource

# The Empyrean and the Empirical

As a practical matter, reserves of randomness certainly appear adequate to meet current needs. Consumers of randomness need not fear rolling blackouts this summer. But what of the future? The great beacon of randomness proposed by Rabin and Ding would require technology that remains to be demonstrated. They envision broadcasting 50 billion random bits per second, but randomness generators today typically run at speeds closer to 50 kilobits per second.

The prospect of scaling up by a factor of a million demands attention to quality as well as quantity. For most commodities, quantity and quality have an inverse relation. A laboratory buying milligrams of a reagent may demand 99.9 percent purity, whereas a factory using carloads can tolerate a lower standard. In the case of randomness, the trade-off is turned upside down. If you need just a few random numbers, any source will do; it’s hard to spot biases in a handful of bits. But a Monte Carlo experiment burning up billions of random numbers is exquisitely sensitive to the faintest trends and patterns. The more randomness you consume, the better it has to be.

Why is it hard to make randomness? The fact that maintaining perfect *order* is difficult surprises no one; but it comes as something of a revelation that perfect *disorder* is also beyond our reach. As a matter of fact, perfect disorder is the more troubling concept—it is hard not only to attain but also to define or even to imagine.

The prevailing definition of randomness was formulated in the 1960s by Gregory J. Chaitin of IBM and by the Russian mathematician A. N. Kolmogorov. The definition says that a sequence of bits is random if the shortest computer program for generating the sequence is at least as long as the sequence itself. The binary string 101010101010 is not random because there is an easy rule for creating it, whereas 111010001011 is unlikely to have a generating program much shorter than "print 111010001011." It turns out that almost all strings of bits are random by this criterion—they have no concise description—and yet no one has ever exhibited a single string that is certified to be random. The reason is simple: The first string certified to have no concise description would thereby acquire a concise description—namely that it’s the first such string.

The Chaitin-Kolmogorov definition is not the only aspect of randomness verging on the paradoxical or the ironic. Here is another example: True random numbers, captured in the wild, are clearly superior to those bred in captivity by pseudo-random generators—or at least that’s what the theory of randomness implies. But Marsaglia has run the output of various hardware and software generators through a series of statistical tests. The best of the pseudo-random generators earned excellent grades, but three hardware devices flunked. In other words, the fakes look more convincingly random than the real thing.

To me the strangest aspect of randomness is its role as a link between the world of mathematical abstraction and the universe of ponderable matter and energy. The fact that randomness requires a physical rather than a mathematical source is noted by almost everyone who writes on the subject, and yet the oddity of this situation is not much remarked.

Mathematics and theoretical computer science inhabit a realm of idealized and immaterial objects: points and lines, sets, numbers, algorithms, Turing machines. For the most part, this world is self-contained; anything you need in it, you can make in it. If a calculation calls for the millionth prime number or the cube root of 2, you can set the computational machinery in motion without ever leaving the precincts of mathland. The one exception is randomness. When a calculation asks for a random number, no mathematical apparatus can supply it. There is no alternative but to reach outside the mathematical empyrean into the grubby world of noisy circuits and decaying nuclei. What a strange maneuver! If some purely mathematical statement—say the formula for solving a quadratic equation—depended on the mass of the earth or the diameter of the hydrogen atom, we would find this disturbing or absurd. Importing randomness into mathematics crosses the same boundary.

Of course there is another point of view: If we choose to look upon mathematics as a science limited to deterministic operations, it’s hardly a surprise that absence-of-determinism can’t be found there. Perhaps what is really extraordinary is not that randomness lies outside mathematics but that it exists anywhere at all.

Or does it? The savants of the 18th century didn’t think so. In their clockwork universe the chain of cause and effect was never broken. Events that appeared to be random were merely too complicated to submit to a full analysis. If we failed to predict the exact motion of an object—a roving comet, a spinning coin—the fault lay not in the unruliness of the movement but in our ignorance of the laws of physics or the initial conditions.

The issue is seen differently today. Quantum mechanics has cast a deep shadow over causality, at least in microscopic domains. And "deterministic chaos" has added its own penumbra, obscuring the details of events that might be predicted in principle, but only if we could gather an unbounded amount of information about them. To a modern sensibility, randomness reflects not just the limits of human knowledge but some inherent property of the world we live in. Nevertheless, it seems fair to say that most of what goes on in our neighborhood of the universe is mainly deterministic. Coins spinning in the air and dice tumbling on a felt table are not conspicuously quantum-mechanical or chaotic systems. We choose to describe their behavior through the laws of probability only as a matter of convenience; there’s no question the laws of angular momentum are at work behind the scenes. If there is any genuine randomness to be found in such events, it is the merest sliver of quantum uncertainty. Perhaps this helps to explain why digging for randomness in the flinty soil of physics is such hard work.

© Brian Hayes

EMAIL TO A FRIEND :

**Of Possible Interest**

**Engineering**: The Story of Two Houses

**Letters to the Editors**: The Truth about Models

**Spotlight**: Briefings