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."
Part of it being infinate is comming across every possible sequence.
No. It is entirely possible for a sequence to be infinite without contain every possible sequence of numbers. To use a trivial example, 3.333 recurring does not contain every possible sequence of numbers. Therefore containing every possible sequence of numbers is not part of being infinite.
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
Pseudo-random number generators not "known to be random." They are constructed to pass certain statistical tests with high certainty. Output of these generators, however, NOT RANDOM in strongest sense. Instead, are generated by DETERMINISTIC ALGORITHM.
Pi's digits also pass certain tests for non-correlation.
OOGG wish correct additional mistaken assumption of yours:
Knowledge or proof of FACT does not CHANGE fact. ONLY CHANGE OUR KNOWLEDGE.
Digits of PI either "random" or "not random" depending on definition you choose for word "random." If not proven, must make experiment study to understand.
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
Actually, he is a simpsons fan
"I was under umpression that truly random data should be completely uncomressible."
Technically it is *chaotic* data that is not compressible. Since random data is almost always chaotic, people tend to play loose with the terminology. But random data can happen to be ordered very well, in which case you can compress it.
"Random" is a feature of the method by which a number was created.
"Chaos" is a feature or the number itself, regardless of how it was created.
The point is that what you're describing --- that an infitite sequence contains all possible finite subsequences infinitely often --- is what's called "normal" in this context, and while all tests show the digits of pi look normal, there's no proof that they are, so you can't say absolutely that it's true.
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.
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 just remember that it was possible because pi was periodic in some obscure fractional base.
I don't believe that's true. Pi is a transcendental number, which pretty much precludes it being periodic in an fractional base.
(Assuming by "fractional" you mean "rational", the ratio of two whole numbers. Sorry to be picky; I'm just trying to be complete.)
You can compute arbitrary digits of pi in hexadecimal (and binary and octal and any other 2^n base), but as far as I'm aware there isn't any corresponding algorithm for decimal numbers. I'm not certain it's been precluded, either, but I'm fairly certain you won't find pi to be periodic in any fractional base.
If there does exist a proof that you can't do it in decimal, I suspect it will involve the fact that there exist fractions in base 10 that don't have terminating representations in base 16 (e.g. 1/5). That'll make it hard to apply the algorithm from base 16 back to base 10; a one-bit change in the base 16 representation will have dramatic effects all over the base 10 representation.
(I'm not a mathematician, but I used to be, which is why this post is so maddeningly vague. I hope somebody gives you a better answer than I just did.)
The computed digits number doesn't even matter anymore since we can calculate the value of a given byte of PI without having calculated any of the previous ones.
As a side note, the current record by the Kanada lab is 1.2411 trillion digits, their previous record was a bit above 200 billions.
"The way we can tell it's C# instead of Haskell is because it's nine lines instead of two." -- wadler
(I believe this is proven)
Pi has not been proven normal.
http://mathworld.wolfram.com/NormalNumber.html
1.000 in base pi is 1 in base 10. You mean 10 in base pi, which is about 3.14159 in base 10.
No... 1 is one in all bases, by definition. 10 is the number of the base in all bases, again by definition. In base ten with represent ten as 10. In base pi, pi is 10.
My understanding is that randomness of a sequence is measured as the degree of predictability: a sequence is random if you can't predict the next bit even if you know any other set of bits in the sequence. So if you have 1,0,1,0,1 and the next bit is 0 with 100% probability, it's not random, but if the next bit is 0 with 50% probability it is. Just being given a portion of a sequence it's not possible to deterministically compute the probability, but it can be computed to within a (exponentially decreasingly small) margin of error. So from a sequence you can't determine if something is truly random, but you can get 99.9999% sure that is.
This is the degree of randomness: they can say that pi is less random than various RNGs because given a few digits of pi, you can calculate remaining digits with 50%+n accuracy, while given the same number of digits from a pseudorandom generator the odds of getting the next bit right are 50%+1/2^-s where s is a large number determined by which RNG you use, among other things. For pi, n is unknown, but these researchers are saying it's not small and possibly not even exponentially small. Truly random has n=0, but exponentially small is good enough for practical use.
And for the sticklers, pseudorandom != random and there are other issues about that too, but that's for another post. Also as a side note, IIRC the absolute predictability of any set of digits of pi from any other set has not been generally ruled out.
First question: no. The number: ...
\sum_{n=1}^{\inf} 10^{-n!} is transcendental; it's a Liouville number. But the digit string is all zeroes (in base 10) except for 1 at position 1!, 2!, 3!,
pi and e may be absolutely normal (i.e. every possible digit sequence in any base occurs about as often as you'd expect if the digits were random) but this is AFAIK not proven. It's also conjectured that every irrational algebraic number is absolutely normal.
Well, strictly speaking sqrt(9) is 3.
+3 and -3 are both solutions to x ^ 2 = 9, and so are both 'square roots' of 9, but sqrt(9) refers to the positive root.
I suppose "randomness" might be the opposite of "order" in an information-theoretical sense. It is also a measure of the level of compressibility of a string. A chessboard pattern can be compressed a lot, white noise can't be compressed. So that would make white noise less ordered and more random. To me as a philosopher however, that looks fishy, because it puts a restriction on how a random sequence can look. It means that if order, or perhaps "correlation," is a property C, then supposedly random series always have the property ~C. But what causes them to have this property? They are supposed to be random! That is not what random is supposed to mean; there are no causes involved in randomness, so it seems to be nonsense to claim that all random series share a property. This information-theoretical notion also seems to jive poorly with cryptographic ideas, where as soon as you introduce a rule, you lose randomness. (In essence, the password gets easier to guess.) But, I'm not a mathematician, so I may have it all wrong. :-)
That's bollocks. I reckon that one day those maths nerds will discover the exact value of pi, and it will be a finite string of digits. There's no reason to believe it goes on for ever. Even if it's not in denary, it may be in another number system.
It's just arrogant to believe that pi goes on forever just because we want it to. When we find that pi comes to an end, all those mathematicians will look really fucking stupid.
Bollocks yourself. If pi can be expressed as a finite series of digits, then it can also be expressed as the quotient of two integers--which would make it a rational number. I can't quote you a proof, but mathematicians have long accepted that pi is irrational.
In any case, the important thing is not that it has an infinite series of decimal digits; so does 1/3. The important fact is that its sequence is non-repeating and apparently patternless.
I figure by 2030 or so my 6-digit UID will be something to brag about.
Al-Kashi used the same method as the Greeks. He calculated the ratio of the radius of a circle to the circumference of a polygon (that's trivial, of course) that fit inside the circle, with an increasing number of sides on the polygon. The more sides on the polygon, the closer to the circle it gets, and the more precise value for pi you get.
:-)
I have a vague memory that the Chinese actually built a large circle that was so exactly round that they _measured_ pi to an impressive number of decimals. So there is obviously more than one way to do it.
The same guy came up with a new proof that allows computation in any base, check it out http://fabrice.bellard.free.fr/pi/pi_n2/pi_n2.html
The road to hell is paved with good intentions.