How to write a function to generate random number 0/1 use another random function?

Question

If I have a function named rand1() which generates number 0(30% probability) or 1(70% probability), how to write a function rand2() which generates number 0 or 1 equiprobability use rand1() ?

Update：

Finally, I found this is a problem on book Introduction to Algorithms (2nd) (I have bought the Chinese edition of this book ), Excercise 5.1-3, the original problem is :

5.1-3 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?

the solution is : (see: http://www.cnblogs.com/meteorgan/archive/2012/05/04/2482317.html)

To get an unbiased random bit, given only calls to BIASED-RANDOM, call BIASED-RANDOM twice. Repeatedly do so until the two calls return different values, and when this occurs, return the Þrst of the two bits:

UNBIASED-RANDOM
while TRUE
do
x ← BIASED-RANDOM
y ← BIASED-RANDOM
if x != y
then return x

To see that UNBIASED-RANDOM returns 0 and 1 each with probability 1/2, observe that the probability that a given iteration returns 0 is

Pr {x = 0 and y = 1} = (1 − p)p ,

and the probability that a given iteration returns 1 is

Pr {x = 1 and y = 0} = p(1 − p) .

(We rely on the bits returned by BIASED-RANDOM being independent.) Thus, the probability that a given iteration returns 0 equals the probability that it returns 1. Since there is no other way for UNBIASED-RANDOM to return a value, it returns 0 and 1 each with probability 1/2.

Answer 1

Generate two numbers, a and b.

If a is 0 and b is 1 (21% chance), generate a 0.
If a is 1 and b is 0 (21% chance), generate a 1.

For all other cases (58% chance), just generate a new a and b and try again.

Answer 2

If you call rand1 twice, there is an equal chance of getting [1 0] and [0 1], so if you return the first of each non-matching pair (and discard matching pairs) you will get, on average, 0.5(1 - p2 - (1-p)2) output bits per input bit (where p is the probability of rand1 returning 1; 0.7 in your example) and independently of p, each output bit will be 1 with probability 0.5.

However, we can do better.

Rather than throw away the matching pairs, we can remember them in the hope that they are followed by opposite matching pairs - The sequences [0 0 1 1] and [1 1 0 0] are also equally likely, and again we can return the first bit whenever we see such a sequence (still with output probability 0.5.) We can keep combining them indefinitely, looking for sequences like [0 0 0 0 1 1 1 1] etc.

And we can go even further - consider the input sequences [0 0 0 1] and [0 1 0 0] produce the same output ([0]) as it stands, but these two sequences were also equally likely, so we can extract an extra bit of output from this, returning [0 0] for the first case and [0 1] for the second. This is where it gets more complicated though, as you would need to start buffering output bits.

Both techniques can be applied recursively, and taken to the limit it becomes lossless (i.e. if rand1 has a probability of 0.5, you get an average of one output bit per input bit.)

Full description (with math) here: http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf

Answer 3

You will need to figure out how close you want to get to 50% 0 50% 1.

If you add results from repeated calls to rand1. if the results is 0 or 2 then the value returned is 0 if it is 1 then return 1. (in code you can use modulo 2)

int val = rand1();   // prob 30%      0, and 70%      1

val=(val+rand1())%2; // prob 58%      0, and 42%      1  (#1 see math bellow)
val=(val+rand1())%2; // prob 46.8%    0, and 53.2%    1  (#2 see math bellow)
val=(val+rand1())%2; // prob 51.28%   0, and 48.72%   1
val=(val+rand1())%2; // prob 49.488%  0, and 50.512%  1
val=(val+rand1())%2; // prob 50.2048% 0, and 49.7952% 1

You get the idea. so it is up to you to figure out how close you want the probabilities. every subsequent call will gets you closer to 50% 50% but it will never be exactly equal.

If you want the math for the probabilities:

1

prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                           = (0.3*0.3)+(0.7*0.7)
                           = 0.09 + 0.49
                           = 0.58
                           = 58%

prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                           = (0.7*0.3)+(0.3*0.7)
                           = 0.21 + 0.21
                           = 0.42 
                           = 42%

2

 prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                            = (0.58*0.3)+(0.42*0.7)
                            = 0.174 + 0.294
                            = 0.468
                            = 46.8%

 prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                            = (0.42*0.3)+(0.58*0.7)
                            = 0.126 + 0.406
                            = 0.532
                            = 53.2%

Answer 4

Below rand2 function will provide 50% probability for occurence of zero or one.

#define LIMIT_TO_CALCULATE_PROBABILITY 10 //set any even numbers

int rand2()
{
    static int one_occurred = 0;
    static int zero_occured = 0;
    int rand_value = 0;
    int limit = (LIMIT_TO_CALCULATE_PROBABILITY / 2);

    if (LIMIT_TO_CALCULATE_PROBABILITY == (one_occured + zero_occured))
    {
        one_occured = 0;
        zero_occured = 0;
    }

    rand_value = rand1();   

    if ((1 == rand_value) && (one_occured < limit))
    {
        one_occured++;
        return rand_value;
    }
    else if ((0 == rand_value) && (zero_occured < limit))
    {
        zero_occured++;
        return rand_value;
    }
    else if (1 == rand_value)
    {
        zero_occured++;
        return 0;
    }
    else if (0 == rand_value)
    {
        one_occured++;
        return 1;
    }   
}