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

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?

• If $p$ is a rational number, your question is covered by this question. If $p$ is an irrational number, I don't think it is possible (in finite many steps)... – xskxzr Nov 5 '18 at 3:53

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