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 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p?

Answer:

If we run BIASED-RANDOM twice, we might get of of following result: 00, 01, 10, 11. And the probabilities for getting each of them is: (1-p) square, (1-p)*p, p*(1-p), p square respectively. We can see that the probabilities for getting 01 equals 10. So, if we can constraint the output to either 01 or 10, we have a UNBIASED-RANDOM that can return 01 or 10 with probability of 1/2 each. And we can simply replace 01, 10 with 0 and 1 to get desired function. How can we constraint the result in 01 and 10? We can use the similar idea used in Ex5.1-2, that's abandoning any result that doesn't belong to 01 and 10 till we get one of them.

And there's a risk in this algorithm. If p is very close to 1 or 0, we may need to try a looooot of times to get either 01 or 10 which makes a very poor performance. To get around this, we can invoke BIASED-RANDOM more times. As we know, the probability of getting a full 0 or 1 permutation is p power the number of times invoking BIASED-RANDOM. And because p is between 0 and 1, the more we invoke BIASED-RANDOM, the less will the probability be, consequently the quicker we don't get full 0 or 1.

Code:

#include "iostream"

#include "ctime"

using namespace std;

int p = 50;

int BIASED_RANDOM ()

{

int rc = 0;

if((rand() % 100) >= p)

rc = 1;

else

rc = 0;

return rc;

} // ----- end of function BIASED_RANDOM -----

int UNBIASED_RANDOM()

{

int rc = 0;

int temp = 0;

int i = 0;

while(true)

{

temp = 0;

temp = BIASED_RANDOM() * 10 + BIASED_RANDOM();

if(temp == 10 || temp == 1)

break;

}

if(temp == 10)

rc = 1;

else

rc = 0;

return rc;

}

int main ( int argc, char *argv[] )

{

if(argc > 1)

p = atoi(argv[1]);

srand(time(NULL));

int rc = 0;

for(int i = 0; i < 100; ++i)

rc += BIASED_RANDOM();

cout << "BIASED SUM:" << rc << endl;

rc = 0;

for(int i = 0; i < 100; ++i)

rc += UNBIASED_RANDOM();

cout << "UNBIASED SUM:" << rc << endl;

return 0;

} // ---------- end of function main ----------

## No comments:

Post a Comment