Pi -- The Source Of All Information?

How can we calculate just how many digits of pi we’d have to go through to find a specific piece of data? If you have a specific file that is n bits long, the probability of getting that specific file out of a random combination of n bits is 1/2^n. But, what is the probability of finding it in a random combination of m bits, where m > n?

Well, first off, pi’s not really random, because it’s an infinite string that can be generated by a finite program. Secondly, we don’t know if we can calculate the starting point of any sequence–but if it’s in there, we are guaranteed to find it. If pi is normal, it’s guaranteed to be in there.

Something else in your OP–this property of pi wouldn’t have anything to do with the fact that pi is transcendental, unless it turns out that all transcendentals are normal. That would be really cool if it were true, but I don’t think we have any reason to suspect that (on the other hand, I could very easily be wrong).

What I was trying to estimate was not exactly where in pi a specific file could be found, but rather the probability of finding a specific file in a piece of pi (heh) of a certain length. If you generated a binary expansion of pi that was 10 terabytes long, what are the chances of finding a specific 1K file in there?

It also turns out that not all transcendental numbers are normal. There is a transcendental number that contains only the digits 0 and 1. Also, numbers such as the square root of 2, which are only irrational, may also be normal.

In fact, Liouville’s number, 0.110001000000000000000001… (with ones in the n! position after the decimal (n a positive integer), zeros elsewhere), was the first number ever proven to be transcendental, but obviously can’t be normal in base ten since it doesn’t even use digits 2 - 9.

Tell you what, go watch this movie, and then come back and talk about this little problem :slight_smile:

-Dani

In fact, the base-2 version of Liouville’s number isn’t normal (in base 2) either, since the string 111 never appears.

Randomly pick a number 100 digits long.
What are the odds of your having picked that particular number ?
In base 10 they’d be 1 out of ~10E100.

What is the shortest number that could possibly contain a significant fraction of all numbers that are 100 digits long ?
If a number is 100 digits long it can contain 1 100 digit substring
If it’s 101 digits long it can contain 2
If it’s 102 digits long it can contain 3…
So to contain 10E100 100 digit numbers (substrings) it would have to be at least 10E100 digits long, and that’s if the digits of the number are chosen so they don’t repeat any 100 digit substring along the way.

So even with a normal number that doesn’t have duplicate substrings your “average” random 100 digit number would be found somewhere about halfway through a string of 10E100 digits.

I’m sure an actual mathematician could make an even grimmer estimate of how far out in pi you’d have to look in order to find the substring you want.

Couldn’t you also say that every number combination, file or whatever is in pi an inifinitely many number of times?

Yeah, that’s true, too. For a number to be normal, it has to have all possible finite sequences of digits occuring at their expected frequency in a uniformly random distribution of digits. For example, the digit “1” has to occur in 1/10 of the digits on average as you go out the infinite string of digits of pi, same as any other digit. “36” has to occur in one out of every hundred pairs of digits, on average. {some string of n digits} has to occur, on average, in one out of every 10[sup]n[/sup] sequences of n digits. Of course, this forces every possible finite string to occur infinitely often.

In hexadecimal, yes, but not in decimal. Unless my information is out-of-date.

Don’t believe there’s anything specifying I can’t do it in hex. Besides, I really wanna see Enderw24’s Shakespeare-typing monkey.

Not only that, but there is an algorithm that will compute the nth decimal digit of pi (or in any other base):

http://www.lacim.uqam.ca/plouffe/Simon/articlepi.html