4

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!

Max
  • 1,408
  • You might be interested in this paper: Szalkai and Velleman, Versatile Coins, Amer. Math. Monthly vol. 100 (1993), pp. 26-33. – Dan Velleman Sep 04 '22 at 21:55

1 Answers1

4

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.

His optimality bound comes from the wonderful results of Knuth and Yao about the optimal generation of general discrete random variables from coin tosses (which they call DDG trees). I put the reference below, you can find it on libgen, it is a real gem and a great read. Lumbroso's paper also describes a neat optimal way do generate discrete uniform variables.

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.

Knuth, Donald E.; Yao, Andrew C., The complexity of nonuniform random number generation, Algorithms and Complexity, Proc. Symp., Pittsburgh 1976, 357-428 (1976). ZBL0395.65004.

justt
  • 4,458