Slashdot Mirror
Pi: Less Random Than We Thought
Autoversicherung writes "Physicists including Purdue's Ephraim Fischbach have completed a study comparing the 'randomness' in pi to that produced by 30 software random-number generators and one chaos-generating physical machine. After conducting several tests, they have found that while sequences of digits from pi are indeed an acceptable source of randomness -- often an important factor in data encryption and in solving certain physics problems -- pi's digit string does not always produce randomness as effectively as manufactured generators do."
Given that its possible to compute any digit of pi without computing the preceding digits its not surprising that the digits have structure. The bizarre part of this algorithm is that computes digits in hexadecimal.
Two wrongs don't make a right, but three lefts do.
Well, define "random". The digits of pi occur equiprobably (I believe this is proven) and so represent a random number in the usual sense.
On the other hand, as you say, they're essentially "pseudorandom" in the sense that they can be computed by a deterministic program.
What you're groping for here is called "Kolmogarov complexity", or sometimes "Kolmogarov- Solomonov- Chaitin complexity" which can be defined as the length in instructions for some fixed machine of the shortest program that can compute an output sequence. If, without loss of generality, we choose something like a conventional machine, you can think of this as the length of the shortest program in bits.
What's kind of amazing about it is that there is a supremely elegant and simple proof that there are "really" random sequences in the sense that there is no program that can compute and output a sequence random sequence R that's any shorter than "print R". This is what you're looking for in the sense you're talking about "randomness".
(The proof comes directly from the fact that there are more bit sequences of length n than there are sequences of length (n-k) for k>0. Thus there must exist sequences of length n which can't be computed by a program of length (n-k).)
This leads to all sorts of cool stuff, including things like a unification of Gödel's Proof, Turing's Halting proof, Hilbert's Tenth Problem, and chaos theory.
To learn more, Google for "algorithmic information theory" and "Gregory Chaitin".
The fun thing about this is that if pi really is "normal", then if you compute long enough, you'll not only eventually find pictures of circles in base 11, you'll also find an MPEG-4 of NTS video of a hand writing, with goose-quill pen, "I exist, yours sincerely, God."
What's worse is that somewhere else is NTS video of the same hand, writing "I don't exist after all, yours sincerely, God."
(I leave the proof of this as an exercise for the interested student.)
I must tell you a story.
In the first half of the 15th century the Persian mathematician Al-Kashi calculated pi to 14 places. It would be over a hundred years until a European calculated it to 9 places. But that's not what makes Al-Kashi cool, the Arabs where so much better at math in that period. What made him cool was that he stopped. He observed that, with his pi, the calculation of the circumference of a circle with a radius twice the size of Earth would have a margin of error smaller than a "horse hair" (a Persian unit). Problem solved, next problem. Meanwhile, people are still today using computers to get pi to _hundreds_of_billions_of_decimal_places!! As if there's something unique about pi because it's irrational and transcendental, when this is in fact true of the vast majority of all real numbers. Here's to Al-Kashi, a sane man and a pragmatic!