A LITTLE randomness goes a long way. It can turn us into millionaires if lottery numbers come up right or kill us from cancer caused by a random mutation of our DNA. Governments rely on it for encoding their secret messages, while technologists use it for computer programming and robotic control. And randomness is also helping scientists answer tough questions from the behaviour of comets to the structure of advanced materials.
But, despite this growing enthusiasm for the use of randomness to solve problems in science and technology, there is an ambivalence in our relationship with it. To make use of randomness, we have to understand it, and be able to produce it on demand. But despite our constant exposure to the effects of randomness, few of us have a good grip on what it is, or how it behaves, still less how to generate it.
Our uneasy attitude to randomness is probably to do with the human penchant for spotting patterns. The brain has an architecture ideal for picking out a person in a crowd, or linking together disparate events 鈥� abilities that have obvious evolutionary advantages. 鈥淗umans want order 鈥� and they will impose order even when it is not there,鈥� says Norman Ginsburg, emeritus professor of psychology at McMaster University, Ontario, who has made a study of how well humans simulate randomness.
Advertisement
This love of order can be a severe handicap when you鈥檙e dealing with random phenomena. Take the apparently simple task of writing down a sequence of 100 鈥渞andom鈥� numbers. In research published recently in the journal Perceptual and Motor Skills, Ginsburg reported that volunteers had serious problems making their numbers genuinely random. In particular, they tended to avoid repeating numbers and having sequences like 15, 16, 17. They also disliked using numbers again until all the others had been 鈥済iven a go鈥�.
But true randomness has no memory of what went before, and it is entirely possible for small samples of random numbers to show fleeting bursts of apparent order. Where people go wrong, it seems, is in thinking that such snapshots of randomness have the characteristic lack of order that actually becomes apparent only in the very long run (see: 鈥淭he Laws of Lawlessness鈥�). Statistics from Britain鈥檚 National Lottery support this: in those weeks for which the numbers drawn contain a consecutive pair, most had no jackpot winner. By contrast, in one draw where the numbers were separated from each other by at least three other numbers, no fewer that 133 people shared the jackpot.
This failure to understand the effects of randomness can be far more serious than losing a quid or two on the lottery. Suppose some random event 鈥� a case of some rare infectious disease, say 鈥� rears its head on average 12 times a year. Without thinking much about it, one might then expect a typical year to produce one case a month. In fact, probability theory shows that such an even spread will be seen on average just once every 164 000 years. The vast majority of years will contain clusters of cases in some months, and nothing at all in others.
Gathering clusters
When the flesh-eating disease necrotising fasciitis flared up in Gloucestershire in May last year, both the media and medical experts feared an epidemic was about to strike. Neighbouring health authorities were put on alert, and a few more cases duly showed up. Yet by the end of the month it was clear that the 鈥渆pidemic鈥� was not going to materialise. In retrospect, it appears to have been no more than a clustering of the otherwise random series of outbreaks of this rare bacterial disease.
鈥淭his episode showed the need to be very careful when reading significance into events we see around us,鈥� says probability expert David Balding at Queen Mary and Westfield College, London. 鈥淲hat tends to be overlooked is all those random outbreaks where not much happened, and so no one noticed. Inevitably, among all these there will be occasional extreme cases which then seem significant.鈥�
Humans may be bad at understanding and generating randomness, yet the need to conjure it on demand has never been greater. Nature is replete with manifestations of randomness, from the jitterings of Brownian motion to the scattering of comets by a star鈥檚 gravitational field. Given a reliable source of random numbers, a supercomputer can simulate these phenomena and work out, say, the likelihood of a collision between a planet and a stray comet.
Diverse range
Computer scientists are also finding that many otherwise clear-cut problems are best attacked by methods that include a random element. These 鈥渞andomised algorithms鈥� are being used in areas as diverse as finding factors of huge numbers, controlling the movement of a robot arm, or even as a fast way of checking long mathematical proofs (鈥淭he easy way to check hard maths鈥�, 快猫短视频, 8 May 1993).
鈥淔or many applications, a randomised algorithm is the simplest algorithm available, or the fastest 鈥� or both,鈥� says Rajeev Motwani of Stanford University, California, who with Prabhakar Raghavan at IBM鈥檚 Thomas J. Watson Research Center has written the first textbook on these methods, due out later this year.
A key advantage of randomised algorithms, says Motwani, is their ability to cut through the messy complexity of real-world problems. He cites the example of trying to work out the best paths for dispatching instructions to the many microprocessors in a parallel-processing computer. Using a 鈥渄eterministic鈥� routeing algorithm 鈥� one that follows a fixed, totally predictable recipe 鈥� the number of steps needed to route instructions among n processors increases as the square root of n. The number of steps needed by a randomised approach, however, rises much more slowly 鈥� as log n 鈥� thus making it far more efficient for large networks.
Raghavan and Motwani, working with Lydia Kavraki and Jean-Claude Latombe at Stanford, have recently attacked another of those messy, all too real problems 鈥� directing a seven-jointed robot arm to go from A to B, avoiding objects on the way. 鈥淭his turns out to be a terribly difficult problem,鈥� says Motwani. 鈥淚t is essentially equivalent to finding a Path between two points in a seven-dimensional space with a multitude of 鈥榟oles鈥� 鈥� forbidden regions 鈥� of complex shapes that cannot be entered.鈥�
Seventh heaven
The Stanford team tackled the problem using an approach originally proposed by Kavraki and Latombe: randomly choosing points called 鈥渕ilestones鈥� within the seven-dimensional space, and forming paths between them that dodge the forbidden regions. The result is a multidimensional map of allowable routes. Getting from A to B then becomes simply a matter of choosing milestones closest to A and B on this map, and following the path between them.
But the central paradox is never far away: these techniques require repeatable, reliable, genuine randomness on tap, but neither humans nor machines can provide it. As the American mathematician and computer pioneer John von Neumann once said: 鈥淎nyone who considers arithmetical methods of producing random numbers is, of course, in a state of sin.鈥� Yet even he couldn鈥檛 resist the temptation to try, coming up with the fairly hopeless 鈥渕id-square鈥� method, where a random starting number is squared, and its middle few digits taken as the 鈥渟eed鈥� for the next random number.
In fact, ways of getting around the paradox have been sought since the advent of modern computers. In 1949, the British computer pioneer Alan Turing developed a black box that could be added to a computer as a source of genuine randomness. It exploited the 鈥渘oise鈥� created by the random movement of electrons in electronic circuitry 鈥� an idea still used today by ERNIE 3, the electronic device used to generate the winning numbers for Britain鈥檚 premium bonds.
But while the output from such devices is truly random, it has some major failings. For a start, it is not repeatable: if someone wants to replicate results based on it, the same sequence of random numbers cannot be conjured up again on demand. Furthermore, without constant, detailed checking 鈥� for example, that there are roughly the same number of odd and even digits, and that the probability of odd numbers following even numbers is about the same as getting any other permutation 鈥� it can be difficult to ensure that some quirk has not slipped in, skewing the sequence away from true randomness.
This problem of repeatability has led to the development of deterministic sources of 鈥減seudorandomness鈥�: mathematical recipes that give repeatable results virtually indistinguishable from the real thing. Some are very simple, such as the decimal expansion of 1/P, where P is a certain type of prime number. If P is chosen correctly, the decimal expansion will generate P-1 random digits before cycling again. For example, if P=23, the result is a nicely distributed sequence of 22 digits beginning 0,4,3,4,7,8,2,6 and ending 1,7,3,9,1,3.
The most commonly used source of random numbers is the so-called linear congruence generator, in which a 鈥渟eed鈥� number, X(0), is used to generate a random number X(1) by being multiplied by a constant, added to another constant, and the remainder taken when it is divided by yet another constant. Expressed mathematically, this translates to X(1) = (AX)(0)+B) modulo C, with the formula being repeated using X(1) as the seed to create X(2) and so on. The key to mimicking randomness this way is to find values of A, B and C that give an output passing statistical tests of randomness.
But as ever with randomness, there are some nasty surprises waiting for the unwary. In the early 1970s, many university mainframes used a random number recipe known as RANDU, a linear congruence generator with A = 65539, B = 0 and C = 231 whose output certainly looked random. Detailed statistical tests, however, showed subtle flaws that turned out to be fundamental, with too much correlation in its output.
Wrong recipe
鈥淚t should never have been used,鈥� says Donald Knuth at Stanford University, who is a leading authority on random number generators. 鈥淚ts very name 鈥� RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists.鈥�
And he stresses that it is just too dangerous to rely on any individual random number generator. 鈥淢any people 鈥� including myself and I ought to know better 鈥� have been burnt by placing too much faith in a method known to have only one or two of the important characteristics needed for randomness in sensitive applications.鈥�
Powerful backing for Knuth鈥檚 warnings emerged in 1993 during work by David Landau and colleagues at the University of Georgia on a well-known problem in solid-state physics, known as the Ising problem, that involves calculating the temperature below which certain materials become magnetic. During their research, the team developed a computer simulation of atoms making up the material, using random numbers to decide whether a specific atom flipped into a particular magnetic state. Alarmingly, they discovered that the answers they got depended on which random number generator they used. An old, simple and slow linear congruence generator gave sensible results for the transition temperatures, unlike those from a new, fast and supposedly better generator (快猫短视频, Science, 24 April 1993).
鈥淭hey failed to note that the generator was specifically designed for speed and convenience in PCs, using only subtraction in single-precision floating-point arithmetic,鈥� says George Marsaglia of Florida State University, co-inventor of the new generator. Echoing Knuth, he adds: 鈥淭he generator in question was not suited to the extensive sampling that the lsing problem requires.鈥� Even so, Marsaglia doubts that there are many seriously flawed simulation results lurking unrecognised in the published literature. 鈥淎 random number generator is like sex,鈥� he says. 鈥淲hen it鈥檚 good, it s wonderful 鈥� and when it鈥檚 bad, it鈥檚 still pretty good.鈥�
Spy holes
While Marsaglia鈥檚 sanguine view may be true in science, any margin of error is unacceptable in the most demanding of all applications of randomness: cryptology, the black art of secret communications. Mathematicians working at Britain鈥檚 GCHQ in Cheltenham, like their counterparts with other governments, know from bitter experience that they must understand every quirk and nuance of their random number generators. If they fail, the results can change the course of history.
The connection between cryptology and randomness was forged almost 80 years ago by Joseph Mauborgne, head of research at the US Army Signal Corps during the First World War. His idea was to combine a message text with a stream of random numbers, producing an unintelligible cipher text. Now known as the 鈥渙ne-time pad鈥� system, after the tiny pads of random numbers used by spies, it remains the only provably unbreakable cipher system.
Yet despite this apparently unassailable advantage over all other cipher systems, the one-time method is only rarely used. The reason can be traced yet again to the central paradox of random-number generation: true randomness has no mathematical recipe.
The ideal one-time pad consists of random numbers generated by a true source of randomness, such as electronic noise. But because such sources do not produce repeatable results, identical copies of the random number pads have to be handed out to all who use them. One mistake, such as reuse of the pads, or their theft, and all security is blown.
The Soviet intelligence service learnt this the hard way shortly after the Second World War. Overloaded with work, its cryptology department inadvertently allowed some one-time pads to be used twice. The officer responsible for the blunder was shot, but the damage had been done. Analysing intercepted messages using the repeated random key, American code-breakers were able to expose such famous spies as Klaus Fuchs, Julius and Ethel Rosenberg and Donald Maclean.
Local loophole
To avoid the dangers of captured or reused one-time pads, intelligence services have developed algorithms that generate random numbers 鈥渙n site鈥�. They typically use nonlinear circuitry that produces extremely long-period sequences of bits 鈥� ones and zeros 鈥� which pass stringent statistical tests of randomness.
Yet for all this, they are still not truly random. The paradox of random number generation can never be evaded, and once again, it is the Soviets who have experienced its worst consequences. During the attempted coup in August 1991, the head of the KGB, Vladimir Kryuchov, and defence minister Dmitri Yazov communicated with each other and their co-conspirators using the most sophisticated Soviet cipher equipment. Even so, American cryptologists were able to exploit the subtle nonrandomness in the cipher, and President George Bush reportedly ordered them to feed this information to the West鈥檚 ally, Boris Yeltsin.
According to the American investigative journalist Seymour Hersh, American intelligence experts are still incensed by the decision to let Yeltsin in on the secret of American cryptology. Quite how the deciphering was done remains unclear to outsiders; ironically, a randomised algorithm known as genetic programming, which 鈥渂reeds鈥� good solutions from an initially random selection, is one possibility.
That it was done at all will, however, be no surprise to those familiar with the fickle nature of randomness. It is simply another demonstration that, like a wilful sprite, randomness is capable of astonishing feats 鈥� and nasty tricks. The bitter experiences of everyone from lottery players to world leaders shows that only the foolish would claim to be its master.
The laws of lawlessness
ONE of the more bizarre properties of randomness is that its lawlessness follows laws. The most familiar of these, the 鈥渓aw of large numbers鈥�, was first stated by Swiss mathematician Jakob Bernoulli in 1713. Roughly speaking, it shows that the longer a random process operates, the more closely the observed frequency of events will match theoretical expectation. Thus, although in a small number of tosses of a coin there may be a preponderance of heads, in the long run the proportion of heads to tails will approach the expected 50:50 split. The crucial words here are 鈥減roportion鈥� and 鈥渋n the long run鈥�: as many gamblers have learnt to their cost, the outcome of any individual toss cannot be predicted.
Dig deeper into randomness, and more curiosities appear. Consider a random process with only a small chance of producing a particular outcome, but with plenty of opportunities to act. An example is the fall of V2 rockets on London: they fell in drove, yet each had only a small chance of hitting a specific area. Such processes obey a law, formulated by French mathematician Sim茅on Denis Poisson in 1837.
In the specific case of V2 rockets, suppose London is divided up into squares of equal area. The proportion of them, P, left untouched by the random falls of V2s is approximately e鈭�2, where e is the base of natural logarithms and A is the average number of hits per region. Using real wartime figures (A=0.932 and P=39.8 per cent), the random fall of V2s can be used to produce a value of e of: 2.690 鈥� within about 1 per cent of the standard value.
Even the famous number 蟺 can be extracted from randomness. Analytical number theory shows that the probability of a pair of random numbers having no common factors apart from 1 is 6/蟺2, or about 61 per cent. In a recent issue of Nature (20 April, p 681), I showed how to turn the scattering of the hundred brightest stars in the night sky into a million random number pairs. By counting how many pairs have no common factors, it is possible to extract an astonishingly accurate 鈥渃elestial鈥� value of 蟺 鈥� 3.12772, which is within half a per cent of the standard value.