Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
61.37%, perhaps? –  Charles Apr 12 '11 at 14:49
    
Good catch, fixed! –  Adrian Petrescu Apr 12 '11 at 16:02

3 Answers 3

up vote 9 down vote accepted

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. $$

share|improve this answer
    
I wouldn't exactly call it easy, but I definitely enjoyed working through your proof, thanks :) –  Adrian Petrescu Apr 10 '11 at 19:10

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$.

share|improve this answer

The Prime Numbers and Their Distribution By Gérald Tenenbaum, Michel Mendès France

Parts of this book, including discussion of the result, are available on Google Books.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.