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
Uniformly distributed rationals
-
1If you sort the rationals by their denominator in lowest terms, then that really, really ought to work. Proving it seems to be not completely trivial, though. – 2011-11-23
-
0Seems like a tough problem. Do you know of any functions $f$ that satisfy the limit? – 2011-11-23
-
0You want the sequence $f(n)$ to be uniformly distributed in $(0,1)$ ... so what happens if you look in the literature on uniform distribution? – 2011-11-23
-
2In particular, does THIS help in constructing such a thing? http://en.wikipedia.org/wiki/Van_der_Corput_sequence – 2011-11-23
3 Answers
(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 $$ \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.)
-
0There is no such thing as a uniform distribution on a countably infinite set. The rationals are a countably infinite set, so there is no uniform distribution on the rationals. It's enough to note, as you have done, that each individual rational would have to be assigned probability zero. I don't see what bringing $Y$ into the discussion does for us. But in any event, none of this has any bearing on the original question. Uniformly distributed sequences are only loosely related to uniform random variables. – 2012-03-30
-
0By a similar argument, one could argue that uniform random variables over the reals are impossible, because the probability of any given real must be zero. But we know that that logic must be flawed, because we are happy with uniform random reals. So what's the difference between the reals and the rationals? I'm not sure, but my thinking was that the difference was that it is easy to write down a distribution over the rationals where every rational is assigned a nonzero probability. Why exactly is a countable sum of zeros still zero, while an uncountable sum (the reals) is able to add up to 1? – 2012-03-31
-
0... I see that I have missed the point of the original question - thanks for the feedback. I'm just trying to identify proofs about the rationals, and the difference between them and the reals in this context. Is it true that the sum of uncountably-many zeros can add to 1, for any uncountable set? What about the continuum hypothesis - does it have any relevance? How big does an uncountable set have to be before we can have a uniform distribution over it? Is that even a question worth asking? – 2012-03-31
-
0sorry, I said "uniform distribution" when I should have said "uniformly distributed random variable". I'm not accustomed to using the word "distribution" for anything other than a random variable. – 2012-03-31
-
0There is no such thing as an uncountable sum. Think about how sums over countably infinite sets are defined, and you'll see it doesn't work for uncountable sets. I don't know whether being uncountable guarantees the existence of a uniform random variable, irrespective of the continuum hypothesis. I don't know offhand whether there is a uniform random variable over the Cantor set. Well, I suppose there is - there's an order-preserving map from Cantor to interval, just define it through that map. Maybe this is worth posting as a question. – 2012-04-01
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.
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.
-
0Can you please provide details for this proof or a reference? Thanks. – 2017-12-23
-
0@ray, the von Neumann reference is von Neumann, J.: Gleichmässig dichte Zahlenfolgen. Mat. Fiz. Lapok 32, 32–40 (1925). – 2017-12-23