Let $B(p)$ be the Bernoulli distribution associated to the probability $p$. Let $(→)$ be the relation such that $(p→q)$ iff you can generate $B(q)$ from $B(p)$ with a bounded number of draws. (This implies that rejection sampling is not relevant here.)
Obviously $p→1-p$ since you just need to swap the output bit. In fact I think that the relation is characterized by:
$p→\sum_{i=0}^{n}a_ip^i(1-p)^{n-i}$
for any integer sequence $(a_i)_{i≤n}$ such that $a_i≤\binom{n}{i}$. This is done by sampling $n$ times and then choosing which words $w$ of $\{0,1\}^n$ will be mapped to $0$ and which will be mapped to $1$. The probability of $w$ is $P(w)=p^{|w|_1}(1-p)^{|w|_0}$. The bound on $a_i$ comes from the fact that for each $i$ there is exactly $\binom{n}{i}$ words $w$ with $i$ $1$'s and $(n-i)$ $0$'s.
My questions are:
(1) Is there an easier characterization of this relation?
(2) Is there a characterization of $D=\{p ∣ p→\frac12\}$?
For now it seems obvious that $\frac13∉D$ and more generally that it only contains only dyadic numbers. What is more surprising to me is that it seems that $\frac14∉D$.