快猫短视频

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鈥檚 no longer random.

快猫短视频s 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 鈥淧RINT鈥� 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 鈥淧RINT鈥�.

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 1s can be
compressed into a program such as 鈥淧RINT 1 100 TIMES鈥濃�攑recisely because
this sequence has a pattern. In fact, any number you can compress can鈥檛 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鈥檛 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鈥檚
also theoretically impossible.

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鈥攖he
random numbers鈥攁re 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.1924鈥�(meaning
that the smallest triangle in this arrangement is 0.1924鈥�times the size
of the square). The sixth Heilbronn number is 1/8 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/n², 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鈥檚 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鈥攈ow 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 Jiang 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.

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.

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鈥攈aving mapped the edge of
randomness鈥攖he 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/n³鈥攏o 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鈥檚. 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. 鈥淩andom 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. 鈥淚t lets you wrap your mind around the suite of all possible
computations,鈥� he says.

The significance goes beyond pure mathematics. Vitanyi鈥檚 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 鈥渁verage鈥� 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.

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鈥檚 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. 鈥淚t鈥檚 powerful and easy to apply to a wide range of problems,鈥�
says Wang. 鈥淭he 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鈥檚
problem, Wang says. When computers simulate random events, like the random dots
in the square, they produce too many 鈥渃lusters鈥� of points. 鈥淚f 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鈥檚 result acts like a
mathematical guarantee of the efficacy of Wang鈥檚 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鈥攊t is a pattern than can easily be compressed and so is immensely
unlikely to be the result of a random process. If you haven鈥檛 worked it out
already, the machine is almost certainly broken and you should bet on it before
the management finds out.