Youre given a fair coin and asked to sample uniformly a numb

You\'re given a fair coin and asked to sample uniformly a number from {0, 1, 2, 3, 4}. Give a randomized algorithm and analyze the expected running time of your algorithm.

Solution

you want to pick some random object from a set (a random integer in the set [a,b] in your case), but you don\'t know how to do that, but you can pick some random object from a larger set containing the first set (in your case, [a,2k+a] for some k such that 2k+ab; this corresponds to k coin flips).

In such a scenario, you just keep picking elements from the bigger set until you randomly pick an element in the smaller set. If your smaller set is big enough compared to your larger set (in your case, [a,2k+a]

contains at most twice as many integers as [a,b], which is good enough), this is efficient.

As per the solution above, we already have a uniformly distributed random number generator R(m) in range [0,m-1] (can be done by tossing k coins, one for each bit).