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.

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.

share|improve this question
    
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
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$. –  André Nicolas Jan 5 '12 at 23:51

1 Answer 1

up vote 2 down vote accepted

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.

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.