## Probability of leading N digits of 2^n

February 19, 2010

Okay, so there was this puzzle which pops out from the ergodic seminar a while ago:

What’s the probability for the leading digit of $2^N$ being $k \in \{1,2, \cdots, 9 \}$ as $N \rightarrow \infty$?

It’s a cute classical question in ergodic theory, the answer is $\log_{10}(k+1) - \log_{10}(k)$.

Proof: (all log are taken in base $10$)
Given a natural number $N$, let $\log(N) = k+\alpha$ where $k \in \mathbb{Z}, \ \alpha \in [0, 1)$, since $N = 10^{\log(N)} = 10^{k+\alpha} = 10^k \cdot 10^\alpha$, $1 \leq 10^\alpha < 10$, we see that the first digit of $N$ is the integer part of $10^\alpha$.

The first digit of $2^n$ is the integer part of $10^{ \log(2^n) \mod{1} } = 10^{ n \cdot \log(2) \mod{1}}$.

For $k \in \{1, 2, \cdots, 9 \}$, leading digit of $2^n$ is $k$ iff $k \leq 10^{ n \cdot \log(2) \mod{1}} < k+1$ iff $\log(k) \leq n \cdot \log(2) \mod{1} < \log(k+1)$.

Let $\alpha = \log(2)$ irrational, let $\varphi: S^1 \rightarrow S^1$ be rotation by $\alpha$ ($S^1$ is considered as $\mathbb{R} / \mathbb{Z}$, $\varphi(x) = x+\alpha$). All orbits of $\varphi$ are uniformly distributed i.e. for any $A \subseteq S^1, \forall x \in S^1$, $\displaystyle \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N \chi_A(\varphi^n(x)) = m(A)$

In particular we have $\displaystyle \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N \chi_{[\log(k), \log(k+1))}(\varphi^n(0))$ $= m([\log(k), \log(k+1)) = \log(k+1) - \log(k)$

Therefore the limiting probability of first digit of $2^n$ being $k$ is $\log(k+1) - \log(k)$.

To generalize, Pengfei asks Given some two digit number K, what’s the probability of the first two digits being K?

The natural thing to do is take base $100$, however one soon figured out there is a problem since we don’t really want to count “$0x$” as the first two digits when the number of digits is odd.

I found the following trick being handy:

When the number of digits is odd, we may consider the orbit of $\log_{100}(10) = 1/2$ under the rotation $\log_{100}(2)$. This will give us the first digit in base $100$ of $2^n \cdot 10$ which takes even number of digits precisely when $2^n$ has odd number of digits, the first two digit is the same as the original. Since this orbit is also uniformly distributed, we get the probability of $2^n$ having odd number of digits and the first two digit is $K \ (10 \leq K < 100)$ is $\log_{100}(K+1) - \log_{100}(K)$.

Applying the usual procedure to the orbit of $0$ in base $100$ gives us the probability of $2^n$ having even number of digits and the first two digit is $K$ is $\log_{100}(K+1) - \log_{100}(K)$.

Hence the actual probability of $2^n$ starting with $K$ is just the sum of the two that’s $2 \cdot (\log_{100}(K+1) - \log_{100}(K))$.

The same works for finding the distribution of the first $n$ digits. i.e. taking the number of digit mod n, we would be summing the probability $\log_{10^n}(K+1) - \log_{10^n}(K) \ n$-times for each $10^{n-1} \leq K < 10^n$, the limiting probability is $n \cdot (\log_{10^n}(K+1) - \log_{10^n}(K))$.

Remark: One can first calculate the probability of $2^n$ having odd number of digit. This would be the orbits of $0$ under rotation $\log_{100}(2)$ inside the interval $[0, \log_{100}(10)$ which is $[0, \frac{1}{2})$. The limiting probability is $1/2$ (make sense since this says about half of the time the number of digits is odd)

In general, the number of digits being $k \mod{n}$ is $1/n$ for each $k$.

For some reason, professor Kra was interested in figuring out the distribution of the ‘middle’ digit…which I’m not exactly sure how one would define it.