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.
... but it seems a shitty research, based on the article:
> Pi never scored less than a B on the tests, and in one case outperformed all the RNGs, which in addition to mathematical algorithms included a device that uses turbulence in a fluid as its source of randomness. But in most cases, pi lost out to at least one RNG, and in several it finished decidedly in the middle of the pack.
Obviously. There is no reason that pi would beat every RNG out there on a sample of numbers. It should just be slightly ahead the pack (if some RNG are bad), or just in the middle (if all are good).
> "Our work showed no correlations or patterns in pi's number set - in short, pi is indeed a good source of randomness," Fischbach said. "However, there were times when pi's performance was outdone by the RNGs."
Well, there is a reason why mathematicians consider that statistics are not a branch of mathematic. And such article are a proof of it.
pi output on the statistical tests were correct (if they werer not, then it would be an important news, as it would imply correlations). The fact that some other RNG generated "better" output for the (relatively) small sample they used is meaningless.
That's only because they forgot to randomize first!
ScienceNews article (2001) on Randomness of Pi's digits
Interesting work from Johan on Testing the a-periodic randomness of and comparing it with a Quantum Mechanical source.
But are the digits truely random ? In 1996, NERSC Chief Technologist David H. Bailey, together with Canadian mathematicians Peter Borwein and Simon Plouffe, found a new formula for pi. This formula permits one to calculate the n-th binary or hexadecimal digits of pi, without having to calculate any of the preceding n-1 digits. This formula was discovered by a computer, using Bailey's implementation of Ferguson's PSLQ algorithm
Mod parent down, he needs to take a basic number theory class. It has not been proven that pi is normal. It has been proven that there are all kinds of infinite sequences which are not normal. Random is not the same as normal
OMG!!! You mean Pi knows my SSN??? It must be a terrorist! We have to do something! (Maybe it knows where WMDs are, too)
Yes, picking every 14th digit of Pi may share the properties of a good random number (although, once again, the article points out that it is not as good as a RNG). However, actually using said digits for anything would be very unwise, since it wouldn't be that hard to determine that you were using a periodic subsequence of Pi's digits. I.e. don't use this for cryptographic keys.
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.)
Being able to reproduce random sequences is a good thing. Let's say you want to set up a test that feeds random data into a program until it crashes. It would be nice to be able to rerun that sequence (without having to store the sequence) to make sure the problem gets fixed.
That's why most random number generators let you specify a seed value. As long as you use the same seed value, you get the same sequence back. If you want a new sequence every time, peg your seed value to some number that varies, like the current time...
I had a teacher who insisted that Pi is exactly 3.14, and that the radiation after nuclear explosion decays by a factor of 2 in exactly 5 hours.
Admittedly, he wasn't a math teacher though...
The real issue with statistics is that people who use them generally do not understand them. I get irritated with people all the time when people "prove" some statement. Statistics shows that a sample of the populace has some correlation within some bound that is likely to be true some percentage of the time. So, the real question is: what was the bound and what percentage of the time was the randomness within that bound. If PI's bound exists outside of the statistical error of the bounds of the other tests then one could say that PI is less random; however, it sounds like they indeed found a few tests where PI "beat" the other tests. In other words, the bound PI was within the statistical error of the other tests, but the computed mean was occasionally better. But, occasionally better is to be expected some percentage of the time. If it is with in that number of times, it is as you say, a meaningless conclusion. Statatics within the bounds of error are completely equal. Probability is math, but it is also just very probable that it is used wrong.
Bel, the mostly sane.. "Of course I can't see anything! I'm standing on the shoulders of idiots." -- Me
Even quantum physics, although theoretically 'random', is generally predictable and reliably recreatable for a large T distribution over time.
If you want truly unpredictable, unrecreatable, random numbers - let my wife balance your checkbook.
Glonoinha the MebiByte Slayer
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!
Calculate it in base pi. After one digit, you'll get an infinite sequence of zeroes.
10.000000......
Accounting Troll: "Over here we have our random number generator"
Number Generator Troll: "Nine Nine Nine Nine Nine Nine"
Dilbert: "Are you sure that's random?"
Accounting Troll: "That's the problem with randomness: you can never be sure"
Recycle PCs and build a wireless community network www.hillsborough.org.nz
Pi is a transcendental number
Yes, that's right...
and therefore cannot be exactly determined
Er, that depends on what you mean by "exactly determined". Do we need to know the digits in decimal expansion (base 10) to "determine" pi? How about saying that pi is exactly "1.000" in "base pi"? IMHO, whether or not a number can be exactly determined is independent of whether its decimal expansion is known. By your logic, sqrt(2) cannot be exactly determined, as it is an irrational number and has infinitely many digits (and they aren't periodic, unlike 1/3=0.33333333333... which also has infinitely many digits). But I am not entirely comfortable with saying that sqrt(2) cannot be exactly determined. After all, we know exactly what it is -- the positive number whose square is two.
I expect e and the square root of 2 to be better choices
WTF? How is e a better choice? It is also a transcendental number, just like pi. And sqrt(2) isn't even transcendental!