0
$\begingroup$

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.

  • 1
    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$.2012-01-05

1 Answers 1

2

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.