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."
PI is exactly three.
Gee, they found that pi wasn't random. Imagine that. Maybe someday we'll even be able to predict the value of pi.
I'm an American. I love this country and the freedoms that we used to have.
Uhh.. we're surprised? Pi can be described by numerous simple iterative formulas. When we do that with especially built algorithms we get pseudo random numbers.
I'd expect pi to be much worse than a PRNG.
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.
Y'know I would have thought this fact would have made it into at least some religious text books.
Deleted
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.
Letter To Iran
...of pi. It's not random at all, I always get 3.14159....
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
As far as I have read, this has yet to be proven.
Switch back to Slashdot's D1 system.
$pi = 4 * atan 1;
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.
Or so I'm told... :)
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.
Fractals, which resemble nature, are not random though they appear to be. Therefore, I've often considered all the universe to be one giant, multi-dimensional fractal.
I think "random" has a misleading connotation. Just because something is highly unpredictable, it is not necessarily without pattern. We take "random" to mean something that cannot ever be predicted, that follows no pattern. But attractor fractals and many areas of Chaos Theory have proved that there are patterns that defy the human pattern recognition faculty (or at least require the use of a pencil, calculator, super-computer, etc.).
Esoteric reference.
I wrote a Pi calculating program, that worked in base Pi. It didn't take long at all to compute pi, and it is a great source of random binary. The answer I got was "10". Now, simply take one of those digits 8 times, and you have a completely random byte.
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
Better still, use this site to find any number string in the first 200,000,000 digits of pi:
http://www.angio.net/pi/piquery
Everything in moderation, including moderation itself
OMG!!! You mean Pi knows my SSN??? It must be a terrorist! We have to do something! (Maybe it knows where WMDs are, too)
Value of pi not depend on coordinate system. pi simply transcendental number with certain value.
Polar coordinate can also use pi: circle of radius pi, arc length of arc subtending angle of pi radians, etc.
OOGG recommend you not change major to math. Otherwise, GPA likely much less than pi.
Physicists have completed a study comparing the randomness in Darl Mcbride's brainwaves to that produced by 30 typing rats. After conducting several tests, they have found that while sequences of digits from Darl are indeed an acceptable source for randomness, Darl's digit string does not always produce randomness as effectively as rats if the rats are using unixware.
"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.
That is a true and fun little fact, but it is nothing special to pi. You can do that with any irrational number, i.e. sqrt(2). Anyway, this story is ridiculous, noone pay attention to it. They did (from the article) 2 or 3 tests, the most significant appearing to be dividing 100 million digits into blocks of 10, plopping a decimal in the front. They then grabbed these blcoks in groups of 3 for x,y, z coordinates. They mapped these points in an imagnary cube and then graphed their distribution in the cube. From this they concluded that the other RNGs are more random. That is an extremely false conclusion. Arguing that one distribution is more random simply because it covers more of the cube or it's distrbution is more of a bell curve is just plain stupid so I really hope I missed some important fact when I read the article. Random is random and there is no rule saying that randomness is only random if it is distributed evenly or forms a bell curve (any such constraint would go against the nature of being random). Most RNGs try to distribute digits in a even manner because for cryptography purposes it is important, but is pointless when trying to deal with true sources of randomness. The fact that there is any such predefined distribution obviously shows that it isn't random (thus they are called pseudo-random), but arguing one algorithm generates a bell curve and another doesn't so the first one is better is just a dumb argument when dealing with random numbers. I hope a few mathematicians chime in and either blow my argument out of the water or confirm what I said.
Regards,
Steve
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.
Isn't randomn just something we can't understand ?. Technically speaking if we had enough infomation nothing would be considered randomn. I guess with encryption you pick something thats pretty damn complex and then hope that your competitors agree with you.
I know this has been said before, but perhaps not in this way. Pi is a number that represents a (ideal) physical phenomenon. Yes, it's complex and (probably) infinite, but it still is a numeric representation of an exact property. To me, that automatically presupposes that by its nature it's ordered.
The only reason anyone could think it would be a good indicator of randomness is because its complexity goes beyond the comprehension of man or machine. I'm not a professional mathematician, so there's not a lot about the nature of pi I can comment on, but it seems to me that in being an ordered number that describes a physical phenomenon, pi has about as much chance to produce randomness as counting the number of leafs on clovers.
The Internet is generally stupid
be careful what you prove next or zebra crossings might become dangerous.
Warning: Opinions known to be heavily biased.
At the risk of losing karma, what an obvious statement!! Pi is a mathematical number used to calculate certain things such as circumference OF COURSE ITS NOT RANDOM, if it was then we wouldn't be using it for so many important functions
The article actually specifies a few tests. One test involved the segmentation of pi's digits (10-digit chunks), and interpreting consecutive triples of these distances as points in 3-dimensional space. The experimenters then considered the distribution of the magnitudes of these vectors against a particular idealized distribution which is presumably that of independent digits and coordinates. This short bit does not specify how they compared distributions, but there are a number of statistical tests that may apply.
So here it's not a question of "is pi random", but "how likely is it that the decimal digits of pi, interpreted in a specific and arbitrary fashion, could arise from a specific distribution which likely presumes independent identically-distributed digits?"
In terms of randomness, it's a symbol string, and an infinite one at that. In theory one could measure the Kolmogorov complexity (sometimes expressed as the shortest possible length of two parts: the string necessary for a Universal Turing Machine to function as a specific TM, defining the 'model'; and the string that provides instructions for this particular instance, e.g. model parameters/data). A more 'random' string should be less easily predictable and require more symbols for the UTM to replicate it, compared to a string that can be represented by few parameters.
Of course, there's the slight problems that (a) the choice of UTM does matter, and (b) it's incomputable in the general case.
Only the dead have seen the end of war.
I don't agree with the term unknowable. Pi is certainly knowable. It just can't be expressed as a finite string of digits after a decimal point. But even if it were unknowable, that doesn't mean it is random. There are many algorithms in mathamatics that produce infinite series, but that doesn't mean they are random. Look at fractals for one example. A very simple math formula can produce an infinite and extremely complex mathmatical result, but even though that result is infinite it is certainly not random. Nor is Pi.
I'm an American. I love this country and the freedoms that we used to have.
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'm going to take "not exact" to mean transcendental, which is probably the strongest "weird" condition that's commonly accessible. In that case, it has nothing to do with our choice of coordinate system, rather our choice of metric and, even more fundamentally, number system.
What I mean by metric is that, after change of coordinates into the polar system, points are still the same distances apart from each other (the mapping from the cartesian plane to the polar plane is an isometry). Therefore, any circle still has the same length (circumference) and diameter, so Pi still has the same value.
If we define Pi by infinite series rather than the ratio of circumference to diameter of circles in Euclidean geometry, however, it's still transcendental because of the real number system. Transcendental, for the non-math people, means it's not a solution to any polynomial equation with rational (i.e., p/q, where p and q are integers) coefficients. So, for example, sqrt(2) is irrational, but it's not transcendental, because it's the solution to x^2 - 2 = 0. Pi is transcendental because of the properties of the real numbers as a field, which takes the problem even deeper than the geometry.
Now, I think what you might've been getting at is we can go back and look at our number system and define the Pi-rationals (rational multiples of Pi) as our new rationals, because our choice of the "regular" rationals was arbitrary. However, if our circle has Pi-rational radius and diameter, their dividend is going to be in the "regular" rationals. This is impossible, so at least one of the two must be irrational in our new number system. Therefore, you still have an irrational number involved somewhere in the process, no matter how you slice it.
Unless of course it was migrated from the open source "stick" project.
(1) "Pi is not random becuase I have a formula for its digits" is nonsense. Randomness is not the inability (or impossibility) to predict (at least in this situation). Randomness refers to statistical properties of the sequences. For ex. no correlation between conseq. digits, no corr. betweteen conseq. pairs of digits and so on brings a sequence closer to randomness.
(2) If you REALLY want randomness (with impossibility of prediction, and unreplicability of the sequence) - go and count events in a radiactive decay experiment. (More precisely, count waiting times for each successive decay - they follow an exponential distribution). (I think fourmilab has a 1-time rnadom number generator linked up to a geiger counter - don;t remmeber the URL any more).
(3) Why do mathematicians find "randomness" in digits interetsing? The reasons are similar to why people prove theorems about "how randomly are the primes distributed among the integers". It says something about the structure of the primes. I am not a number theorist - so I cannot give explicit results.
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!
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
This is untrue. The most common fallacy about random numbers is that they need to "appear" random.
Of the list of numbers,
734901253789
666666666666
123456789012
Which is random? One answer is that all of them may be random. There is no reason why 1234 is any less random than 7305. A truly random number with infinite digits will absolutely repeat any sequence of numbers you can think of of any length whatsoever.
Think of it this way: If you have a true random number generator, spitting out a digit every second, and you see it spit out:
1...2...3...4...
then can you predict what the next digit will be? If it is truely a random number generator, the answer is no, you can not. However, the next digit has a 1 in 10 chance (0..9) of being a 5, so it is possible. If you reject 1...2...3...4...5 as possible sequence, then you have instituted a rule restricting the possible outcomes of the random number generator--and have therefore reduced it's effective randomness. Rules defeat randomness, so 12345 is as valid a random number as any other sequence of five digits.
Jim
http://users.aol.com/s6sj7gt/picode.htm
:)
Quite an entertaining read
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.
For example, lots of large numbers follow Benford's Law. Excerpt: "Benford's law states that in listings, tables of statistics, etc., the digit 1 tends to occur with probability ~= 30% , much greater than the expected 11.1%" The probability distribution is logarithmic; the probability of a digit D is log10(1 + 1/D). This is a way the SEC checks filings for fraud. If the numbers are too evenly distributed, there's a good chance of fraud. Obviously if you know about this law you can spoof it to some degree, but it was an effective tool for a while (still probably is for some not so smart firms).
"Nature doesn't care how smart you are. You can still be wrong." - Richard Feynman
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. :-)
Plenty good enough for most of the great engineering of the 20th century. Another example of practical and "good enough".
In case, you find that interesting, here is a more recent article on their exploits.
Capturing the Unicorn
"sweet dreams are made of this..."