1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)... $\endgroup$ – xskxzr Nov 5 '18 at 3:53
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.