Let $\alpha \in [0,9]\subset\mathbb{R}.$ Is the following set countable or uncountable:

The set of all (nonnegative) real numbers which, when written in decimal expansion form

$$k_1\ldots k_m\cdot k_{m+1}\ldots$$

where the $k_i$ are digits between $0$ and $9$, satisfy

$$\lim_{n\to\infty}\left( \frac{\sum_{j=1}^n k_j}{n} \right) = \alpha ?$$

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Mar 13 at 14:07
  1. There are uncountably many numbers with $\alpha = 0$.

Let $\{a_n\}$ be a strictly increasing sequence of natural numbers. For each sequence, we'll build a number with $\alpha=0$. Since there are uncountably many such sequences (in particular, the set of sequences s.t. $a_{n+1} = a_n + 1$ or $a_{n+1} = a_n + 2$ is uncountable), we can generate uncountably many numbers.

Let $s_n = \sum_{i=1}^n a_i$. Let $x$ be the number such that its $i$'th digit $x_i = 1$ iff $i = s_n$ for some $n$, and $x_i=0$ otherwise.

Then $\alpha(x) = 0$. It suffices to show that $\lim \frac n {s_n} = 0$ (it's the average up to $s_n$'th digit). It follows from the fact that $a_n \ge n$ and therefore $s_n \ge \frac {n^2} 2$.

  1. There are uncountably many numbers for any $\alpha \in (0, 1)$. Handling $\alpha \ge 1$ is trivial (just add $\lfloor\alpha \rfloor$ to all digits).

Consider digits between $s_{n-1}$ and $s_{n}$, There are $a_n$ such digits. Let $c_n \in \mathbb N$ s.t. $\frac {c_n} {a_n}$ is the closest to $\alpha$. Let ${c_n}$ digits between $s_{n-1}$ and $s_n$ be $1$ and the rest of the digits be $0$, then the average of these digits is $\frac {c_n} {a_n}$.

Since $a_n$ strictly increases, $\lim \frac {c_n} {a_n} = \alpha$. Therefore, for any $\epsilon$ there exists $n_0$ s.t. $\frac {c_n} {a_n} \in [\alpha - \epsilon, \alpha + \epsilon]$ for $n \ge n_0$. Then the average up to $s_n$ is \begin{align*} avg_{s_n} &= \frac {c_1 + \cdots + c_n} {s_n}\\ &= \frac {c_1 + \cdots + c_{n_0}} {s_n} + \frac {c_{n_0 + 1} + \cdots + c_{n}} {s_n} \\ &= \frac {c_1 + \cdots + c_{n_0}} {s_n} - \alpha \frac {s_{n_0}} {s_n} + \frac {\alpha s_{n_0} + c_{n_0 + 1} + \cdots + c_{n}} {s_n} \\ &\to 0 + 0 + \ell \in [\alpha - \epsilon, \alpha + \epsilon], \end{align*} since $$\alpha s_{n_0} + c_{n_0 + 1} + \cdots + c_{n} \ge \alpha s_{n_0} + a_{n_0 + 1} (\alpha - \epsilon) + \cdots + a_{n}(\alpha - \epsilon) \ge \alpha s_n - \epsilon s_n$$ (the same for $\alpha+\epsilon$). Since this holds for arbitrary $\epsilon$, $\lim avg_n = \alpha$.

Some technicalities

  1. For the limit to exist, we also need to consider all $n' \in [s_{n-1}, s_n]$. It suffices to guarantee that $a_n = o(s_{n-1})$, and I gave an example of such a family of sequences above.
  2. For $\alpha \in (0,1)$, I don't actually guarantee that the generated numbers are distinct. We can guarantee this with some adjustments, but it's simpler to do the following: generate one number, and then change its $s_n$'th digits to be either $0$ or $1$ (all combinations). As shown in the case $\alpha = 0$, it doesn't change the limit of the average.
  • 1
    $\begingroup$ I was about to post almost the same thing. I started with sequences of positive integers, which is obviously uncountable, took partial sums (an invertible operation) to get uncountably many strictly increasing sequences, and then took partial sums again, as you do, to get the thinning out sequence $s_n$. Your way of showing that the strictly increasing sequences are uncountable is very nice too. $\endgroup$ Mar 12 at 16:57
  • $\begingroup$ When you wrote, "Let $s_n = \sum_{i=1}^n a_n$." Did you mean: Let $s_n = \sum_{i=1}^n a_i$ ? $\endgroup$ Mar 12 at 18:39
  • $\begingroup$ Also, is $\{a_n\}$ a strictly increasing sequence of integers or real numbers? $\endgroup$ Mar 12 at 21:52
  • $\begingroup$ Yes, it should be $\sum_i a_i$. $a_i$ are natural numbers. $\endgroup$
    – Dmitry
    Mar 12 at 22:20

Let $\ \alpha\in [0,9].$

Proof outline

  1. There exists a sequence of integers $\ k_1,\ k_2,\ldots\ $ such that $\ \displaystyle\lim_{n\to\infty}\left( \frac{\sum_{j=1}^{n} k_j}{n} \right) = \alpha.\quad$
  2. Create a new sequence by changing every member of the above sequence of the form $\ \large{k_{2^j}}\ $ i.e. changing $\ k_1\to \ {k_1}',\quad k_2\to\ {k_2}',\quad k_4\to\ {k_4}',\quad k_8\to\ {k_8}',\quad k_{16}\to\ {k_{16}}',\ $ etc, and in our new sequence we keep other members the same as before: $\ {k_3}' = k_3,\ {k_5}' = k_5,\ {k_6}' = k_6,\ $ etc. Then the limit as in $(1)$ but for our new sequence, is also equal to $\ \alpha,\ $ i.e. we have: $\ \displaystyle\lim_{n\to\infty}\left( \frac{\sum_{j=1}^{n} {k_j}'}{n} \right) = \alpha.$
  3. This gives us a countably infinite collection $\ (\ k_1,\ k_2,\ k_4,\ k_8,\ k_{16},\ \ldots\ )$ of members of the above sequence- and we can change each of these terms to what we want without affecting the sum of the series. Now for each $\ j\in\mathbb{N},\ $ map $\ \large{k_{(2^j)}}\to 0\ $ and $\ \large{k_{(2^j)'}}\to 1.\ $ This now resembles Cantor's Diagonalisation argument with sequences containing only $\ 0's\ $ and $\ 1's\ $ as entries, which is famously uncountable, and so the set of all real number sequences satisfying $\ \displaystyle\lim_{n\to\infty}\left( \frac{\sum_{j=1}^{n} k_j}{n} \right) = \alpha\quad$ is uncountable.

Funnily enough, I have found Step 2 easy to prove, but couldn't come up with an easy proof for Step 1.

Proof of Step 2:

Limit of altered ("new") sequence

\begin{align} =\displaystyle\lim_{n\to\infty}\left(\frac{\displaystyle\sum_{j=1}^{n} {k_j}'}{n}\right)\\ \\ =\displaystyle\lim_{n\to\infty}\left(\frac{\displaystyle\sum_{j=1}^{n} k_j + \displaystyle\sum_{j=0}^{\lfloor \log_2(n) \rfloor} ({k_{2^j}}'-k_{2^j}) }{n}\right)\\ \\ =\displaystyle\lim_{n\to\infty}\left(\frac{\displaystyle\sum_{j=1}^{n} k_j}{n}\right) + \displaystyle\lim_{n\to\infty}\left(\frac{\displaystyle\sum_{j=0}^{\lfloor \log_2(n) \rfloor} ({k_{2^j}}'-k_{2^j}) }{n}\right)\\ \\ =\alpha + \displaystyle\lim_{n\to\infty}\left(\frac{\displaystyle\sum_{j=0}^{\lfloor \log_2(n) \rfloor} ({k_{2^j}}'-k_{2^j}) }{n}\right),\\ \\ \text{and this final limit term equals zero, because it's absolute value is}\\ \\ \leq\ \displaystyle\lim_{n\to\infty}\left(\frac{\displaystyle\sum_{j=0}^{\lfloor \log_2(n) \rfloor} \vert{k_{2^j}}'-k_{2^j}\vert }{n}\right)\ \leq\ \displaystyle\lim_{n\to\infty}\left(\frac{\displaystyle\sum_{j=0}^{\lfloor \log_2(n) \rfloor} 9 }{n}\right)\\ \\ \leq\ \displaystyle\lim_{n\to\infty}\left(\frac{ 9\log_2(n) +1 }{n}\right) = 0.\\ \end{align}


If you are willing to allow a little heavy machinery, one can show that the set is uncountable for every $\alpha$, even just restricting to the set of numbers of the form $0.x_1 x_2 x_3 \dots$. In fact the argument below will give more precise information than just uncountability.

Setup. Rather than work with the averages of the digits $\frac{1}{n} \sum_{j=1}^{k} x_j$ directly, we will instead work with the frequencies of occurrences of specific digits, and make the connection at the end. If $x = 0.x_1 x_2 \dots$ and $r \in \{0,1,2,\dots, 9\}$, let us define $$ D_x(r) = \lim_{n \to \infty} \frac{1}{n} \#\{1 \leq j \leq n : x_j = r\} $$ whenever the limit exists.

Black box theorem. Let $p = (p_0, p_1, \dots, p_9)$ be a probability vector over the set $\{0,1,2,\dots, 9\}$ (that is, all $p_i \geq 0$ and $\sum p_i = 1$). Then the Hausdorff dimension of the set $$ \{x \in [0,1] : D_x(r) \text{ exists and is equal to } p_r \text{ for each } r \in \{0,1,2,\dots,9\} \} $$ is given by $\frac{H(p)}{\log 10}$, where $H(p) = \sum_{i=1}^{10} -p_i \log p_i$ is the Shannon entropy of the vector $p$. The relevant fact about $H$ that we'll need later is that $H(p) > 0$ whenever at least two of the $p_i$ are $>0$.

Essentially this theorem specifies the "size" (in the sense of Hausdorff dimension) of the set of numbers that have specified frequencies of digits in their base 10 expansions. It was proved originally by Patrick Billingsley, I think. I can't find an exact reference right now but I'd be happy to look a little more if you are curious. The proof uses a little ergodic theory and a little geometric measure theory (hence the aforementioned "heavy machinery").

Connection. Fix $\alpha \in [0,9]$. There are two cases, depending on if $\alpha \in \mathbb{Z}$ or not. If $\alpha \in \mathbb{Z}$, let $x = 0.x_1 x_2 \dots$ be any number satisfying $D_x(\alpha - 1) = D_x(\alpha + 1) = 1/2$. Then $$ \lim_{n \to \infty} \frac{1}{n} \sum_{j=1}^{n} x_j = \lim_{n \to \infty} \sum_{r=0}^9 r \cdot \frac{1}{n} \#\{1 \leq j \leq n : x_j = r \} = \sum_{r=0}^9 r \cdot D_x(r) = (\alpha - 1) \cdot \frac12 + (\alpha + 1) \cdot \frac12 = \alpha. $$ By Billingsley's theorem, the set of $x$ satisfying this has strictly positive Hausdorff dimension, which implies that it is uncountable.

Finally, consider the case where $\alpha$ is not an integer. Then write $\alpha = A + t$ where $A \in \mathbb{Z}$ and $t \in (0,1)$. Then we let $x = 0.x_1x_2 \dots$ be any number satisfying $D_x(A) = 1-t$, $D_x(A+1) = t$. A similar calculation as above will then show that any such $x$ satisfies $\frac{1}{n} \sum_{j=1}^{n} x_j = A+t = \alpha$, and again applying Billingsley's theorem shows that the set of such $x$ has positive Hausdorff dimension and is therefore uncountable.


Given $\alpha\in[0,9]$, for $n\in\Bbb N$ let $$x_n=\lfloor n\alpha\rfloor-\lfloor (n-1)\alpha\rfloor.$$ Note that $x_n$ is a non-negative integer and $\le 9$, so can be used as a decimal digit. Let $A\subseteq \Bbb N$ be an arbitrary set (so there are continuum-many choices for $A$). Then consider the number $ X_{\alpha,A}=0.d_1d_2d_3\ldots$ that has (no integer part and) as $n$th decimal digit $$d_n=\begin{cases}1&n=2^k,k\in A\\0&n=2^k,k\notin A\\x_{n-k}&2^k<n<2^{k+1}\end{cases} $$ Then one verifies quickly that the average digit is $\alpha$.


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.