Finding 2013 in Pi | Hacker News Reader

Finding 2013 in Pi

johndcook.com

46 pointswmat8 comments

http://www.angio.net/pi/piquery

Assuming the digits of pi are randomly distributed, any finite digit sequence can be found in pi.

The probability any sequence of length d is found in N digits of pi is 1 - 1/exp(N*0.1^d) (Poisson distribution for approximating the binomial). Then the limit as N approaches infinity is 1 for any finite d.

Amusing fact: the probability that a sequence can be found is not equal for all sequences.

A simple example: 2 binary digits in binary sequences of length 3. There are eight binary sequences of length 3:

3 of those contain '00' but 4 of them '01'. Reason for the discrepancy is that one of those with '00' has 2 overlapping occurrences, but is counted only once. You get this as soon as overlap can occur, i.e. when the sequence to be found starts with x digits that it also ends with.

Of course, none of this matters, especially not when d << N, which it will be if N goes to infinity.

Also, the mathematical term is 'normal number' (http://mathworld.wolfram.com/NormalNumber.html), and we do not know whether pi is normal.

The probability of an event being 1 is _not_ the same thing as that event being completely certain. For example, if you pick a random real number between 0 and 1, the probability of getting something rational is zero. It's clearly not impossible, though.

Do you know of any proof for that? My math intuition is telling me that randomly picking a real number is guarenteed to be irrational, based on the fact that there is an uncountable infinity real numbers, but only a countable infinity of rational numbers. But, without assuming a probability of 0 means impossible, I do not know how to go about proving/disproving this.

We can't really pick "random real numbers" in any practical sense, so this is pretty much a theoretical distinction. It's essentially a matter of definition. The rational numbers have probability zero of being drawn, but they still lie in the sample space.

One way to see it is this: The probability of picking any particular point in the interval is 0. But that doesn't mean that picking that point is impossible. _Some_ point has to show up when you pick one at random.

(The digits of pi are definitely not randomly distributed, since they can be generated by a deterministic algorithm; and a randomly distributed infinite digit sequence need not have that specific probability of finding a d-length sequence in the first N digits, unless the random distribution is specifically uniform. Someone is correct that the relevant term here is 'normal'.)

He buried the lede!

   In fact, no one has proved that any particular number is
   normal. However, we do know that almost all numbers are 
   normal. That is, the set of non-normal numbers has 
   Lebesgue measure zero.

Reply on news.ycombinator.com