Probability of leading N digits of 2^n

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.

One thought on “Probability of leading N digits of 2^n”

hehe this was in my Analysis take-home midterm just a week ago. But it is provided that orbits of an irrational are equidistributed in (0,1), and that log2 is irrational…

LikeLike

Area777

Chasing dreams from mathematics to the real world

Probability of leading N digits of 2^n

One thought on “Probability of leading N digits of 2^n”

Leave a Reply Cancel reply

Share this:

Like this:

One thought on “Probability of leading N digits of 2^n”

Leave a Reply Cancel reply