0

I came across a question to implement an unbiased random function which outputs 0 or 1 using a biased output function which outputs 0 or 1 with probability P for outputting 1. And to predict how the runtime varies in accordance with P

I implemented it as follows

Random() {
     i = BRand();
     j = BRand();

    if(j==0) j=1;
    else j=0;

    if(i==j)
          Return i;
    else
           Random();
    }

But I'm unable to figure out how the runtime would vary in terms of P.

Improve this question

1 Answer 1

Reset to default
0

I don't know why you would invert j in such a complicated way instead of just if (i != j).

The probability for such a pair is (1-P)*P+P*(1-P)=2*P*(1-P) (could be 01 or 10).

In a single step, you add 1 to the number of iterations, and with a probability of 1-2*P*(1-P) start the process again, resulting in the recursive formula E(N)=1+(1-2*P*(1-P))*E(N). Which, if you simplify the formula, tells you the more biased P is (away from 0.5), the worse the performance.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .