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