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

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.

## Answers

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.