Suppose that we want to generate a random variable X that is equally likely to be either 0 or 1, and that all we have at our disposal is a biased coin that, when flipped, lands on heads with some (unknown) probability p. Consider the following procedure: 1.

Flip the coin, and let 0,, either heads or tails, be the result. 2.

Flip the coin again, and let 0 be the result. 3.

If 0, and 02 are the same, return to step 1.

4. If O is heads, set X = 0, otherwise set X = 1.

(a) Show that the random variable X generated by this procedure is equally likely to be either 0 or 1.

(b) Could we use a simpler procedure that continues to flip the coin until the last two flips are different, and then sets X = 0 if the final flip is a head, and sets X = 1 if it is a tail?