From: "r.e.s." Subject: Re: continued fraction terms for pi Date: Wed, 2 Jun 1999 11:12:46 -0700 Newsgroups: sci.math Keywords: Gauss-Kusmin distribution of partial quotients Thank you for the Mathematica output. Here's a summary of what it shows for integers 1,...,10 among the first 10,000 terms: --------------------------------------------- obs. obs. Gauss-Kusmin k freq. proportion probability discrepancy --------------------------------------------- 1 4206 0.4206 0.415037499 0.005562501 2 1672 0.1672 0.169925001 -0.002725001 3 883 0.0883 0.093109404 -0.004809404 4 597 0.0597 0.058893689 0.000806311 5 442 0.0442 0.040641984 0.003558016 6 282 0.0282 0.029747343 -0.001547343 7 224 0.0224 0.022720077 -0.000320077 8 186 0.0186 0.017921908 0.000678092 9 143 0.0143 0.014499570 -0.000199570 10 123 0.0123 0.011972642 0.000327358 --------------------------------------------- The rightmost two columns show the "fit" of probability = log(1+1/(k*(k+2)) / log(2) which is the limiting distribution lim pr(a_n=k) (n->oo) appearing in the Gauss-Kusmin theorem. See http://www.mathsoft.com/asolve/constant/kuzmin/kuzmin.html (This may be surprising, since the applicability of that theorem my be questioned in the present context.) -- r.e.s. (Spam-block=XX) Jim Ferry wrote ... : Also of possible interest: the frequencies of the terms : in the first 10, 100, 1000 and 10000 terms of the continued : fraction for pi (= [3,7,15,1,292,1,1,1,2,1,...]). I'd : expect the term n about 1/(n(n+1)) of the time (based on : an obvious, possibly naive heuristic) for a generic number. : Based on this, pi seems a little light on 1's. : In[7]:= a[10000] : Out[7]= {{4206, 1}, {1672, 2}, {883, 3}, {597, 4}, {442, 5}, : {282, 6}, {224, 7}, {186, 8}, {143, 9}, {123, 10}, {78, 11}, ============================================================================== From: "r.e.s." Subject: Distribution of Continued Fraction Terms for Pi Date: Wed, 2 Jun 1999 16:51:04 -0700 Newsgroups: sci.math Here's something remarkable about the empirical distribution of continued fraction terms for pi: The Gauss-Kumin limit- distribution fits very well -- but why should it? I believe that what we have here is the continued fraction parallel to the well-known pseudo-randomness in the decimal digits of pi. The relative frequencies of the first 10,000 terms for pi, according to Mathematica output posted by Jim Ferry in another thread, provide the following: ------------------------------------------------ obs. obs. Gauss-Kusmin k freq. proportion probability* discrepancy ------------------------------------------------ 1 4206 0.4206 0.4150 0.0056 2 1672 0.1672 0.1699 -0.0027 3 883 0.0883 0.0931 -0.0048 4 597 0.0597 0.0589 0.0008 5 442 0.0442 0.0406 0.0036 6 282 0.0282 0.0297 -0.0015 7 224 0.0224 0.0227 -0.0003 8 186 0.0186 0.0179 0.0007 9 143 0.0143 0.0145 -0.0002 10 123 0.0123 0.0120 0.0003 >10 1242 0.1242 0.1255 -0.0013 ------------------------------------------------ * probability = log(1+1/(k*(k+2)))/log(2) ------------------------------------------------ A simple goodness-of-fit test suggests that discrepancies of this magnitude or greater would be expected in at least 60% of random samples if the Gauss-Kumin limit-distribution were in fact the underlying distribution here. Theorem (Gauss-Kusmin): If x is uniformly distributed on the interval (0,1) and a_n(x) is the n-th continued fraction term for x, then lim(n->oo)(pr(a_n(x) >= k) = log(1+1/k)/log(2) for k=1,2,3,... (The limit distribution can also be written using pr(a_n=k) = pr(a_n>=k) - pr(a_n>=k+1) -> log(1+1/(k*(k+2)))/log(2).) But here's the peculiarity: To realize pr(a_n(x)=k) "empirically", one would generate x_1,x_2,... iid x, and examine the long-run proportion of these x_i for which a_n(x_i)=k, for sufficiently large n. This is in contrast to what we have in the observed distribution of terms for one particular x, namely for x = fractional part of pi. In a nutshell: It is not clear why the empirical distribution of a_1(x), a_2(x),... --i.e.*one x* & *multiple n*-- should so well approximate what is expected of the empirical distribution of a_n(x_1), a_n(x_2),... --i.e.*one n* & *multiple x*. In other words, it is not clear why the successive terms for pi mimic a sequence formed by taking a single "remote" term from each of a succession of numbers drawn uniformly at random from (0,1). ("Remote" meaning "sufficiently far into the sequence of terms for that number".) But the consequence seems to be that pi has a continued fraction behavior that parallels the well-known pseudo-randomness in its decimal digits; if so, it would seem to have a more elegant flavor, since the continued fraction terms of pi are unique and independent of numerical representation. --- r.e.s. (Spam-block=XX) ============================================================================== From: gerry@mpce.mq.edu.au (Gerry Myerson) Subject: Re: Distribution of Continued Fraction Terms for Pi Date: Thu, 03 Jun 1999 15:51:15 +1100 Newsgroups: sci.math In article <7j4g18$j28@sjx-ixn9.ix.netcom.com>, "r.e.s." wrote: => Here's something remarkable about the empirical distribution => of continued fraction terms for pi: The Gauss-Kumin limit- => distribution fits very well -- but why should it? => => Theorem (Gauss-Kusmin): => If x is uniformly distributed on the interval (0,1) => and a_n(x) is the n-th continued fraction term for x, => then lim(n->oo)(pr(a_n(x) >= k) = log(1+1/k)/log(2) => for k=1,2,3,... => => In other words, it is not clear why the successive => terms for pi mimic a sequence formed by taking a => single "remote" term from each of a succession of => numbers drawn uniformly at random from (0,1). => ("Remote" meaning "sufficiently far into the sequence => of terms for that number".) Gauss-Kuzmin can also be twisted to say that for all reals x outside of a set of measure zero the frequency of k as a partial quotient in the expansion of x is log(1+1/(k*(k+2)))/log(2). That set of measure zero contains all the rationals & the quadratic irrationals, but there's no reason to think it contains pi (and empirical evidence suggests that it isn't). Gerry Myerson (gerry@mpce.mq.edu.au) ============================================================================== From: "r.e.s." Subject: Re: Distribution of Continued Fraction Terms for Pi Date: Thu, 3 Jun 1999 02:13:35 -0700 Newsgroups: sci.math Gerry Myerson wrote ... [most of previous article quoted --djr] This seems more than a merely semantic "twisting". All sources I've found for the Gauss-Kuzmin theorem refer to a *limit* distribution equivalent to lim(n->oo) pr{x: a_n(x)=k} = log(1+1/(k*(k+2)))/log(2), k=1,2,..., where a_n(x) = n-th term (partial quotient) of the continued fraction for x. How can this be seen as addressing the distribution of terms in the continued fraction of a *particular* x? (It's a *set* of x that has the limit-probability.) I vaguely recall this as a kind of ergodic property.(?) -- r.e.s. (Spam-block=XX) ============================================================================== From: "r.e.s." Subject: Re: Distribution of Continued Fraction Terms for Pi Date: Thu, 3 Jun 1999 12:03:37 -0700 Newsgroups: sci.math Keywords: Gauss-Kuzmin theorem OK, I've convinced myself that the theorem you state is at least made plausible by Gauss-Kuzmin in the form I cited it. For example, using "term" to mean "partial quotient", an instance of the Gauss-Kuzmin theorem is that there exists an N such that for any n>N, "1.00...%" of all x in (0,1) have their n-th term equal to eleven. (log_2(1+1/(11*13))=0.0100...) But since this is true "for any n>N", we can say loosely that 1% of *all* the "remote" terms of (almost) *all* x in (0,1) are equal to eleven. And the "almost" is reasonable because the original statement about "1.00...%" could be true even if there were an exceptional set of Lebesque measure 0. (But I do think you need to state the result as a limit for n->oo, i.e. to refer to sufficiently "remote" terms in the partial fractions.) And I wonder what it would take to make the argument rigorous. (I still suspect ergodicity is involved.) -- r.e.s. (Spam-block=XX) r.e.s. wrote ... [previous article --djr] ============================================================================== From: "r.e.s." Subject: Re: 355/113 Is there a better... Date: Fri, 16 Jul 1999 17:41:05 -0700 Newsgroups: sci.math Kurt Foster wrote ... [snip] : A great many partial quotients in the SCF for pi are known (but not by : me). Perhaps one of the later ones is 292 or greater; this might give a : larger value of c in (2) for pi. Anyone have that info handy? In the first 2,000,000 terms (partial quotients), about 10,000 (~0.49%) are >=292. For the first 2,000,000 terms, I've confirmed that the proportion of terms >=k is log(1+1/k)/log(2), k=1,2,..., to within bounds that would be expected if this were indeed the underlying distribution. This is the Gauss-Kusmin distribution, which would be the limit distribution for the terms if pi were in fact normal. -- r.e.s. XXrs.1@mindspring.com (Spam-block=XX)