## Question

Suppose we have a means of generating independent fair coin flips. We want to simulate a biased coin that comes up heads with probability p.

1. Give an algorithm to simulate such a coin. Assume that p is given in binary notation, this notation describing p may possibly be infinite if p is irrational.
2. Estimate the expected number of flips of a fair coin per a simulated flip of the biased one.

1. Assume that 0 is shown with probability 1-p and 1 is shown with probability p.

Algorithm.

Let binary representation of p is 0. p_1,p_2,p_3....

Repeat for i=1,2,3....

1. Flip a coin - obtain X_i.

2. If p_i=1 and X_i=0, stop and output 1.

3. If p_i=0 and X_i=1, stop and output 0.

2. Notice, that on each iteration algorithm stops if X_i!=p_i. This happens with probability of 1/2. Therefore n iterations will be performed with probability 1/2^n. So, expected number of iterations (flips) is E(X)=sum_(n=1)^oon/2^n=2.