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.


Need Your Help

SVN merge problem with “svn:mergeinfo” property

svn merge

I have one big problem with merging - it falls on start with strange message: "Server sent unexpected return value (401 Authorization Required) in responce to PROPFIND request for

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.