Suppose that you want to output 0 with probability 12 and 1

Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 p, where 0 p 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 Chapter 5 Probabilistic Analysis and Randomized Algorithms and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p?

Solution

UNBIASED-RANDOM() :

Output: 0 with possibility 1/2 and 1 with possibility 1/2

Step1: while true do

Step2: a BIASED-RANDOM()

Step3: b BIASED-RANDOM()

Step4: if a < b then return 0

Step5: if a > b then return 1

The algorithm calls BIASED-RANDOM twice to get two arbitrary numbers A and B. It repeat this until A not equal to B. Then, depending on whether A less than B (that is, A=0 and B=1) or A Greater than B(that is, A=1 and B=0) it returns 0 or 1 respectively.

On any iteration, we enclose Pr(A<B) =p(1-p) =Pr(B<A), that is, the possibility that the algorithm proceeds 0 on that iteration equals to the possibility that it returns 1 on that iteration. Since with possibility 1we return something at some point and the probabilities of returning 0 and1 are equal on each iteration, the total probability of returning 0 and 1 have to be 1/2 and 1/2 respectively.

The algorithms stops, if it either returns 0 or 1. On every iteration, the probability of this is Pr(A not equal to B) =Pr(A<B)+Pr(B<A) =2p(1-p). Thus, we have a sequence of independent Bernoulli trials, each with possibility 2p(1-p) of success. so, the number of iterations required before the algorithm stops is geometrically distributed with parameter 2p(1-p) .

The expected running time of the algorithm is (1/(p(1 p))).