2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Mark Jun 7 at 4:15
  • 1
    $\begingroup$ 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." $\endgroup$ – Clement C. Jun 7 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.