3
$\begingroup$

In the book Probability by Geoffrey Grimmett and Dominic Welsh, One of the exercise in page 19 says: Any number $w\in[0,1]$ has decimal expansion $w=0.x_1x_2...$, and we write $f_k(w,n)$ for the proportion of times that the integer $k$ appears in the first $n$ digits in this expansion. We call a number normal if $f_k(w,n) \rightarrow\frac{1}{10}$ as $n \rightarrow \infty$ for $k=1,2,3,4,5,6,7,8,9$. Prove that 0.123456789101112... is normal.

So the number of times $1$ appear in the first $9$ digits after the decimal point is 1, then in the next $90$ digits is $19=10+1+8*1$, then the number of times $1$ appears in the next 900 digits is $100+19+19*8$...

Here is what I tried:So if we look at the first $10^i$ digits after the decimal expansion, and we know the number of 1 in the first $i-1$ digits is $f_{i-1}$. we get the number of ones that appear is $\frac{10^{i-1}+f_{i-1}+f_{i-1}*8}{10^i}$. Here $f_i=10^{i-1}+f_{i-1}+f_{i-1}*8$ with $f_1=1$. So it boils down to solve the recurrence. And relate the recurrence equation to the case of analyzing the first $n$ digits for arbitrary $n$ and not just powers of 10.

$\endgroup$
  • 2
    $\begingroup$ For searchability, this is the base-10 Champernowne constant. $\endgroup$ – Henning Makholm Jun 28 at 17:28
  • $\begingroup$ The definition of normality is wrong; it should be $f_k(w,n)\to\frac{1}{10^{\|k\|}}$ where $\|k\|$ is the number of digits in $k$ (and there should be a "for all $k$" somewhere). $\endgroup$ – Henning Makholm Jun 28 at 17:30
  • $\begingroup$ Do you have any partial progress yourself? Something you've tried that didn't work? Any thoughts at all? $\endgroup$ – Henning Makholm Jun 28 at 17:32
  • $\begingroup$ I added the reference too the book, The definition I wrote is what is written in the question. Also, I edited the question to include some attempts. $\endgroup$ – user 42493 Jun 28 at 17:49
  • 1
    $\begingroup$ The definition does then not define the same concept as what people usually call "normal" numbers. According to your definition, $\frac{12562210}{101010101}=0.\overline{1243658790}$ would be normal, but it's far from normal in the usual sense. $\endgroup$ – Henning Makholm Jun 28 at 18:00
2
$\begingroup$

I think this is a great problem. Although the Champernowne constant $C$ is well-known as one of the few real numbers proven to be normal, I could not find a concise proof online. It is somewhat "obvious" that $C$ should be normal, but I think it is a challenge to prove it.

My approach was not to consider all indices $n \in \mathbb N$, but only those indices $(n_i)_{i\in\mathbb N}$ for which the Champernowne number truncated at $n_i$-th position reads off the first $i$ integers. For example, we set $n_{99}=189$ since the first $189$ digits of the Champoernowne number read off the first $99$ integers. Hopefully this diagram will make the sequence $(n_i)$ clear:

$$ \begin{array}{c|cccccc} C:& 1 & 2 & 3 & & 9 & 1 & 0 & 1 & 1 & & 9 & 9 & 1 & 0 & 0 & \ \\ \text{Label} & n_1 & n_2 & n_3 & \cdots & n_9 & & n_{10} & & n_{11} & \cdots & & n_{99} & & & n_{100} & \cdots\\ \text{Value} & 1 & 2 & 3 & & 9 & & 11 & & 13 & & & 189 & & & 192 \end{array} $$

A formula for $n_i$ is given by

$$ \begin{split} n(i) & = (i + 1 - B^{L(i)-1}) \cdot L(i) + (B-1)\sum_{d=1}^{L(i)-1} d B^{d-1} \\ & = (i+1) \cdot L(i) - \frac{B^{L(i)} - 1}{B-1} \end{split} $$

where $B$ is the base, and $L(i) = 1 + \lfloor \log_B(i) \rfloor$ gives the length of an integer (here, $\lfloor \cdot \rfloor$ is the floor function).

The change of perspective from the first $n$ indices to the first $i$ integers is helpful in deriving a counting function $c_k(n_i)$ which will count the number of times the digit $k$ appears in the first $i$ integers.

First, I derived a preliminary function $c_k^{(d)}(n_i)$ which counts the number of times the digit $k$ appears specifically in the $d$-th place of some integer, where $d=1,2,3,\dots$ (in base 10, the ones place, tens place, etc.) This one is not too difficult to calculate:

$$ c_k^{(d)}(n_i) = B^{d-1} \left \lfloor \frac{i+1}{B^d} \right \rfloor + \begin{cases} 0 & \text{if } 0 \leq m < kB^{d-1} \\ m - k B^{d-1} & \text{if } k B^{d-1} \leq m < (k+1) B^{d-1} \\ B^{d-1} & \text{otherwise} \end{cases} $$

where $0 \leq m < B^i$ satisfies $m \equiv i+1 \quad (\bmod B^d)$. This function is notationally dense, but seeing its plot, perhaps in Desmos, makes it clear. Now, the function $c_k(n_i)$ is the sum over each $d$:

$$ c_k(n_i) = \sum_{d=1}^{\infty} c_k^{(d)}(n_i) $$

(For practical purpose, you need only to compute the terms $d \leq 2 + \log_B(i)$.) Below I have plotted $c_k(n_i)$ in blue and $\frac{1}{10} n(i)$ in red (the expected limit) with $k=1$ and $i$ in $[0,10^{11}]$.

The convergence is quite erratic, at least by absolute difference, but I think the relative error is indeed vanishing. Now, we may write

$$ f_k(n_i) = \frac{c_k(n_i)}{n_i} $$

The solution is not complete, however, for taking the limit as $i \rightarrow \infty$ only addresses a narrow subsequence of all $n \in \mathbb N$. And although $f_k(n_i)$ is precisely equal to $1/B$ for all digits $k$ whenever $i$ is a power of $B$, this likewise does not imply convergence to $1/B$.

So, how to proceed? I imagine the counting function $c_k(n_i)$ could be extended to a more general function which takes as input any index $n$, not just the $n_i$ (which are relatively sparse). Perhaps, for arbitrary $n$, an improved counting function could take the form $$ c_k(n_i) + r_k(n) $$ where $n_i$ is the most recent integer index, satisfying $n_i \leq n < n_{i+1}$, and $r_k(n)$ acts like a "remainder" term, counting up any digits between $n_i$ and $n$ which are not yet part of a fully formed integer. Maybe you can make some progress on this problem.

$\endgroup$
  • $\begingroup$ Cool! thanks sir, I'm wondering how did you come up with the formula for $n(i)$ and $c_k^{(d)}(n_i)$ and how did you graph $c_1(n_i)$ as $c_1(n_i)$ is a infinite sum. Is the choice of the number of terms to add a numerical method. $\endgroup$ – user 42493 Jul 2 at 0:24
  • $\begingroup$ The formulas for $n(i)$ is the solution to a summation, which I just edited into the post, and $c_k^{(d)}(n_i)$ comes from thinking about when integers acquire new digits. I also used Desmos to help me generalize the formulas. Here are my plots: desmos.com/calculator/fllskpbvfl. Also, I think it may be easier to, instead of calculating the exact number of digits, to just prove that all numbers have the same proportion, hence they are equal, and since there are $B$ of them, their proportion is $1/B$. $\endgroup$ – M. Nestor Jul 2 at 23:12

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.