Consider the following randomized algorithm for generating biased random bits. The subroutine FAIRCOIN returns either 0 or 1 with equal probability; the random bits returned by FAIRCOIN are mutually independent.
ONEINTHREE:
if FAIRCOIN = 0
return 0
else
return 1 - ONEINTHREE
(a) Prove that ONEINTHREE returns 1 with probability 1/3.
(b) What is the exact expected number of times that this algorithm calls FAIRCOIN? Prove your answer is correct.
(c) Now suppose you are given a subroutine ONEINTHREE that generates a random bit that is equal to 1 with probability 1/3. Describe a FAIRCOIN algorithm that returns either 0 or 1 with equal probability, using ONEINTHREE as a subroutine. Your only source of randomness is
ONEINTHREE; in particular, you may not use the RANDOM function from problem 3.
(d) What is the exact expected number of times that your FAIRCOIN algorithm calls ONEINTHREE?
Prove your answer is correct.