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?

(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 your only source of randomness.