It is widely conjectured that $\pi$ is normal in base $2$.

But what about the law of the iterated logarithm?

Namely, if $x_n$ is the $n$th binary digit of $\pi$, does it seem likely (from computer experiments for example) that the following holds? $$\limsup_{n\rightarrow\infty} \frac{S_n }{\sqrt{n\log\log n}}=\sqrt{2}\quad\text{where}\quad S_n=2(x_1 + \ldots + x_n) - n$$

What about other (conjectured) normal numbers like $e$ and $\sqrt{2}$?

I am sorry if this is too easy, but I tried to search for it and I could not find in on the Internet. I suppose I could run an experiment myself, but I assumed this is well known, and I would need to brush up on my programming skills to do so...

Update 8/9/2013:

I found a website with the first 32,000 binary digits of $\pi$ and (using a spreadsheet program) graphed out the average of the bits $S_n/n$, comparing it to $\sqrt{\frac{2 \log \log n}{n}}$. The results were inconclusive. The average never got close to $\sqrt{\frac{2 \log \log n}{n}}$ (except at the very beginning when it was way past it). However, I had the same result with a source of randomness (the one built into the spreadsheet program). My conclusion is that 32,000 bits is not enough to see if the law of the iterated logarithm (experimentally) holds for $\pi$. (The picture in the Wikipedia article uses at least $10^{50}$ bits, and the pattern is clear at about $10^{12}$ bits. However, I don't know where to get even 1,000,000 binary digits of $\pi$ on the Internet.

[End Update]

Also, I am sorry that I really don't know how to properly tag this.

  • $\begingroup$ I deleted my answer. I had not noticed that the question was about base $2$. $\endgroup$ – Omnomnomnom Aug 8 '13 at 1:16
  • $\begingroup$ I'd be interested in other bases as well. (Obviously, the corresponding $S_n$ would be scaled and shifted differently.) $\endgroup$ – Jason Rute Aug 8 '13 at 3:15
  • $\begingroup$ Hadn't said much, just that the mean of the digits would be $4.5$ and the variance would be $8.25$ in base $10$ $\endgroup$ – Omnomnomnom Aug 8 '13 at 4:20
  • $\begingroup$ My understanding is that the binary expansions of $\pi$, $e$, $\sqrt2$ have passed every test of randomness to which they have ever been subjected. $\endgroup$ – Gerry Myerson Aug 8 '13 at 11:38
  • $\begingroup$ David Bernier asked this question in the Usenet newsgroup sci.math in January, 2000, but got no answers. $\endgroup$ – Gerry Myerson Aug 8 '13 at 11:42

I favourite'd this two years ago and recently stumbled upon it again. Here's some code I wrote to answer this numerically.

enter image description here

  • The dotted line is $\sqrt{2 \log\log n/n}$
  • The solid line is $S_n/n$
  • $S_n = 2 \sum_{k=1}^n x_k - n$ where $x_k$ is the k-th decimal digit of Pi in binary.

You should be able to zoom in by running the code. You'll need matplotlib and numpy. I used y-cruncher to generate the digits.

  • $\begingroup$ This is very helpful! Unfortunately, this graph doesn't clearly make the LIL behavior stand out (or its refutation stand out). It probably just takes more digits than is feasible to work with to get a good graph, or I am being too picky in what a "good graph" looks like. I think it would be interesting to compare this to the Wikipedia picture I linked to in my question, and to use similar scales for the axes (that is scales which are approximations of log that make the dotted lines almost straight), or even to put this graph (as is) side by side with a random Bernoulli process and compare. $\endgroup$ – Jason Rute Mar 3 '15 at 17:33
  • 1
    $\begingroup$ I should say that I also tried it with $10^{12}$ binary digits, and the result looked more or less the same. I'm not too familiar with number theory beyond the elementary setting, but I should ask, is it conjectured that $2x_n-1$ has unit variance? If I have a big hard disk available to me in the near future I can set up an experiment with far more digits. It shouldn't be too hard to fix the scaling on the y-axis. $\endgroup$ – parsiad Mar 3 '15 at 18:20
  • $\begingroup$ I don't know about your conjecture, but it's a good MSE question. :) $\endgroup$ – Jason Rute Mar 3 '15 at 21:45
  • $\begingroup$ I checked: numerically, $x_n$ has variance 1/4, so the answer would be "yes, probably." $\endgroup$ – parsiad Mar 4 '15 at 19:36

I am not sure if this is the answer you are looking for (or if you want something more computational specifically for $\pi$), but if a number is normal in base 2, then the sum $S_n$ that you defined above will satisfy the law of the iterated logarithm.

First, let $X_i$ be the $i$th binary digit. Assuming normality, the digits $X_i$ are iid and $X_i\sim\text{Bernoulli}(1/2)$. Then, let $Y_i = 2X_i-1$. Consequently, $\mathrm{EY_i=0}$, $\text{Var}(Y_i)=1$, and $S_n = Y_1+\ldots+Y_n$. Consequently, $$ \mathrm{P}\left( \limsup_{n\rightarrow\infty} \frac{S_n}{\sqrt{2n\log\log n}}=1 \right)=1. $$ This result and an accompanying proof, which relies on the result for Brownian motion and Skorokhod embedding, can be found in Section I.16 of Rogers and Williams' Diffusions, Markov Processes and Martingales: Volume 1.

In general, if a number is normal in base $b$, then the digits $X_i$ have a discrete uniform distribution on $0,1,2,\ldots,b-1$. Hence, $\mathrm{E}X_i=\frac{1}{2}(b-1)$ and $\text{Var}(X_i) = \frac{1}{12}(b^2-1)$. Therefore, setting $$ Y_i = \frac{2\sqrt{3}\left(X_i-\frac{1}{2}(b-1)\right)}{\sqrt{b^2-1}}, $$ gives $Y_i$ zero mean and unit variance. The sum of the $Y_i$ $$ S_n = \sum_{i=1}^n Y_i = \frac{2\sqrt{3}}{\sqrt{b^2-1}}\sum_{i=1}^n X_i -n\sqrt{3}\sqrt{\frac{b-1}{b+1}}, $$ once again satisfies the law of the iterated logarithm.

  • $\begingroup$ How can $X_i$ be iid? It is a deterministic sequence? I am not convinced of your argument that every normal number satisfies LIL. $\endgroup$ – Jason Rute May 18 '14 at 23:58
  • $\begingroup$ Perhaps I am oversimplifying this. I define a normal number as one where the probability of observing a substring of a fixed length is uniform across that length. This is, I believe, equivalent to treating each digit as a Bernoulli (or discrete uniform) rv. Then, $\pi$ or $\sqrt{2}$, assuming the conjecture that they are normal, could be treated as a specific realization of these random variables. If you simulate coin flips on your computer, you will get an actual sequence out, but its behavior will be that of a random sequence. Once a random variable is realized, then it is deterministic. $\endgroup$ – Adam B Kashlak May 19 '14 at 20:39
  • 4
    $\begingroup$ You are mixing up a normal number and a Bernoulli process. I am pretty sure, for example, that Champernowne's constant, 0.11011100101110111... is normal, but doesn't satisfy LIL. $\endgroup$ – Jason Rute May 20 '14 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.