A fun problem by Arnold using the Poincaré recurrence theorem

Question

I came across this problem by V. I. Arnold while studying his classical mechanics book.

Consider a sequence where the $n^{th}$ term is made up by considering the first digit of $2^n$, the first terms are: $1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4,.. $

By using the Poincaré recurrence theorem, say whether (prove that) the number $7$ will appear and which number between $7$ and $8$ will appear more often, and how much.

Now we all know this theorem is very useful in many areas of Physics, especially Statistical Mechanics, but here Arnold is really stressing that it also has an abstract value!

Maybe it's a super easy problem, but I thought about it a bit and couldn't find a decent way to do it.. it's crucial to solve the problem by using this theorem, I'm sure it's easier to do it another way but the goal is to show how applicable the recurrence's theorem is.

Answer 1

I remember that one, as well as the questions about how high animals can jump (if animals are approximated by boxes of course)! Really lovely book. Anyways! We will want to write $2^n=a\times10^k$, $1\leq a< 10$, and then take the base 10 logarithm, to get $n \log_{10}2=k+\log_{10}a$. Now I'll just say that the $k$ is unimportant, so we have $n \log_{10}2\equiv \log_{10}a \,(\mod 1)$. The modulo should remind you of a certain geometrical object, so you can apply the theorem and note that probablities are proportional to lengths, and you should find for example $$P_7=P(7\leq a< 8)=P(\log_{10}7\leq a< \log_{10}8)=\log_{10}8-\log_{10}7\approx 5.8\%,$$ and similarly $P_8\approx 5.1\%$, which is a bit unintuitive. I had to tell my computer to do a little loop and confirm it, as I expected there to be more 8's than 7's!

Answer 2

A hint:

One has $x_n:=\log_{10}\bigl(2^n\bigr)=n\>\kappa$, where $\kappa:=\log_{10}(2)$ is irrational. It follows that the $x_n$ are uniformly distributed modulo $1$. See also Benford's law.

You don't need Poincaré's recurrence theorem for this.

Answer 3

$2^{46}=70368744177664$ so 7 does definitely appear.

The first digit of a number $x$ can be found by:

$$\left\lfloor10^{frac\left(\log x\right)}\right\rfloor$$

Here $\log$ is the base 10 logarithm. Thus the first digit is 7 iff:

$$\log7 \le frac\left(\log x\right) \lt \log8$$

And it is 8 iff:

$$\log8 \le frac\left(\log x\right) \lt \log9$$ Now since

$$\log{2^n}=n\log2$$

We get that any range of values within $\left[0;1\right)$ will be represented, and their frequency will be proportional to the size of the range (ie. the distribution is uniform). Since $\log9-\log8\lt\log8-\log7$, we should see the digit $7$ more often than $8$, and in general, the smaller the digit, the more often it will appear.

Indeed, I made my computer calculate the first digits of $2^n$ for $0\le n\lt 1000000$, and it gave me: $$ \begin{matrix} 1: & 301030 \\ 2: & 176093 \\ 3: & 124937 \\ 4: & 96911 \\ 5: & 79182 \\ 6: & 66947 \\ 7: & 57990 \\ 8: & 51154 \\ 9: & 45756 \\ \end{matrix} $$

You will notice that these counts are all roughly equal to $1000000\cdot\left(\log{\left(d+1\right)}-\log{d}\right)$