"Random" pi digits and Mahler's theorem
r.e.s.
are "random" in some (or all) integer bases b >= 2. One
way of posing the question is to ask whether the digits
behave statistically "like" a realization of a sequence
of iid rv's uniformly distributed on {0, 1, ..., b-1}.
A fact sometimes used to argue in the negative is a
theorem of Mahler stating that for all integers p,q > 1,
|pi - p/q| > 1/q^42. For example, a consequence of the
theorem is that given any n, the next 41*n digits after
the nth digit cannot all be zero -- which seems to
contradict statistical independence.
But just how unlikely is this very same behavior with
a corresponding sequence of iid random variables?
In other words ...
If X is uniform on (0,1), then what is the value of P=
pr( for all integers p,q > 1, |3+X - p/q| > 1/q^42 )?
Until P is shown to be "small" in some sense (which it
may turn out to be), it seems to me that the argument
based on Mahler's theorem is moot.
--r.e.s.
Herman Rubin
r.e.s. <r...@ZZmindspring.com> wrote:
...................
>But just how unlikely is this very same behavior with
>a corresponding sequence of iid random variables?
>In other words ...
>If X is uniform on (0,1), then what is the value of P=
>pr( for all integers p,q > 1, |3+X - p/q| > 1/q^42 )?
P < \sum 2/q^42 < .5/10^12
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
Robert Israel
Herman Rubin <hru...@odds.stat.purdue.edu> wrote:
>In article <qKs3c.12089$%06....@newsread2.news.pas.earthlink.net>,
>r.e.s. <r...@ZZmindspring.com> wrote:
> ...................
>>But just how unlikely is this very same behavior with
>>a corresponding sequence of iid random variables?
>>In other words ...
>
>>If X is uniform on (0,1), then what is the value of P=
>>pr( for all integers p,q > 1, |3+X - p/q| > 1/q^42 )?
> P < \sum 2/q^42 < .5/10^12
Herman, I think you did the wrong inequality: that would be
a bound on pr{ for some integers p,q > 1, |3+X - p/q| < 1/q^42 }.
So r.e.s.'s P > 1 - .5/10^12.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
r.e.s.
> Herman Rubin <hru...@odds.stat.purdue.edu> wrote:
> >r.e.s. <r...@ZZmindspring.com> wrote:
> >>If X is uniform on (0,1), then what is the value of P=
> >>pr( for all integers p,q > 1, |3+X - p/q| > 1/q^42 )?
>
> > P < \sum 2/q^42 < .5/10^12
>
> Herman, I think you did the wrong inequality: that would be
> a bound on pr{ for some integers p,q > 1, |3+X - p/q| < 1/q^42 }.
> So r.e.s.'s P > 1 - .5/10^12.
If the argument above is what it seems, I believe the
bound it gives is slightly weaker than the one stated.
1 - P
= pr(exist integers p,q > 1, |X - (p/q-3)| <= q^-42)
<= sum( pr(|X - (p/q-3)| <= q^-42), p,q > 1 )
<= sum( 2 q^-42 + (q-1)2 q^-42, q > 1 ) [*]
<= sum( 2 q^-41, q > 1)
< 0.909... 10^-12
The line marked [*] is by noting that for each (p,q),
the contribution to the sum is 0, q^-42, or 2 q^-42,
and that for given q, the second value occurs 2 times
(p=3q, p=4q) while the third value occurs q-1 times
(3q < p < 4q). An approximate bound is then
P > 1 - 10^-12.
I think this is a very interesting result, viz., that
practically every real number x in the interval (3,4)
satisfies a "Mahler-like" theorem just as pi does:
For all integers p,q > 1, |x - p/q| > 1/q^42.
Also, ISTM that P > 1 - 10^-12 is strong enough to
undermine the argument (based on Mahler's theorem)
that the digits of pi are not "random" in the sense
stated in my original posting. (Of course, there are
senses in which the digits of pi aren't random --
this just doesn't seem to be one of them.)
--r.e.s.
r.e.s.
Theorem.
Let X be uniformly distributed on interval (a, b), where a and b
are integers, and let m be a real number > 1. Then
pr( exist integers p,q > 1, |X - p/q| <= 1/q^m ) <= 2(Zeta(m)-1)
where Zeta is the Riemann Zeta function.
Proof (sketch):
pr( exist integers p,q > 1, |X - p/q| <= 1/q^m )
<= sum( pr(|X - p/q| <= 1/q^m, integers p,q > 1 ) (subadditivity)
<= sum( 2(1/q^m)/(b-a) + (q(b-a)-1)(2/q^m)/(b-a), q > 1) [*]
<= sum( 2/q^(m-1), q > 1 )
<= 2 (Zeta(m) - 1)
where [*] follows by noting the cases summarized in the following
table, each case corresponding to the joint occurrence of the
conditions indicated in the first two columns of a row:
contrib. to sum
p/q - 1/q^m p/q + 1/q^m cases #cases (per case)
-----------------------------------------------------------------
<= a > a p = aq 1 (1/q^m)/(b-a)
< b >= b p = bq 1 (1/q^m)/(b-a)
> a < b aq < p < bq q(b-a)-1 (2/q^m)/(b-a)
other other other 0
-----------------------------------------------------------------
QED.
Some examples:
m 2 ( Zeta(m) - 1 )
----------------------
4 0.40411...
5 0.16464...
6 0.73855... 10^-1
7 0.34686... 10^-1
8 0.16698... 10^-1
9 0.81547... 10^-2
10 0.40167... 10^-2
15 0.12249... 10^-3
20 0.38164... 10^-5
30 0.37253... 10^-8
40 0.36379... 10^-11
42 0.90949... 10^-12
--r.e.s.
r.e.s.
Extending the previous results (well-known, no doubt) ...
Theorem.
Let X be uniformly distributed on interval (a, b), where a and b
are integers, and let m be a real number > 1. Then
pr( exist integers p,q > 1, |X - p/q| <= 1/q^m ) <= 2(Zeta(m)-1)
where Zeta is the Riemann Zeta function.
Proof (sketch):
pr( exist integers p,q > 1, |X - p/q| <= 1/q^m )
<= sum( pr(|X - p/q| <= 1/q^m, integers p,q > 1 ) (subadditivity)
<= sum( 2(1/q^m)/(b-a) + (q(b-a)-1)(2/q^m)/(b-a), q > 1) [*]
<= sum( 2/q^(m-1), q > 1 )
<= 2 (Zeta(m-1) - 1)
where [*] follows by noting the cases summarized in the following
table, each case corresponding to the joint occurrence of the
conditions indicated in the first two columns of a row:
contrib. to sum
p/q - 1/q^m p/q + 1/q^m cases #cases (per case)
-----------------------------------------------------------------
<= a > a p = aq 1 (1/q^m)/(b-a)
< b >= b p = bq 1 (1/q^m)/(b-a)
> a < b aq < p < bq q(b-a)-1 (2/q^m)/(b-a)
other other other 0
-----------------------------------------------------------------
QED.
Some examples:
m 2 ( Zeta(m-1) - 1)
-----------------------