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

why do I get either a Socket Exception or the wrong data when I do a DNS lookup?

c# .net url dns ip-address

When I open firefox and enter "209.191.122.70" as the URL and press enter, it immediately resolves to "http://failsafe.fp.yahoo.com/404.html"

SpriteKit Collision Detection with Transparent image

ios canvas png sprite-kit collision-detection

I am trying to learn SpriteKit by going through a tutorial on making a Flappy Bird like Game. In my version of the game, the pipes are not pipes, and are irregularly shaped objects that don't fill...

Compaq Visual Fortran versus gfortran FORMAT statement differences

fortran translate gfortran intel-fortran

I have a huge piece of Fortran code and I want to compile that code with gfortran. I have not worked with Fortran before. I do not know exactly what specification the code is of, but I found out th...

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.