Finding a random sequence is as easy as pi--or is it? Mathematicians often depend on irrational numbers like , e (the basis of natural logarithms), and 2 to give them an unpredictable stream of digits. But a paper in today's Proceedings of the National Academy of Sciences is upsetting the conventional wisdom about randomness by showing that some of these numbers are far more predictable than expected. That could sound alarms in fields that depend on random numbers, such as cryptography and the design of certain experiments.
The finding comes from a new technique for quantifying randomness. Any mathematician can tell you that 01101100 is more random than 01010101, but until last year none could tell you just how much more random. Then two researchers--Steve Pincus, a free-lance mathematician based in Guilford, Connecticut, and Burton Singer, a mathematician and demographer at Princeton University--created a method for determining a sequence's "entropy," or disorder.
Pincus and Singer's method builds on the observation that all possible digits are represented about equally in a perfectly random stream of digits. The binary sequences 01101100 and 01010101--each with four 1's and four O's--both pass this test, for example. Pincus and Singer also noted that when the digits are taken two at a time, a random sequence should have equal numbers of all possible pairs: 00, 01, 10, and 11, in this case. The sequence 01010101 fails this test miserably; there are no 00s or 11s at all. The same reasoning can be extended to larger groups of digits, taking them three at a time, four at a time, and so on. By comparing the actual frequency of groups of digits to their expected frequency, Pincus and Singer come up with the "approximate entropy" (ApEn) of the sequence--a measure of its randomness.
"[ApEn] is one of those tools that makes you say, `Hey, that's a good one!' and you put it in your tool kit," says Max Woodbury, a mathematician at Duke University. But it's a tool that is raising more questions than it answers, as the Proceedings paper shows. In it, Pincus and Rudolf Kalman, a mathematician at the Swiss Federal Institute of Technology in Zurich, Switzerland, calculated the ApEn of various irrational numbers. They included both algebraic numbers, which are solutions of polynomials with finite numbers of terms--3, for example--and "transcendental" numbers like and e, which are not algebraic. Transcendental numbers are, in a sense, more complicated than algebraic numbers, so Pincus expected that when they are written out in decimal form, their strings of digits would be more random. He was wrong.
" is the most irregular," says Pincus. "But I was very surprised that e was not next in line." In fact, 2, an algebraic number, was more random than e, a transcendental number. Mathematicians are scratching their heads over this. Says Singer, "It raises serious conceptual problems about the idea of randomness."