lotus

previous page: 416 probability/particle.in.box.p
  
page up: Puzzles FAQ
  
next page: 418 probability/random.walk.p

417 probability/pi.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

417 probability/pi.p


Are the digits of pi random (i.e., can you make money betting on them)?

probability/pi.s

No, the digits of pi are not truly random, therefore you can win money
playing against a supercomputer that can calculate the digits of pi far
beyond what we are currently capable of doing. This computer selects a
position in the decimal expansion of pi -- say, at 10^100. Your job is
to guess what the next digit or digit sequence is. Specifically, you
have one dollar to bet. A bet on the next digit, if correct, returns
10 times the amount bet; a bet on the next two digits returns 100 times
the amount bet, and so on. (The dollar may be divided in any fashion,
so we could bet 1/3 or 1/10000 of a dollar.) You may place bets in any
combination. The computer will tell you the position number, let you
examine the digits up to that point, and calculate statistics for you.

It is easy to set up strategies that might win, if the supercomputer
doesn't know your strategy. For example, "Always bet on 7" might win,
if you are lucky. Also, it is easy to set up bets that will always
return a dollar. For example, if you bet a penny on every two-digit
sequence, you are sure to win back your dollar. Also, there are
strategies that might be winning, but we can't prove it. For example,
it may be that a certain sequence of digits never occurs in pi, but we
have no way of proving this.

The problem is to find a strategy that you can prove will always win
back more than a dollar.

The assumption that the position is beyond the reach of calculation
means that we must rely on general facts we know about the sequence of
digits of pi, which is practically nil. But it is not completely nil,
and the challenge is to find a strategy that will always win money.

A theorem of Mahler (1953) states that for all integers p, q > 1,

		-42
  |pi - p/q| > q

This says that pi cannot have a rational approximation that is
extremely tight.

Now suppose that the computer picks position N. I know that the next
41 * N digits cannot be all zero. For if they were, then the first N
digits, treated as a fraction with denominator 10^N, satisfies:

|pi - p / 10^N| < 10^(-42 N)

which contradicts Mahler's theorem.

So, I split my dollar into 10^(41N) - 1 equal parts, and bet on each of
the sequences of 41N digits, except the one with all zeroes. One of
the bets is sure to win, so my total profit is about 10(^-41N) of a
dollar!

This strategy can be improved a number of ways, such as looking for
other repeating patterns, or improvements to the bound of 42 -- but the
earnings are so pathetic, it hardly seems worth the effort.

Are there other winning strategies, not based on Mahler's theorem? I
believe there are algorithms that generate 2N binary digits of pi,
where the computations are separate for each block of N digits. Maybe
from something like this, we can find a simple subsequence of the
binary digits of pi which is always zero, or which has some simple
pattern.

 

Continue to:













TOP
previous page: 416 probability/particle.in.box.p
  
page up: Puzzles FAQ
  
next page: 418 probability/random.walk.p