# Simulate a biased coin with a fair coin using a fixed number of tosses

For which values of $$p$$ can you simulate a $$p$$-biased coin using a fair coin in a fixed number of tosses (the "reverse" direction of this problem)?

I have read of an approach where you consider the binary expansion of $$p$$, let's call it $$0.b_1b_2b_3\dots$$. Then, we toss the fair coin until it lands on heads. Let's say this took $$n$$ tosses. If $$b_n=1$$, then we map this to a heads for our $$p$$-biased coin, otherwise if $$b_n=0$$ we map this to a tails. This works because the probability of mapping to heads in our $$p$$-biased coin is simply $$\sum_{i|b_i=1}\frac{1}{2^i}=0.b_1b_2b_3\dots=p$$

But this still gives an expected run time of $$2$$ flips. Is there an approach which takes a constant worst case number of flips? Or is the binary representation of $$p$$ in base 2 terminating a necessary condition for this to be the case? Any ideas are appreciated!

• You might be interested in this paper: Szalkai and Velleman, Versatile Coins, Amer. Math. Monthly vol. 100 (1993), pp. 26-33. Commented Sep 4, 2022 at 21:55

By constant you mean nonrandom ? If there is a deterministic bound $$n$$ on the number of flips you need, then your coin is a random variable $$X$$ defined on $$\{0,1\}^n$$ and necessarily $$p = P(X=1) = 2^{-n} \mathrm{Card}\{\omega \in \{0,1\}^n, X(\omega) = 1\}$$ is a multiple of $$2^{-n}$$ so the binary representation terminates.
Regarding your randomized algorithm, when $$p$$ is non-dyadic it is optimal in expectation as explained by Lumbroso in appendix B of this paper https://arxiv.org/pdf/1304.1916.pdf (Lumbroso makes a small mistake : his computation does not work when $$p$$ is dyadic in which case you can stop the procedure after $$2^{-n}$$ steps for a small gain.
If you want many independent samples of your biased coin, you can get a performance boost up to $$H(p) = p \log(1/p) + (1-p)\log(1/(1-p))$$ expected bits per sample by reusing randomness from one sample to the next. https://arxiv.org/pdf/1502.02539.pdf $$H(p)$$ is the Shannon entropy of the distribution and is a hard lower bound. Lumbroso also does this in his paper for the discrete uniform case.