Probability distribution for the remainder of a fixed integer

In the "Notes" section of Modern Computer Algebra by Joachim Von Zur Gathen, there is a quick throwaway remark that says:

Dirichlet also proves the fact, surprising at first sight, that for fixed $a$ in a division the remainder $r = a \operatorname{rem} b$, with $0 \leq r < b$, is more likely to be smaller than $b/2$ than larger: If $p_a$ denotes the probability for the former, where $1 \leq b \leq a$ is chosen uniformly at random, then $p_a$ is asymptotically $2 - \ln{4} \approx 61.37\%$.

The note ends there and nothing is said about it again. This fact does surprise me, and I've tried to look it up, but all my searches for "Dirichlet" and "probability" together end up being dominated by talks of Dirichlet stochastic processes (which, I assume, is unrelated).

Does anybody have a reference or proof for this result?

Solution 1:

It's not hard to prove. Let $$f(x) = \begin{cases} 0 & x \geq 0 \\ 1 & x < 0 \end{cases}.$$ Then $$f \left( 1 - \frac{k}{n} \left[ \frac{n}{k} \right] - \frac{k}{2n} \right) = 1$$ if and only if $n \ \mathrm{mod} \ k$ is smaller than $k/2$, so that we have $$p_n = \frac{1}{n} \sum_{k=1}^{n} f \left( 1 - \frac{k}{n} \left[ \frac{n}{k} \right] - \frac{k}{2n} \right).$$ Now take $n \to \infty$. Then this becomes $$\lim_{n\to\infty} p_n = \int_{0}^{1} f\left( 1 - \left( \left[ \frac{1}{x} \right] + \frac{1}{2} \right) x\right) \, dx.$$ To evaluate this integral, we divide the domain of integration according to the value of $[1/x]$. Then $$ \int_{0}^{1} f\left( 1 - \left( \left[ \frac{1}{x} \right] + \frac{1}{2} \right) x\right) \, dx = \sum_{n=1}^{\infty} \int_{1/(n+1)}^{1/n} f\left( 1 - \left( n + \frac{1}{2} \right) x\right) \, dx, $$ and since $1 - (n+(1/2))x < 0$ for $2/(2n+1) < x < 1/n$, it is equal to $$\sum_{n=1}^{\infty} \left( \frac{1}{n} - \frac{2}{2n+1} \right) = 2 - \log 4. $$

Solution 2:

sos440's answer is correct, but I think it makes the calculation look unnecessarily complicated. The boundaries where the remainder switches between being greater or less than $b/2$ are $a/b=n/2$, that is $b=2a/n$, for $n>2$. If we choose $b$ as a real number uniformly distributed over $[0,a]$, we can calculate the probability of $a \;\text{mod}\; b$ (defined as the unique number between $0$ and $a$ that differs from $a$ by an integer multiple of $b$) being less than $b/2$ by adding up the lengths of the corresponding intervals,

$$ \begin{eqnarray} &&\left(\left(\frac{2a}{2}-\frac{2a}{3}\right)+\left(\frac{2a}{4}-\frac{2a}{5}\right)+\left(\frac{2a}{6}-\frac{2a}{7}\right)+\ldots\right)\\ &=&2a\left(1-(1-\frac{1}{2}+\frac{1}{3}-\ldots)\right)\\ &=&2a(1-\ln2)\;, \end{eqnarray} $$

which is the integral from $0$ to $a$ of the characteristic function $\chi_S$ with $S=\{b\mid a\;\mathrm{mod}\;b < b/2\}$ and yields the probability $p_a=2a(1-\ln2)/a=2(1-\ln2)$. By scaling from $[0,a]$ to $[0,1]$, we can interpret the probability for integer $b$ as an approximation to this integral using the rectangle rule, which converges to the integral as $a\to\infty$ since the mesh size of the approximation is $1/a\to0$.