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/
Showing posts with label randomized. Show all posts
Showing posts with label randomized. Show all posts
Subscribe to:
Posts (Atom)
