# Is it possible to split a single sample from a discrete uniform distribution into two samples from two smaller distributions?

Suppose I have a single integer sample $k$ from a discrete uniform distribution such that $0 \le k \lt 2^{32}$. Is it always possible to interpret this sample as a pair of samples $m, n$ from two other discrete uniform distributions such that $0 \le m \lt r$ (for any integer $r$ less than, say, $2^{30}$) and $0 \le n \lt 2^p$ (where $p$ is any integer at all, but ideally as large as possible)?

I know that this is trivial when $r = 2^x$; you can take $p = 32 - x, m = k \bmod r, n = \lfloor k / r \rfloor$. But I don't know how to do it in general and still preserve uniformity.

-
My guess is that it should only be possible when $r*2^p | 2^{32}$ --- at least, assuming you don't want to place any other conditions on $k$ (for example, you might resample from $[0, 2^{32}-1]$ whenever $k > z * r * 2^p$, where $z = \lfloor 2^{32}/(r*2^p) \rfloor$. – duncanm Jan 5 '12 at 23:44
Take for example $r=2^{30}-1$, or much more modestly, $r=3$. If we want to simulate a uniform on $\{0,1,2\}$ using a uniform on a set of size $2^{32}$, there will have to be instances when we throw the sampled number away and repeat. For $3$, it can be arranged that this hardly ever happens, since the number of integers between $1$ and $2^{32}-1$ (inclusive) is divisible by $3$, so we need a new sample only if in our sampling we get the number $0$. – André Nicolas Jan 5 '12 at 23:51

Let $\Omega$ be a sample space of cardinality $2^n$, and suppose that all the elements $\alpha\in \Omega$ are equally likely. Then any event $E \subseteq \Omega$ has probability of the shape $\frac{m}{2^n}$ for some integer $m$. Thus $P(E)$ is a dyadic rational. If $p$ is not a dyadic rational, we cannot find an event $E\subseteq \Omega$ such that $P(E)=p$.
In particular, if the positive integer $r$ is not a power of $2$, we cannot find an $E\subseteq \Omega$ that has probability (exactly) equal to $\frac{1}{r}$, and interpreting as a pair of samples in the desired way is not possible.
Sampling from $\Omega$ a bounded number of times will produce the same result. If we do not put a priori bounds on the number of times that we sample, then any probability $p$ can be simulated.