Lower bound on the worst-case unbiased coin flips to sample a distribution?

Question

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.

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