Generating uniformly distributed random numbers using a coin

You have one coin. You may flip it as many times as you want.

You want to generate a random number r such that ar<b where r,a,bZ+.

Distribution of the numbers should be uniform.

It is easy if ba=2n:

r = a + binary2dec(flip n times write 0 for heads and 1 for tails) 

What if ba2n?

Answer

What you're looking for is based on Rejection sampling or the accept-reject method (note that the Wiki page is a bit technical).

This method is useful in these kinds of situations: 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.

An alternative example: suppose you want to pick a random point inside a circle with radius 1. Now, it isn't really easy to come up with a direct method for this. We turn to the accept-reject method: we sample points in a 1x1 square encompassing the circle, and test if the number we draw lies inside the circle.

Attribution
Source : Link , Question Author : Pratik Deoghare , Answer Author : Community

Leave a Comment