<p>Fix such a distribution, and an element <span class="math-container">$k$</span> showing its non-triviality. In particular, <span class="math-container">$\Pr[X=k]= (2m+1)/2^p$</span> for some integer <span class="math-container">$m$</span>.</p>

<p>Suppose by contradiction you have an algorithm A to sample from the distribution given <span class="math-container">$p-1$</span> i.i.d. unbiased bits. Such an algorithm is, given the realization of the coins, deterministic: i.e., it is equivalent to a partition of the leaves of the complete binary tree of height <span class="math-container">$p-1$</span>, each output <span class="math-container">$x$</span> corresponding to a different set <span class="math-container">$S_x$</span> in the partition.</p>

<p>As such, since all leaves have probability <span class="math-container">$1/2^{p-1}$</span>, any output <span class="math-container">$x$</span> has probability <span class="math-container">$|S_x|/2^{p-1}$</span>, i.e., of the form <span class="math-container">$2\ell/2^p$</span> for some integer <span class="math-container">$\ell$</span>. That cannot be equal to <span class="math-container">$(2m+1)/2^p$</span>.</p>

CC BY-SA 4.0
2019-06-07T04:15:52.907Z
I have a similar proof, my issue is that I completely expect this to be in the literature somewhere already, and I'd like to cite it properly (and potentially see if anyone has generalizations, as even for distributions not specified via fixed point numbers there seems to be some connection by how well the probabilities can be approximated by dyadic rationals and the entropy usage, at least for "approximately sampling", meaning sampling from a distribution within $1/2^p$ from the true one in SD).
Mark Schultz-Wu
CC BY-SA 4.0
2019-06-07T04:23:14.217Z
My bad, I had missing the (crucial) *"I'm solely looking for a reference for who to cite"*... I don't know of a reference for it, but it may just be either folklore, or "not explicitly known/stated as such but an easy fact."
Clement C.
CC BY-SA 4.0
2019-06-07T00:17:57.460Z
2019-06-07T00:17:57.460Z
Clement C.
<p>Say that we have a distribution <span class="math-container">$\mathcal{D}$</span> such that all probabitilities associated with it are <span class="math-container">$p$</span>-bit fixed precision numbers, so:
<span class="math-container">$$
\Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i},\quad k_i\in\{0,1\}
$$</span>
Say that this is a <em>non-trivial</em> <span class="math-container">$p$</span>-bit distribution if at least one element <span class="math-container">$k$</span> truly takes all <span class="math-container">$p$</span> bits to represent, meaning <span class="math-container">$\exists k\in\mathsf{supp}(\mathcal{D})$</span> such that <span class="math-container">$k_p = 1$</span></p>

<p>I'm interested in the number of <span class="math-container">$\mathsf{Bern}(1/2)$</span> random variables required to sample a single sample from this in the worst-case.
From some discussions with others we think it's obvious that it's <span class="math-container">$p$</span>, and that there should be a lower bound. It seems like a rather basic observation though, so I was wondering if I could find it in the literature anywhere so I could cite it.</p>

<p>Edit: To make the question slightly more specific, I have a ~1/2 page information theoretic argument showing this is true (it's really quite trivial), so I'm solely looking for a reference for who to cite regarding this lower bound.</p>

<reference-request><randomness>
Lower bound on the worst-case unbiased coin flips to sample a distribution?
Mark Schultz-Wu
# Lower bound on the worst-case unbiased coin flips to sample a distribution?

(Asked by: username_0 on 2019-06-06)

Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:
$$
\Pr\_{X\sim \mathcal{D}}[X = k] =\sum\_{i = 1}^p \frac{k\_i}{2^i},\quad k\_i\in\{0,1\}
$$
Say that this is a *non-trivial* $p$-bit distribution if at least one element $k$ truly takes all $p$ bits to represent, meaning $\exists k\in\mathsf{supp}(\mathcal{D})$ such that $k\_p = 1$

I'm interested in the number of $\mathsf{Bern}(1/2)$ random variables required to sample a single sample from this in the worst-case.
From some discussions with others we think it's obvious that it's $p$, and that there should be a lower bound. It seems like a rather basic observation though, so I was wondering if I could find it in the literature anywhere so I could cite it.

Edit: To make the question slightly more specific, I have a ~1/2 page information theoretic argument showing this is true (it's really quite trivial), so I'm solely looking for a reference for who to cite regarding this lower bound.

**Tags:** reference-request, randomness

---

## 1 answers

### Answer by username_1 on 2019-06-07. Score: 1

Fix such a distribution, and an element $k$ showing its non-triviality. In particular, $\Pr[X=k]= (2m+1)/2^p$ for some integer $m$.

Suppose by contradiction you have an algorithm A to sample from the distribution given $p-1$ i.i.d. unbiased bits. Such an algorithm is, given the realization of the coins, deterministic: i.e., it is equivalent to a partition of the leaves of the complete binary tree of height $p-1$, each output $x$ corresponding to a different set $S\_x$ in the partition.

As such, since all leaves have probability $1/2^{p-1}$, any output $x$ has probability $|S\_x|/2^{p-1}$, i.e., of the form $2\ell/2^p$ for some integer $\ell$. That cannot be equal to $(2m+1)/2^p$.

> **Comments:**
> **username_0**: I have a similar proof, my issue is that I completely expect this to be in the literature somewhere already, and I'd like to cite it properly (and potentially see if anyone has generalizations, as even for distributions not specified via fixed point numbers there seems to be some connection by how well the probabilities can be approximated by dyadic rationals and the entropy usage, at least for "approximately sampling", meaning sampling from a distribution within $1/2^p$ from the true one in SD).  
> **username_1**: My bad, I had missing the (crucial) *"I'm solely looking for a reference for who to cite"*... I don't know of a reference for it, but it may just be either folklore, or "not explicitly known/stated as such but an easy fact."  

---

