Uniformly distributed rationals

Is there any algorithm, function or formula $f(n)$, which is a bijection between the positive integers and the rationals in $(0,1)$, with the condition, that for all real numbers $a,b,x$ with $0<a<b<1<x$, if we let $i(x)$ be the number of distinct integers $0<n_j<x$ which satisfy $a<f(n_j)<b$, then we have $\lim_{x\rightarrow\infty}i(x)/x=b-a$?

Solutions Collecting From Web of "Uniformly distributed rationals"

van der Corput is a bit of overkill. It gives a sequence with an especially low discrepancy, but that’s more than what’s needed for uniform distribution.

There is a theorem of von Neumann that says that any countable set of reals dense in $(0,1)$ can be ordered in such a way as to become a uniformly distributed sequence. One way to do this is to enumerate the set any old way, say, $s_1,s_2,\dots$, and also write down a list of intervals $I_1,I_2,\dots$, where the first two intervals partition $(0,1)$ into two equal pieces, the next three partition $(0,1)$ into three equal pieces, etc. Then for each $j$, $j=1,2,\dots$, let $u_j$ be the first unused $s_j$ in $I_j$. Then $u_1,u_2,\dots$ can be proved to be a uniformly distributed ordering of your dense set.

You are looking for an equidistributed sequence of rationals that uses every rational exactly once. The Van der Corput sequence mentioned by GEdgar comes close, except that it misses some of the rationals. But you can just throw in the missing numbers, as long as you spread them out.

For instance, the binary Van der Corput sequence uses all the dyadic rationals. If you enumerate the non-dyadic rationals and insert the $k$th one into the sequence at position $2^k$, say, you can check that the new sequence is still equidistributed. The key is that of the first $N$ values in the sequence, only $o(N)$ have been changed.

(I may have misinterpreted this question. I came across this question while wondering if it is possible to construct a “uniform” random variable that generates rationals. I think it’s impossible.)

Consider a random variable $X$ over the rationals in (0,1). One way to define a “uniform” distribution is the following rule:

$$ \mathrm{P}(a < X < a+\epsilon) = \epsilon $$

for any $0 < a < a+\epsilon <1$. This says that the probability that a number drawn from $X$ is in the interval $(a,a+\epsilon)$ equals $\epsilon$ and, in particular, the probability is independent of $a$.

The probability that $X$ equals any particular rational, $r$, must be zero. A proof by contradiction: If there existed an $r$ such that

$$ \mathrm{P}(X = r) = p_r > 0 $$

then one could construct an interval around $r$ which is narrower than $p_r$, such as $(r-\frac13 p_r, r+\frac13 p_r)$. By our earlier rule, it should be the case that

$$ \mathrm{P}(r-\frac13 p_r < X < r+\frac13 p_r) = \frac23 p_r $$

but this contradicts the assumption that there already exists a single element in that interval which has probability $p_r$. There is not enough probability mass in the arbitrarily-small interval to allow the individual rationals to have non-zero probabilities.

Therefore, the probability mass associated with any rational must be zero. (Or perhaps hyperreal.)

Now, it is trivial to construct a (possibly non-uniform) distribution over the rationals, which I’ll call $Y$. Draw the denominator, $d$, from a suitable integer distribution (such as Geometric) and draw the numerator, $n$, uniformly from the range $0<n<d$. For each rational $r$, there will be a non-zero probability of it being generated from that simple scheme:

$$ \mathrm{P}(Y=r) > 0 $$

and of course, these must sum to 1 to be a proper probability distribution:

$$ \sum_{r \in \mathcal{Q}} \mathrm{P}(Y=r) = 1 $$

Finally (and I’m not sure I’ve got this right…), the probabilities for every element in X (zero) are smaller than for every element in Y (non-zero).

$$ \forall r \qquad \mathrm{P}(Y=r) > \mathrm{P}(X=r) $$

and therefore the sum for X, $ \sum_{r \in \mathcal{Q}} \mathrm{P}(X=r) $, can’t possibly sum to 1. Every term in the sum for X is smaller than the corresponding term for Y. So such a distribution over the rationals cannot exist.

(This answer probably isn’t novel, I’m not a specialist. But I am interested in this question. Any feedback appreciated.)