Lower bound of generating a biased coin? If we have an unbiased coin and we want to generate a biased coin with probability $p$ of getting a head and $1-p$ of getting a tail. What is the lower bound of the expected number of flips that generating this biased coin?
 A: This answer concerns the maximal (rather than expected) number of tosses; which is not what is asked for.

After flipping a fair coin $n$ times, you have $2^n$ equally likely outcomes. Every event defined in terms of these outcomes has probability   $k/2^n$ for some $k\in\{0,\dots,2^n\}$. And conversely, for every $k$ there is such an event. Conclusion: 

Required number of flips is $ \inf\{n: 2^np\in\mathbb Z\}$. 

Which is infinite when $p$ is not a dyadic rational; meaning that for such $p$ you can't simulate the  biased coin at all.
Example: if $p=0.375$, you need $3$ flips.
A: If you expand $p$ in binary, then take head of your flips as a $1$, tail as a $0$, you can state head or tail as soon as you disagree with $p$.  There is no lower bound, as the sequence of flips could match the expansion of $p$ as long as you want.  Say $p=\frac 13=0.01010101\overline{01}_2$.  As long as you alternate tails and heads you can't tell.  With probability $1$ that will stop sometime.  The expected number of flips is $\sum_{i=1}^{\infty} \frac i{2^i}=2$
