Playing anything just to roll the dice just one more time...

Understand randomness and you could win a Nobel prize, or clean up big time at the casino. So the stakes are high indeed for a tiny band of mathematicians who reckon they are beginning to crack it, says Dana Mackenzie

ONE DAY, while wasting time and money in your local casino, you notice that a computer-animated craps game is behaving in a strange way. For 100 consecutive rolls of the dice, the machine comes up with an odd number. Visions of a big payout dance in your head. Should you start betting on odd numbers? Or would that be superstitious nonsense?
Your dilemma reflects a problem that has mystified gamblers and mathematicians alike: how do you tell whether an individual event is random or has an underlying pattern. Randomness is all around us, in the motion of stock prices and atoms; yet it is maddeningly elusive. If you succeed in trapping it, it's no longer random.

Scientists are forever limited to living on the few islands of order in the vast sea of randomness, because they can only study what they can describe. A truly random event has no pattern to it and hence is indescribable. Or so it would seem, according to classical theories of randomness. But a revisionist view, called Kolmogorov complexity, is now beginning to turn that conventional wisdom upside down. Using this theory, mathematicians have found a curious thing: an area of their world where the normal roles are reversed, where randomness is entirely surrounded by order, rather like a lake surrounded by land.
Such a find is a huge breakthrough for mathematicians. Computer scientists even compare the discovery to the breakthroughs that led to quantum physics. It means that even if this lake of randomness is strictly off limits, it is possible to map its shores. Armed with such a map, they should be able to better explore the nature of randomness and to tackle hitherto unsolvable problems. And in the real world computer scientists, financial analysts and even gamblers could benefit.
The idea that makes all this possible dates back to the mid-1960s when the Soviet mathematician Andrei Kolmogorov and the Americans Roy Solomonoff and Gregory Chaitin hit upon a way of defining randomness. Their idea was that most numbers or sequences of digits (they amount to more or less the same thing in mathematical terms) are random in the sense that they contain no pattern. The big question was how to spot them, how to distinguish these numbers that by their very nature lack any distinguishing features.

Kolmogorov, Chaitin and Solomonoff defined the notion of the complexity of a number. Roughly speaking, the complexity of a sequence of digits is the length of the shortest computer program that prints that sequence and then stops running. A computer program can be written for any sequence of digits simply by issuing the command "PRINT" followed by the numbers in the sequence. So the Kolmogorov complexity of a sequence, as it later became known, is never more than the length of the sequence plus the number of bits it takes to encode the instruction "PRINT".
Of course, some nonrandom sequences can be printed by much shorter programs. The first billion digits of the number pi are not random because a short program can be written to generate them. And a sequence of one hundred is can be compressed into a program such as "PRINT 1 100 TIMES" -precisely because this sequence has a pattern. In fact, any number you can compress can't be random because it contains a pattern.

This leads to a straightforward definition of randomness. Kolmogorov and his colleagues defined a number as random if the shortest program for calculating its digits turns out to be about the same length as the number itself. Random numbers cannot be compressed. But as simple and appealing as this notion seems, determining the Kolmogorov complexity of a number is fraught with difficulty. Suppose you have a long sequence of digits and a program to generate it that is about the same length. Does that prove that your number is random? Absolutely not, since there could be a shorter program that also does the job that you don't know about and the number could be compressible in some hidden way. In fact, it turns out that you can never know whether you have the shortest program or not. Not only is it practically impossible to find the shortest program that computes a number, it's also theoretically impossible.

Pebbles in the Sky
That leaves mathematicians in a fix. It means they can only play with the small proportion of numbers that have some kind of pattern. The rest-the random numbers-are forever hidden since it is impossible to prove they really are random.
For this reason, Kolmogorov complexity remained more of a curiosity than a practical mathematical tool. But in the last few years Paul Vitanyi, an information theorist at the Centre for Mathematics and Computer Science and the University of Amsterdam, both in the Netherlands, and his long-time collaborator Ming Li at the University of Waterloo in Canada, have made huge progress in using Kolmogorov complexity. Their stunning result concerns a famous geometric problem set out in the first half of this century by the German mathematician Hans Heilbronn. If a number of pebbles (n) are placed inside a square and triangles are drawn between them, what arrangement of pebbles makes the smallest triangle as large as possible? (see Diagram). Mathematicians call the largest possible size of the smallest triangle the nth Heilbronn number.

The smallest triangle
Even with a small number of pebbles, the problem is extremely challenging. With five pebbles, the Heilbronn number turns out to be 0.l924... (meaning that the smallest triangle in this arrangement is 0.1924... times the size of the square). The sixth Heilbronn number is the size of the square. But even for as few as seven pebbles, the Heilbronn number is too difficult to calculate. Heilbronn suspected that for large numbers of pebbles, the Heilbronn number would be roughly proportional to 1/ n2, meaning that the smallest triangle in a configuration of 1000 pebbles would have an area no bigger than one-millionth the size of the square. But in 1982, experts in geometry proved that Heilbronn's guess was wrong and that the real power of n is somewhere between the numbers 8/7 and 2. But to this day, nobody knows exactly how to work out the correct power.
There is another version of this problem that has traditionally been even more difficult to crack. This is the one that Vitanyi and his colleagues have chosen to tackle. Instead of looking for the very best configuration of n pebbles, they asked what would happen if the pebbles fall at random in the square-how big is the smallest triangle formed in this case? This version has the added problem of randomness built in. If you decide to study an arrangement of pebbles, how do you know that it really is random?
Enter Li, Vitanyi and Tao hang of McMaster University in Hamilton, Ontario. They reasoned that although the answer itself must involve the notion of randomness, any tiny deviation away from this answer would contain some order and could therefore be spotted and eliminated using the ideas of Kolmogorov complexity. In this way, they could approach the answer from above and below by eliminating all the nonrandom possibilities until what is left must be random. In a sense, they would be mapping the shores of randomness without ever getting their feet wet.

'Mathematicians can only play with the small proportion of numbers that have some kind of pattern. The rest, the random numbers, are forever hidden since it is impossible to prove that they really are random'

At the heart of their approach is the idea that the positions of the pebbles can be encoded using a coordinate system inside the square. This means that any arrangement of pebbles can be represented by a sequence of numbers. If you can compress this sequence by writing a shorter program that produces the same sequence, then the arrangement cannot be random.

A pentacle...the sign of might
As in many mathematical proofs, the first step is to guess an answer and then try to prove it right. Vitanyi and his colleagues picked an answer and showed that if the spacing between the pebbles were larger than this, the pebbles would have to adopt a regular pattern as they were added to the square. Likewise, they showed that if the spacing were smaller, at least three pebbles would fall in a straight line. This extra information would allow the sequence of coordinates to be compressed and so it cannot be random. Having proved that the answer cannot be larger or smaller than the guess-having mapped the edge of randomness-the only other option is that the guess is correct.
Using this method, the team showed that the area of the smallest triangle is proportional to 1/n3 -no more, no less. So with 1000 pebbles randomly arranged in a square, the smallest triangle will have an area roughly one-billionth of the square's. In February they published the result on the Internet and it is currently being reviewed for publication.


The work represents an extraordinary achievement. Mathematicians now have a powerful way to make an exact statement about randomness. And not just about one random number "Random objects are all interchangeable since by definition they have no special properties that can be used to effectively select a proper subset of them. They are like a sea of water molecules which cannot be distinguished," says Vitanyi.
So the answer holds true for every random arrangement that it is possible to generate. In one giant leap, mathematicians have gone from complete ignorance of every random sequence to being able to say something about all of them. And since the vast majority of numbers are random, this is an astonishing achievement. For this reason, Vaughan Pratt, a leading expert on the complexity of computer systems at Stanford University and one of the founders of Sun Microsystems, calls Kolomogorov complexity a bulk theory of random numbers that is comparable to the discovery of wave-particle duality in physics. When physicists stopped thinking of subatomic particles as points in space and started thinking of them as waves that spread throughout space, they were better able to predict their behaviour. Similarly, by treating random numbers as objects that cannot be pinned down, mathematicians have a powerful new way to solve problems. "It lets you wrap your mind around the suite of all possible computations," he says.
The significance goes beyond pure mathematics. Vitanyi's group and other mathematicians are working on ways to apply their new found skills to problems in computer science. One important problem is determining the average running time of a given computer program. Essentially, this problem boils down to the task of finding an average" number with which to test the program. An average number is one that does not have any special sequence or pattern that could make the program run especially quickly or slowly. If this sounds familiar, there is a good reason. In mathematical terms, an average number is very similar to a random number.

Roll the Bones
Computer scientists are painfully aware that finding a truly random number is tough. Instead, they usually confine themselves to finding best and worst-case scenarios, a problem that equates to finding numbers with a special sequences that make the program run as quickly or as slowly as possible. Of course, the worst case scenario may not bear any relation to how fast the program runs under average conditions which is why the method is frustrating.
But a solution may be in sight. Vitanyi and his colleagues recently applied the idea of mapping randomness to the problem of determining the average running time of a list-sorting program called Shellsort, a problem that has gone unsolved for some forty years. And the idea is spreading. According to Xiaolu Wang, a mathematician and computer scientist in New Jersey, the work may point the way to a better solution to one of Wall Street's trickiest problems: how to determine the fair market value of derivatives. These are essentially IOUs, promises to buy or sell a given stock by a certain date, or when it reaches a certain price. Their value depends on how likely the stock is to go up or down by the prescribed amount, and that in turn depends on predicting the seemingly random fluctuations of the market.

Because the stock market is so complex, analysts like Wang do not use mathematical formulae to price a derivative. (While economists Fischer Black and Myron Scholes recently won a Nobel prize for such a formula, its assumptions on how investors react are now thought by many analysts to be too simplistic.) Instead, they simulate the stock market many times on powerful computers and work out an average estimate of how it will behave, a trick known as the Monte Carlo method. "It's powerful and easy to apply to a wide range of problems," says Wang. "The drawback is that its convergence [the time it takes to arrive at a reliable estimate] can be agonisingly slow."
The inefficiency of the Monte Carlo method comes right back to Heilbronn's problem, Wang says. When computers simulate random events, like the random dots in the square, they produce too many "clusters" of points. "If you have a cluster in a given region, you will emphasise that region too much," Wang says. He has founded a financial consulting company called Advanced Analytics that sells a proprietary method for generating sequences that are more evenly distributed, although not random. So Vitanyi, Li and Jiang's result acts like a mathematical guarantee of the efficacy of Wang's method. By describing precisely what the degree of clustering is in random simulations, it should allow Wang to determine just how much better he can do with more uniform simulations.
And for the gambler playing computer animated craps, there is also hope. In the example at the beginning of this story; betting on an odd number is the right idea. A hundred odd numbers in a row is more than just a lucky streak-it is a pattern than can easily be compressed and so is immensely unlikely to be the result of a random process. If you haven't worked it out already, the machine is almost certainly broken and you should bet on it before the management finds out.


Author

Dana Mackenzie is a science writer based in Santa Cruz.

Further Reading

Does God Play Dice? by Ian Stewart.

MAIN INDEX

REFERENCE GUIDE

TRANSCRIPTS

GLOSSARY

Chaos Quantum Logic Cosmos Conscious Belief Elect. Art Chem. Maths


New Scientist 6 November 1999 File Info: Created 24/7/2003 Updated 8/9/2017  Page Address: http://leebor2.100webspace.net/Zymic/onaroll.html