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."

Comments

Computing any digit of pi

[G4from128k]

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.

Completely Unsurprised

[DumbSwede]

I actually find this completely unsurprising. PI is completely UNRANDOM. It can be compressed very efficiently with the progression Pi =4 (1-1/3+1/5-1/7+1/9- ...). It is even possible to derive binary or decimal digits of PI in isolation with a formula as well. My point is that since the digits can be represented as a formula, they may completely screw up other functions expecting randomness from them. When they do I would predict there is some deeper connection between the function being tested and Pi than is realized.

When you cite for example a deviation from a Chi distribution, then there is probably some connection between Chi and Pi that doesn't seem obvious from how Chi is calculated, but is there non-the-less.

I am not a mathematician (though I did work at Wolfram Research for ten years). I look forward to seeing real mathematicians take on this.

Re:Completely Unsurprised

[crmartin]

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".

Pi experiments and random numbers

[rice_burners_suck]

I would say that it's not too wise to get random digits from pi anyway, because it's too obvious a source. It's also not too difficult, what with storage and whatnot nowadays, to store about ten billion digits and then, knowing a few digits in the sequence, perform a quick pattern match, find it in pi, and know the next digit in the sequence.

I was wondering, maybe not more than an hour ago, why not get a TV card and gather randomness from there? There are lots of channels on TV, and they have both a video and an audio component. You could set the thing up to change channels at random intervals, and gather things like the color of random pixels at random times, the frequency of random sounds, etc. Perhaps you could use a radio card to do something very similar with the radio. That, combined with entropy from the keyboard, mouse, the time between interrupts of various kinds, the contents of various processor registers or random memory locations, or whatever, should provide basically a random pool that is so random, you'll never have to worry about security problems with relation to them.

Speaking of which, there are ten digits used in our radix 10 notation; if you want to store a character string in a strange format, you could conceivably store two digits in one byte, because four bits are enough to describe all ten digits, leaving plenty of room for things like a decimal point or a negative sign. I'm saying this because it's not too terribly expensive these days to get a terabyte of storage. If you store, on this terabyte, nothing but digits from pi, in this space-saving format I'm describing, you could store 2,417,851,639,229,258,349,412,352 digits from pi. You'd need some kind of cluster, like PI@home, to compute all those digits. Once computed, who said you can't use pattern-matching algorithms to see if there isn't some kind of pattern? I still believe that somewhere in there, there is a pattern, though it is very large. Hell, who said you can't get an exabyte of storage and do this? If anything, it could become one component in a random number generator that simply never repeats itself.

Re:Did Sagan See This?

[crmartin]

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.)

Al-Kashi, a cool mathematician

[kronocide]

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!