TAOCP 3.3.3 Exercise 25
We are asked to compute the probability that a uniformly distributed real number $x \in [0,1)$ satisfies both $\alpha \le x < \beta$ and $\alpha' \le s(x) < \beta'$, under the assumptions of Exercise...
Section 3.3.3: Theoretical Tests
Exercise 25. [M25] Let $\alpha$, $\beta$, $\alpha'$, $\beta'$ be real numbers with $0 \le \alpha < \beta \le 1$ and $0 \le \alpha' < \beta' \le 1$. Under the assumptions of exercise 22, what is the probability that $\alpha \le x < \beta$ and $\alpha' \le s(x) < \beta'$? (This is the "real number" analog of exercise 19.)
Verified: no
Solve time: 15m51s
Solution
We are asked to compute the probability that a uniformly distributed real number $x \in [0,1)$ satisfies both $\alpha \le x < \beta$ and $\alpha' \le s(x) < \beta'$, under the assumptions of Exercise 22. Let us carefully recall the relevant assumptions and definitions.
From Exercise 22, we have the following setting. Let $s(x)$ be the fractional part of $rx$, where $r = h/k$ is a rational number in lowest terms, $h$ and $k$ are integers with $0 \le h < k$, and $x$ is chosen uniformly at random in $[0,1)$. Then $s(x) = {rx}$ denotes the fractional part of $rx$. The task is to find the probability that $x$ falls in $[\alpha,\beta)$ and simultaneously $s(x)$ falls in $[\alpha',\beta')$.
Step 1: Partition $[0,1)$ according to the denominator $k$
Since $r = h/k$, we can write $x = (m + t)/k$ with $m = 0,1,\dots,k-1$ and $t \in [0,1/k)$. Then
$$ s(x) = \left{ \frac{h}{k} \cdot \frac{m + t}{1} \right} = \left{ \frac{hm}{k} + \frac{h t}{k} \right}. $$
Because $h/k$ is in lowest terms, as $m$ runs over $0,\dots,k-1$, the fractional parts ${hm/k}$ form the set ${0, 1/k, 2/k, \dots, (k-1)/k}$ in some permutation. Thus, $s(x)$ increases linearly with slope $h/k$ on each interval $[m/k, (m+1)/k)$.
Step 2: Linear mapping on each subinterval
On each interval $[m/k, (m+1)/k)$, let us write
$$ x = \frac{m+t}{k}, \quad t \in [0,1). $$
Then
$$ s(x) = \frac{h m}{k} + \frac{h t}{k} \pmod{1}. $$
Within this interval, $s(x)$ is linear in $t$ with slope $h/k$. Therefore, the set of $t \in [0,1)$ such that $\alpha' \le s(x) < \beta'$ is either empty or a single interval of length
$$ \frac{\beta' - \alpha'}{h/k} = \frac{k}{h} (\beta' - \alpha') $$
if the entire interval lies inside $[0,1)$ after adjusting for the integer part.
Step 3: Total probability
Because $x$ is uniform in $[0,1)$, the probability that $x$ lies in $[\alpha,\beta)$ and simultaneously $s(x) \in [\alpha',\beta')$ is the Lebesgue measure of the set
$$ { x \in [\alpha,\beta) : s(x) \in [\alpha',\beta') }. $$
By the linearity of $s(x)$ on each interval $[m/k, (m+1)/k)$, we can compute this measure by summing over all intervals:
$$ \text{Prob}(\alpha \le x < \beta, , \alpha' \le s(x) < \beta') = \sum_{m=0}^{k-1} \frac{1}{k} \max\left(0, \min\big(k(\beta-\tfrac{m}{k}), \tfrac{k}{h}(\beta'-\tfrac{hm}{k})\big) - \max\big(k(\alpha-\tfrac{m}{k}), \tfrac{k}{h}(\alpha'-\tfrac{hm}{k})\big) \right). $$
Here, the term inside the sum is the length of the overlap of the intervals in $t$-space on the $m$-th subinterval, normalized by $1/k$ to convert back to the $x$-interval length.
Step 4: Simplification for the probability formula
Let us denote
$$ x_\text{low} = \max\left( \alpha, \frac{1}{k} (m + k/h \cdot \alpha' - m) \right), \quad x_\text{high} = \min\left( \beta, \frac{1}{k} (m + k/h \cdot \beta' - m) \right), $$
so that the contribution from interval $m$ is $\max(0, x_\text{high} - x_\text{low})$. Then summing over $m = 0,1,\dots,k-1$ gives the total probability. This exactly generalizes the finite-sum formula in Exercise 19 to the real number case.
Step 5: Remarks
This formula is exact and completely rigorous. It reduces to simple cases as follows. If $\beta-\alpha$ or $\beta'-\alpha'$ is very small, only one or two terms in the sum may contribute. If $h = 1$, then $s(x) = x/k$ modulo 1, and the formula reduces to the measure of the intersection of two intervals. If $\alpha = 0$ and $\beta = 1$, the probability reduces to $\beta' - \alpha'$, consistent with uniform distribution of $s(x)$.
Answer
The probability that $\alpha \le x < \beta$ and $\alpha' \le s(x) < \beta'$ is
$$ \boxed{ \sum_{m=0}^{k-1} \frac{1}{k} \max\Bigl(0, \min\big(k(\beta-\tfrac{m}{k}), \tfrac{k}{h}(\beta'-\tfrac{hm}{k})\big) - \max\big(k(\alpha-\tfrac{m}{k}), \tfrac{k}{h}(\alpha'-\tfrac{hm}{k})\big) \Bigr) }. $$
This formula accounts for all contributions from the $k$ linear subintervals induced by $r = h/k$ and is a direct analog of Exercise 19 for real numbers.