Modifying the range of a uniform random number generator

Question

I am given a function rand5() that generates, with a uniform distribution, a random integer in the closed interval [1,5]. How can I use rand5(), and nothing else, to create a function rand7(), which generates integers in [1,7] (again, uniformly distributed) ?

---

1. I searched stackoverflow, and found many similar questions, but not exactly like this one.
2. My initial attempt was rand5() + 0.5*rand5() + 0.5*rand5(). But this won't generate integers from 1 to 7 with uniform probability. Any answers, or links to answers, are very welcome.

Answer 1

Note that a prefect uniform distribution cannot be achieved with a bounded number of draw5() invocations, because for every k: 5^k % 7 != 0 - so you will always have some "spare" elements.

Here is a solution with unbounded number of draw5() uses:

Draw two numbers, x1,x2. There are 5*5=25 possible outcomes for this.

Note that 25/7 ~= 3.57. Chose 3*7=21 combinations, such that each combination will be mapped to one number in [1,7], for all other 4 numbers - redraw.

For example:

(1,1),(1,2),(2,1) : 1
(3,1),(1,3),(3,2): 2
(3,3),(1,4),(4,1): 3
(2,4),(4,2)(3,4): 4
(4,3), (4,4), (1,5): 5
(5,1), (2,5), (5,2) : 6
(5,3), (3,5), (4,5) : 7
(5,4),(5,5),(2,3), (2,2) : redraw

Answer 2

Here's a simple way:

1. Use rand5() to generate a sequence of three random integers from the set { 1, 2, 4, 5 } (i.e., throw away any 3 that is generated).
2. If all three numbers are in the set { 1, 2 }, discard the sequence and return to step 1.
3. For each number in the sequence, map { 1, 2} to 0 and { 4, 5 } to 1. Use these as the three bit values for a 3-bit number. Because the bits cannot all be 0, the number will be in the range [1, 7]. Because each bit is 0 or 1 with equal probability, the distribution over [1, 7] should be uniform.

Answer 3

ok I had to think about it for a while but it is actually not that hard. Imagine instead of rand5 you had rand2 which either outputs 0 or 1. You can make rand2 our of rand5 by simply doing

rand2() {
    if(rand5() > 2.5) return 1
    else return 0
}

now using rand2 multiple times do a tree to get rand7. For example if you start rand7 can be in [1,2,3,4,5,6,7] after a throw of rand2 which gives 0 you now subset to [1,2,3,4] and after another throw or rand2 which is 1 you subset to [3,4] and a final throw of 1 gives the output of rand7 to be 4. In general this tree trick can work to take a rand2 and map to randx where x is any integer.

Answer 4

Here's one meta-trick which comes in handy for lots of these problems: the bias is introduced when we treat the terms differently in some fashion, so if we treat them all the same at each step and perform operations only on the set, we'll stay out of trouble.

We have to call rand5() at least once (obviously!), but if we branch on that bad things happen unless we're clever. So instead let's call it once for each of the 7 possibilities:

In [126]: import random

In [127]: def r5():
   .....:     return random.randint(1, 5)
   .....: 

In [128]: [r5() for i in range(7)]
Out[128]: [3, 1, 3, 4, 1, 1, 2]

Clearly each of these terms was equally likely to be any of these numbers.. but only one of them happened to be 2, so if our rule had been "choose whichever term rand5() returns 2 for" then it would have worked. Or 4, or whatever, and if we simply looped long enough that would happen. So there are lots of way to come up with something that works. Here (in pseudocode -- this is terrible Python) is one way:

import random, collections

def r5():
    return random.randint(1, 5)

def r7():
    left = range(1, 8)
    while True:
        if len(left) == 1: 
            return left[0]
        rs = [r5() for n in left]
        m = max(rs)
        how_many_at_max = rs.count(m)
        if how_many_at_max == len(rs):
            # all the same: try again
            continue
        elif how_many_at_max == 1:
            # hooray!
            return left[rs.index(m)]
        # keep only the non-maximals
        left = [l for l,r in zip(left, rs) if r != m]

which gives

In [189]: collections.Counter(r7() for _ in xrange(10**6))
Out[189]: Counter({7: 143570, 5: 143206, 4: 142827, 2: 142673, 6: 142604, 1: 142573, 3: 142547})