# 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

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

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9441967010498047, "perplexity_flag": "head"}