Okay, time for another math post. Here's my question about pi:
We all know, of course, that pi can't repeat because it's irrational (transcendental, even). But that just means that it can't repeat the same string over and over and over forever. There's nothing to prevent any particular string of symbols from repeating once, starting right after the string ends. So the question is, for some n, do the first n digits of pi repeat (once, in positions n+1 through 2n)?
Here's the only progress that I've made so far. For a random list of numbers (and I'm pretty sure pi actually hasn't been proven to be totally random, but I could be wrong about that...please let me know if I am), the probability that a specific n consecutive digits will appear at a given location is clearly 1/(10^n). So for that random string, the probability that the first n digits repeat as described above is 1/(10^n). Call that event E_n. I think that the set of events {not(E_n) for all positive integers n} is a set of independent events—meaning that if one set of n digits doesn't repeat, then it has no bearing on whether any other set repeats or not.
Therefore, the probability of none of the events E_n occuring is the product of the indvidual events:
[1—1/10][1—1/100]...[1—1/(10^n)]...
which I'll call P, and which doesn't equal 0, since none of the factors (thanks vlorbik) are 0;
and the probability that a string of n digits will repeat for some n must be:
1 —P.
But I sure don't know how to compute that product, and since so many digits of pi are known, I can't decide if this calculation should apply to pi or not.
Any ideas? Am I way off base here?
UPDATE: my spreadsheet tells me that P is surely .9, which makes 1-P=.1, which sounds like a semi-reasonable probability that a random string of digits has that property. but nothing definitive.
Pi hasn't been proven to be normal, but all empiral evidence suggests that it is.
In which case, of course, the probability of anything (finite) happening is one (if you're not picky about where it happens)
Useful reference:
http://en.wikipedia.org/wiki/Pi#Open_questions
Posted by: Westacular | November 19, 2005 at 02:54 AM
That link is useful, thanks.
And I understand that anything finite must happen with a probability of 1. But I'm convinced of that if you name me the length of the finite string (with some desired property, like 1000 8's in a row) beforehand. But this question doesn't quite do that.
Every time we discover few more digits of pi, and those digits do not start with 314159, then the probability of the repeat gets exponetially smaller.
I'm very willing to be proven wrong, but I'm still not sure that "any finite string appears in pi" means that the first n digits have to repeat once for some n.
Posted by: Polymath | November 20, 2005 at 01:04 AM
P just *can't* be .1;
that's the probability
that the *very first* digit
is repeated as the second!
1 - [1-.1][1-.01]
("first digit or first two")
is already .109 ; this is
(at least slightly) less
than P.
Posted by: vlorbik | December 09, 2005 at 02:07 PM
oops. for "P" read "1-P".
Posted by: vlorbik | December 09, 2005 at 02:08 PM
yeah, vlorbik, i think you're right...i thought of that recently. .1 is the probability that the first will repeat. the probability that the the first two will repeat is .01, the first three, .001. clearly adding these up gives .111111.... or 1/9. but this seems too big, since more than one of those events could happen, so we have to subtract the probability of that, which is very hard because those probabilities arent independent. i also agree with your calculation, which means i think we have a lower and upper bound...a start!
Posted by: Polymath | December 10, 2005 at 11:51 AM
Actually, the E_n's aren't independent. To see why, suppose that we work in binary, and note that P(E_3) = 1/8. However, suppose that E_1 and E_2 hold; then by E_1, a_1 = a_2, and by E_2, a_2 = a_4. Therefore, a_1 = a_4, and P(E_3 | E_1 and E_2) = 1/4.
Posted by: Alon Levy | December 20, 2005 at 12:16 PM
i agree with you, actually, Alon, but thanks for a lucid explanation. the events that i think are independent are the (NOT E_n) events. if the first n digits don't repeat, then you have no information about whether any other string does or does not repeat. i think.
i also think i need a serious probabilitician (?) to tackle this one...because i'm getting lost in it, and it's my own dang problem.
Posted by: Polymath | December 20, 2005 at 02:33 PM
I don't have a real answer, but here's a point or two that may be helpful:
1) For starters, we can discard the trivial (small-N) cases, precisely because pi isn't in fact a "random" real, and in fact we know the first "few" digits. It's just that its decimal *representation* has properties similar to a random stream of digits.
2) What you're looking for is the "probability" that there exists an integer N such that the N digits of pi starting at digit N (0-based) are successively identical to the first N digits. For any given N (where digits N and following are initially "unknown"), this would initially appear to be 10^(-N), which approaches 0 geometrically as N increases.
3) This property would be similar for pi/10, and that simplifies the exponents, so:
The conjecture would imply that there exists a (fairly large) integer N, another integer Q between 10^N and 10^(N-1), and a real value R less than 10^(-2N) such that:
pi/10 = (Q + Q/(10^N)) /10^N + R
In practice, Q has less range than given above, because as I said, we know the first few digits of pi. For example, Q must be between .314159 and .314160 times 10^N, and we can narrow those limiting ratios by supplying more digits.
Now at this point my own math expertise runs aground upon the long years since I attended college. Even so, I suspect the above features may well collide (or collude) with some other known feature of pi. Any more ideas?
Posted by: David Harmon | July 04, 2006 at 06:13 PM
This may sound a bit silly, but a certain number theory professor I had was of the opinion that pi hasn't actually been proven to be irrational, in the same way that sqrt(2) can be proven to be irrational...
Posted by: Coconuts | July 05, 2006 at 11:14 PM
Here are the first few probabilities for binary strings of length 2N:
1: 0.5 = 2/4
2: 0.625 = 10/16
3: 0.6875 = 44/64
4: 0.7109375 = 182/256
5: 0.720703125 = 738/1024
6: 0.7255859375 = 2972/4096
7: 0.727783203125 = 11924/16384
8: 0.7288818359375 = 47768/65536
9: 0.7294235229492188 = 191214/262144
10: 0.7296905517578125 = 765136/1048576
11: 0.7298240661621094 = 3061104/4194304
12: 0.7298904657363892 = 12245530/16777216
13: 0.7299235761165619 = 48984342/67108864
14: 0.7299401015043259 = 195941804/268435456
Looks like 0.73? That's pretty rigorous, I'd say. It couldn't be any other number... I mean, look how slow it's growing, and there's no nice number just above 0.73, right? Or maybe it's 0.72999..., which we know is less than 0.73.
Anyway, if someone can find a sequence those numerators go in, and prove that sequence correct, it can probably be generalized to a base 10 random string.
Posted by: GreedyAlgorithm | July 06, 2006 at 01:33 AM
0.72999..., which we know is less than 0.73.
Oh man, not THAT again!
Posted by: Thingummy | August 01, 2006 at 08:23 AM
I asked this question in livejournal's mathematics community (link: http://community.livejournal.com/mathematics/869682.html ). It appears the probability for a random base-10 string to have this property is about 0.1099989899899190110911.
Posted by: GreedyAlgorithm | August 02, 2006 at 11:23 AM
Hmm. For some odd reason this made me think of Penrose tilings. In a Pensorse universe, if I remember correctly, the universe is infinite and nonrepeating (like pi).
However, any SUBSET of the universe exists in multiple locations.
If I recall correctly (correct me, someone, if I'm wrong here) the shortest distance from the edge of a pattern (call it Pattern A) to the edge of an IDENTICAL Pattern A is linearly related to.... damn, can't remember if it's the pattern's diameter or area. Anyway. Could a similar proof be provided for pi?
Posted by: Sailorman | September 11, 2006 at 04:03 PM
doesn't pi continue on forever? if so why isn't it called infinity, because infinity continues forever.
Posted by: Caity | January 17, 2007 at 05:54 PM
Caity: its decimal expansion continue forever. But pi is still greater than 3 but less than 4, and so certainly not 'infinity'. This is because 0.1 < 1, so 3.1 < 4, 3.14 < 3.1, and so on.
As for infinity, that's not even a number really. It's a concept for 'the largest number', which of course can't actually be evaluated. Just because a number has an expansion going on forever, that doesn't mean it is infinity (the largest number). That's like saying crabs are fish because they both live in water.
Posted by: Matt | February 24, 2007 at 10:32 AM