Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I deleted my answer. I had not noticed that the question was about base $2$. –  Omnomnomnom Aug 8 '13 at 1:16
    
I'd be interested in other bases as well. (Obviously, the corresponding $S_n$ would be scaled and shifted differently.) –  Jason Rute Aug 8 '13 at 3:15
    
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$ –  Omnomnomnom Aug 8 '13 at 4:20
    
My understanding is that the binary expansions of $\pi$, $e$, $\sqrt2$ have passed every test of randomness to which they have ever been subjected. –  Gerry Myerson Aug 8 '13 at 11:38
    
David Bernier asked this question in the Usenet newsgroup sci.math in January, 2000, but got no answers. –  Gerry Myerson Aug 8 '13 at 11:42

1 Answer 1

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.

share|improve this answer
    
How can $X_i$ be iid? It is a deterministic sequence? I am not convinced of your argument that every normal number satisfies LIL. –  Jason Rute May 18 at 23:58
    
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. –  Adam Kashlak May 19 at 20:39
3  
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. –  Jason Rute May 20 at 1:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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