Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p

Question

So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...

Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$

So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ [0,1] and returns $0$ if $f < 0.5$, $1$ if $f \geq 0.5$.

I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $\frac{1}{4}$... and I can expand that solution to any $p$ where $p = \frac{1}{2^x}$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...

I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?

Answer 1

Suppose $p=\sum\limits_{n=1}^\infty \frac{1}{2^n}p_n$, where $p_n\in\{0,1\}$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i \neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^{-(k-1)}\frac{p_k}{2}$, thus the probability of generating heads is $\sum\limits_{k=1}^{\infty}2^{-k}p_k =p$. The expected number of iterations is $2$.

Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.