Generating Random Numbers

How to generate random integer between A and B, using an unbiased coin. For ex. If A = 3 and B = 6 then your algorithm should generate 3, 4, 5, 6 with equal probabilities.

Solution:
Without loss of generality, we consider the problem of generating random number r in range [0,n] with n=B-A. We can return r+A as the solution to input problem. The number n can be represented using k bits where k = 1 + [log n] ([x] indicates the largest integer smaller than x). Now the k-bits can be generated using the unbiased coin trivially in O(k). The generated number r can be greater than n with probability = 1-(n+1)/2^k. If that happens then repeat the experiment. Pseudo code for the algorithm looks like the following:-

function random(A, B)
  n = B - A
  k = 1 + int(log n)
  r = 0
  for i = 1 to k
    bit = coin_toss(); // head means 1, tail means 0
    r += bit
    r <<= 1
    if r > n
      return random(A, B)
  return r

This function can go into infinite loop. Let us calculate the expected number of times random(A,B) is called. It is called once by the the actual caller and called again if r > n. Let us assume that the expected number of calls be e. The probability that r <= n is given as Pr(r <= n) = (n+1)/2^k.

=> e = 1 * Pr(r <= n) + (1 + e) * Pr(r > n) => e = 2^k/(n+1) 

In the worst case, n=2^m+1. In this case, k=1+m. We get

==> e = 2 * 2^m/(2^m + 2) < 2

So expected number of internal calls is at-most 2. This gives a good assurance against going into infinite loops. Note that e can be estimated by using the observation that random variable e - 1 is a geometric distribution. Another way to reach above conclusion is by observing probability of failure, p = 1-(n+1)/2^k < 1/2. Since the probability of failure is less than 1/2, the chances that we run into infinite loop is quite low.

The above solution can be explained in simpler terms as well. Assume that we have people numbered A to B and we are playing a tournament. In each round of the tournament, two players are paired up, they call on the coin toss, player who wins goes to next level. In case if pairs can not be formed we add dummies to form pairs. If a normal player wins we are done, but if dummy wins we repeat the experiment again. So for example if we have 3, 4, 5, 6, 7 as initial number, and we add 'd' as dummy. Then a possible tournament could be as follows:

round 1: (3 vs 4) , (5 vs 6) , (7 vs d) --- winner --> 3, 5, d
round 2: (3 vs 5), (d vs d) -- winner --> 5, d
round 3: (5 vs d) -- winner --> 5

If d wins the last round, we repeat the experiment. This algorithm is just the same as earlier algorithm.