Are The Digits of Pi Random?

Steve Hamlin writes "A researcher at Lawrence Berkeley National Laboratory, and his colleague at the Center for Advanced Computation at Reed College, have taken a major step toward answering the age-old question of whether the digits of pi and other math constants are "random." In addition, a simple formula discovered makes it possible to calculate the Nth binary digit of Pi without computing any of the first N-1 digits, and do the computation with very little computing power. "

Comments

formula for nth digit != random?

[Hitch]

I was wondering the same thing...BUT. I think we're looking at this the wrong way. the number are not, and have never been, and are in no danger or question of BEING, truly random. they're there, they're set, and it's done. the question is "is there a pattern"? and so, the formula does not automatically force there to be a pattern, just forces us to realize that they're static and predictable.
------------------------------------ ----------
All that glitters has a high refractive index.

Pi is hardly random.

[KFury]

A lot of people are playing fast and loose with the word 'random' today. The value of Pi, in whole or of any one digit, isn't random at all. It's entirely deterministic, defined rigidly by a simple formula. No matter how many times or ways that formula is interpreted, the value of Pi is the same, and not random.

What can be said to be 'random' (really pseudorandom or, in the parlance of mathematicians, 'random enough') is an arbitrary digit or sequence of digits from pi, given that the starting decimal place N is also random, or at least non-repeating. The randomness of pi is that each succeeding digit of Pi has no correlation to the preceding digit.

Of course we all know this inherently, but it wouldn't hurt to be a little clearer in these posts about exactly what is random (or not) about Pi.

Kevin Fox
--

Partly old news

[LinuxParanoid]

The fact that there's a algorithm for determining the Nth digit of Pi is old news. The BBP formula which does that was discovered by Bailey, Borwein, and Plouffe in 1995. (PDF paper here).

There was a distributed computing project called PiHex that lasted several years for computing the five trillionth, 40 trillionth, and the quadrillioth bit of Pi, using a variant of the Plouffe discovery, Bellard's formula.

A proof that digits of Pi are random would indeed be news, albeit not exactly a surprise; I'd comment on it but the article's link seems bad or swamped at the moment.

--LP

P.S. Google has a nice list of Pi links.

Not Texas, Indiana

[sg3000]

Although I wouldn't put it past Dubya to legislate pi to a particular value -- this is the guy that doesn't believe Social Security is a Federal program, and his party has been trying to legislate the story of biblical creation as science for decades -- it was actually Indiana where this happened.

in 1897 Representative T.I. Record introduced House Bill 246 suggesting three values for pi: 3.2, 4, and ~3.23. These three figures were based on the work of an amateur mathematician Edward Goodwin. The bill was quickly forwarded to the Committee on Swamp Lands (of course), which then forwarded it to the Committee on Education. This committee gave it a pass, where the House approved it unanimously. The bill made it to the Senate.

Before the Senate could make asses of themselves as well, a professor of mathematics at Purdue named C.A. Waldo, intervened, and it died an embarrassing death.

For a more humorous account, read Cecil Adam's account of this at the Straight Dope.

Re:Why does this matter?

[(void*)]

Also, since Pi is a ratio that we 'choose' to express in a base10 numerical system, would the fact that the digits are random in a decimal system mean that they would be random if we expressed Pi in a hexidecimal or octal system?

How is this insightful?

Suppose there is some base b such that the digits of repeat. Then Pi * b * m = n where m and n is some integer. And so we would have Pi = n / b *m. But m and n are integers, as is b. So you've just shown that Pi is a rational number. It is not. Hence, no such base exists.

More info on the Algorithm

[regen]

Can be found at http://www.lbl.gov/Science-Articles/Archive/pi-alg orithm.html.

I couldn't get the link in the story to work, and found this while searching for the story.

Re:Biblical precidence

[istartedi]

Well, if you're going to be using "cubits", it's not like precision is really a concern to begin with. IIRC, The cubit was the distance from the elbow to the tip of the longest finger. Whoever was ruler at the time set the standard. It would be interesting to see how close we could come doing it by hand, or with a "cubit-stick".

Cool Application!

[FreezerJam]

If it is possible to calculate digits of Pi starting at any point, then you could easily use Pi as a pseudo-random pad.

Once you know the starting digit location, you can easily decrypt something that has been XOR'd with the sequence from that point onward. But - given that each n-bit sequence occurs 1/n of all n-bit sequences, there are essentially an infinite number of options facing the code-breaker - even after each successful step!

If you are feeling particularly vicious that day, encrypt with two XOR sequences, based on two difference starting points.

Re:True story.

[BlowCat]

The string 1337 was found at position 222222 counting from the first digit after the decimal point. The 3. is not counted.

Wow, Pi is Leet!

Neumann said ...

[(H)elix1]

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
(John Von Neumann, 1951 )

This is a clear violation of the DMCA

[GMFTatsujin]

Consider:

1. All computer code can be represented as a series of ons and offs, typically interpreted as 1's and 0's
2. Any series of 1's and 0's can be interpreted as a base 2 form of some integer x
3. Pi contains an infinitely variable series of digits which, in chunks, can be taken as integers
4. Pi is infinite and non-repeating, and therefore contains every possible combination of every integer in the infinite set (some mathbrained guru can feel free to slap me down on this)

Therefore, somewhere in the digits of Pi is a string of digits which, when transformed into binary, form the code to decrypt CCS on a Linux box. All the scientists have to do is find the correct starting position and how may digits need to be calculated. The resulting information could be spread throughout the internet and used to decrypt protected content.

Further investgation into the true nature of Pi is a violation of the DMCA! This must stop at once!

or... Holy moley! Taking that same argument, one could reason that every movie ever made, or that ever could be made, is buried digitally in Pi somewhere! Piracy is built in to the very structure of the universe!!!!

Tatsujin

Pi is great as a random source.

[acidblood]

I did some very interesting work this year with this, in the course of planning a high-quality pseudo-random library. I calculated the first 512 megabits of Pi, and then started splitting up the file in smaller pieces, to study whether they had an "information-theoretic randomness quality". That is, they're not random (you can calculate them), but they exhibit desirable randomness properties, such as uniform statistical distribution.

Here's the output of John Walker's ent program for 512 megabits of Pi:

Entropy = 7.999997 bits per byte.

Optimum compression would reduce the size of this 67108864 byte file by 0 percent.

Chi square distribution for 67108864 samples is 245.38, and randomly would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.4938 (127.5 = random).
Monte Carlo value for Pi is 3.142281720 (error 0.02 percent).
Serial correlation coefficient is -0.000145 (totally uncorrelated = 0.0).

For the entropy test, a completely random sample would have an entropy of 8.0 bits per byte, and the ideal Chi Square distribution would be 256.0 (considering there are 256 degrees of freedom in an 8-bit data structure, or 2**8 possibilities.) As you can see, that's about as random as you can get. And the larger the samples you feed it, the more it converges to the ideal values.

I've also done some testing with other transcendental numbers, such as e (2.718281828...), and they all seem to show great randomness properties, in the information-theoretic sense at least. However, I have a feeling to "trust" Pi more than e, given that you can write e in form of continued fractions with repeating patterns, and nobody has yet found a pattern in the continued fractions of Pi.

As for my pseudo-random library project, my programming skills are quite bad, but if you have some knowledge of scientific computing (multiplication algorithms using FFTs, for example), you can contact me and I might revive the idea.