Generate a Bernoulli random variable X with P[X=1]=p and P[X=0]=1-p by flipping a fair coin

Without losing generality, assume p=0.a_1a_2a_3\ldots a_n, a_i\in \{0, 1\}. If we have a uniform random variable Y with a probability density function of f_Y(y)=1, 0\leq y<1. We can generate X as follows:

X=\begin{cases} 1 & Y<p \\
0 & Y>p \end{cases}

We can generate Y by flipping a fair coin repeatedly. Let Y=0.B_1B_2B_3\ldots, B_i\in \{0, 1\},

B_i=\begin{cases} 0 & i\textrm{th flip is “head”} \\
1 & i\textrm{th flip is “tail”} \end{cases}

In order to decide whether Y is greater or less than p, we need to generate the binary expansion of Y bit by bit and compare them with the corresponding bits of p. Once we find the smallest k such that a_k\neq B_k, we will stop flipping the coin. Then, X can be generated as follows:

X=\begin{cases} 1 & \textrm{if }a_i=B_i,i=1,2,\ldots k-1\textrm{ and }B_k<a_k,k\leq n \\
0 & \textrm{if }a_i=B_i,i=1,2,\ldots k-1\textrm{ and }B_k>a_k,k\leq n\\
0 & \textrm{if }a_i=B_i,i=1,2,\ldots n \end{cases}

Note that when the comparison reaches the end of binary expansion of p, i.e., the first n bits of p are the same as the first n bits of Y, we know that Y will be greater than p eventually since it has an infinite expansion. Therefore, we can set X as 0 and stop flipping the coin.

Based on the algorithm above, the probability of the number of flips required is the following:

P\left[\textrm{# of flips}=k\right]=\begin{cases} \left(\frac{1}{2}\right)^k & k<n \\
\left(\frac{1}{2}\right)^n & k=n \end{cases}

We have the expected number of flips:

E\left[\textrm{# of flips}\right]=\sum_{k=1}^{n-1}k\cdot\left(\frac{1}{2}\right)^{k}+n\cdot\left(\frac{1}{2}\right)^{n}=2-\left(\frac{1}{2}\right)^{n-1}

For p=0.5, the length of its binary expansion n=1, and thus the expected number of flips is 1. For p=0.625, i.e., n=3, the expected number of flips is 1.75. When n\rightarrow\infty, e.g., p=5/7, the expected number of flips will be 2.