[ALGO] Random number generator, with equal probability

RANDOM(a.b) is a random number generator that generates integers between a and b (inclusive), all equally likely.

Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/n, where n = (b-a+1)

Source : Cormen - Problem 5.1-2 (randomized algorithms)

Similar problem :
At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here  http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/


Madhur Kumar Tanwani said...

anand kishore said...

maybe this works for the *equal probability of choosinf n numbers* problem.

Assuming we have RAND(0,1).
And we have N numbers.

(1) Run RAND(0,1) N times.
(2) Add up all the outputs of RAND(0,1) generated above). This is nothing but an addition of all 1's generated.
(3) Use this sum as the index of the number to pick from N.

FY's said...

this would not work since the sum follows binomial distribution, thus don't have equally like chance

John Farell said...

Thanks for sahring a informationProbability Generator.