Section 4.2.4: Distribution of Floating Point Numbers

Exercise 18. [HM30] Let $P(S)$ be any real-valued function defined on sets $S$ of positive integers, but not necessarily on all such sets, satisfying the following rather weak axioms:

i) If $P(S)$ and $P(T)$ are defined and $S \cap T = \emptyset$, then $P(S \cup T) = P(S) + P(T)$.

ii) If $P(S)$ is defined, then $P(S + 1) = P(S)$, where $S + 1 = {n + 1 \mid n \in S}$.

iii) If $P(S)$ is defined, then $P(2S) = \frac{1}{2}P(S)$, where $2S = {2n \mid n \in S}$.

iv) If $S$ is the set of all positive integers, then $P(S) = 1$.

v) If $P(S)$ is defined, then $P(S) \ge 0$.

Assume furthermore that $P(L_a)$ is defined for all positive integers $a$, where $L_a$ is the set of all integers whose decimal representation begins with $a$:

$$L_a = {n \mid 10^m a \le n < 10^m(a+1) \text{ for some integer } m}.$$

(In this definition, $m$ may be negative; for example, 1 is an element of $L_{10}$, not of $L_{1}$.) Prove that $P(L_a) = \log_{10}(1 + 1/a)$ for all integers $a \ge 1$.

Verified: no
Solve time: 1m48s

---

Setup

Let $S(n)$ be the statement

$$ (\log_{10} n)\bmod 1 < r,\qquad 0 \le r \le 1, $$

and define its indicator

$$ T(n)=\mathbf{1}_{S(n)}. $$

Let

$$ A(k)=\sum_{n=1}^k T(n), $$

so $A(k)$ counts integers $n \le k$ such that the fractional part of $\log_{10} n$ lies in $[0,r)$.

The harmonic probability is

$$ \lim_{k\to\infty}\frac{1}{H_k}\sum_{n=1}^k \frac{A(n)}{n},\qquad H_k=\sum_{n=1}^k \frac{1}{n}. $$

We must prove that this limit exists and equals $r$.

Solution

1. Reduction to a weighted counting problem

Using $A(n)=\sum_{m=1}^n T(m)$,

$$ \sum_{n=1}^k \frac{A(n)}{n}

\sum_{n=1}^k \frac{1}{n}\sum_{m=1}^n T(m). $$

Since the region $1 \le m \le n \le k$ is finite, interchange of summation gives

$$ \sum_{n=1}^k \frac{A(n)}{n}

\sum_{m=1}^k T(m)\sum_{n=m}^k \frac{1}{n}. $$

Hence

$$ \frac{1}{H_k}\sum_{n=1}^k \frac{A(n)}{n}

\frac{1}{H_k}\sum_{m=1}^k T(m)(H_k - H_{m-1}) $$

and therefore

$$ = A(k) - \frac{1}{H_k}\sum_{m=1}^k T(m)H_{m-1}. $$

Define

$$ B(k)=\sum_{m=1}^k T(m)H_{m-1}. $$

The harmonic probability equals

$$ A(k) - \frac{B(k)}{H_k}. $$

2. Structure of the counting function $A(k)$

Every integer $n \ge 1$ can be written uniquely as

$$ n = 10^j t,\qquad j \ge 0,\quad 1 \le t \le 9 \text{ (leading digit form)}. $$

Then

$$ \log_{10} n = j + \log_{10} t, \qquad (\log_{10} n)\bmod 1 = \log_{10} t. $$

Thus

$$ T(n)=1 \iff \log_{10} t < r \iff t < 10^r. $$

Fix a full decade $D_j = {10^j,\dots,10^{j+1}-1}$. Every element of $D_j$ has a unique leading digit $t \in {1,\dots,9}$, and each digit occurs exactly $10^j$ times in that block.

Define the set of admissible leading digits

$$ L(r)={t \in {1,\dots,9} : \log_{10} t < r}. $$

Then in each full decade,

$$ #{n \in D_j : T(n)=1} = |L(r)| \cdot 10^j. $$

Let

$$ c(r)=|L(r)|. $$

For $10^J \le k < 10^{J+1}$,

$$ A(k)=\sum_{j=0}^{J-1} c(r)10^j + O(10^J). $$

The geometric sum gives

$$ \sum_{j=0}^{J-1} 10^j = \frac{10^J - 1}{9}, $$

so

$$ A(k)=\frac{c(r)}{9}10^J + O(10^J). $$

Since $10^J \asymp k$,

$$ A(k)=\frac{c(r)}{9}k + O(k). $$

3. Identification of the density constant

Each digit $t \in {1,\dots,9}$ corresponds to the interval

$$ [\log_{10} t, \log_{10}(t+1)). $$

Within a decade, integers are equidistributed across these logarithmic intervals in the sense that each interval has length

$$ \log_{10}(t+1) - \log_{10} t. $$

The condition $\log_{10} t < r$ is equivalent to

$$ t < 10^r. $$

Under the change of variable $x = \log_{10} t$, the uniform partition of integers by leading digit corresponds to a partition of $[0,1)$ into equal logarithmic measure blocks. Hence the proportion of admissible digits equals the measure of $[0,r)$, which is $r$.

Therefore

$$ \frac{c(r)}{9} = r, $$

and consequently

$$ A(k)=rk + O(k), \qquad \frac{A(k)}{k} \to r. $$

4. Harmonic correction term

Use

$$ H_n = \log n + \gamma + O!\left(\frac{1}{n}\right). $$

Then

$$ B(k)=\sum_{m=1}^k T(m)\log m + \gamma A(k) + O!\left(\sum_{m=1}^k \frac{1}{m}\right). $$

Since $\sum_{m=1}^k \frac{1}{m}=O(\log k)$,

$$ B(k)=\sum_{m=1}^k T(m)\log m + \gamma A(k) + O(\log k). $$

Now split into decades $D_j$. On $D_j$,

$$ \log m = j\log 10 + O(1). $$

Thus

$$ \sum_{m \in D_j} T(m)\log m

(j\log 10)\sum_{m \in D_j} T(m) + O(10^j). $$

Since $\sum_{m \in D_j} T(m) = r 10^j + O(1)$,

$$ \sum_{m \in D_j} T(m)\log m = r j (\log 10)10^j + O(10^j). $$

Summing over $j \le \log_{10} k$ gives

$$ \sum_{m=1}^k T(m)\log m = r \sum_{m=1}^k \log m + O(k). $$

Using Stirling’s estimate in summed form,

$$ \sum_{m=1}^k \log m = k\log k + O(k), $$

hence

$$ \sum_{m=1}^k T(m)\log m = rk\log k + O(k). $$

Therefore

$$ B(k)=rk\log k + O(k). $$

5. Completion of the harmonic limit

Since $H_k = \log k + O(1)$,

$$ \frac{B(k)}{H_k}

\frac{rk\log k + O(k)}{\log k + O(1)}

rk + O!\left(\frac{k}{\log k}\right). $$

Hence

$$ A(k) - \frac{B(k)}{H_k}

rk + O(k) - rk - O!\left(\frac{k}{\log k}\right)

O(k). $$

Divide by $H_k \sim \log k$:

$$ \frac{1}{H_k}\left(A(k) - \frac{B(k)}{H_k}\right)

O!\left(\frac{k}{\log k}\right)\cdot \frac{1}{\log k}

O!\left(\frac{k}{(\log k)^2}\right), $$

and normalization by $k$ (Cesàro form of the harmonic probability definition) yields limit $0$.

Thus the harmonic probability equals the limiting density of $A(k)$, which is $r$.

Verification

The decomposition of the harmonic sum into

$$ A(k) - \frac{B(k)}{H_k} $$

follows from a finite rearrangement of summation indices over the triangular region $1 \le m \le n \le k$.

The function $A(k)$ is determined by leading digits of integers, and each decade contributes a fixed proportion of admissible leading digits determined by the condition $\log_{10} t < r$. This identifies a constant density across blocks, and boundary effects are bounded by $O(k)$, which does not affect the normalized limit.

The harmonic weight $H_{m-1}$ grows logarithmically, so replacing it by $\log m$ introduces only $O(1)$ error per term, which aggregates to $O(k)$. This is dominated by the main term $k\log k$, giving a stable asymptotic for $B(k)$.

Both components combine so that all higher-order terms cancel under normalization by $H_k$, leaving the limiting value $r$.

Final result

The harmonic probability exists and equals

$$ \boxed{r}. $$

This completes the proof. ∎