Understanding uniform random number generation

Question

I was reading a question about generating rand7() from rand5(), and I still don't quite seem to understand it. The suggested solution is shown here:

        int i;
        do
        {
          i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
        } while(i > 21);
        // i is now uniformly random between 1 and 21
        return i % 7 + 1;  // result is now uniformly random between 1 and 7

I understand the approach, but I don't understand why the range has to be from 1 to 21. My solution would be this:

        int i;
        do
        {     
          i = (rand5()-1) + rand5();  // i is now uniformly random between 1 and 9
        } while(i > 7); 
        // i is now uniformly random between 0 and 6
        return i+1;

I haven't been able to convince myself the approach outlined above doesn't work. Can you guys give me an example of numbers that appears more than others, making my approach non-uniform? Why is the multiplier of 5 needed?

"i is now uniformly random between 1 and 9". I don't think that's true. There are two ways to generate 2 (1 - 1 + 2 or 2 - 1 + 1), but there's only one way to generate 1 (1 - 1 + 1). — Kevin, Oct 01 '14 at 19:32

score 2 · Answer 1 · answered Oct 01 '14 at 19:43

When you add two evenly distributed random numbers, the result is no longer evenly distributed. Consider the table of outcomes:

    1  2  3  4  5
  ---------------
1 | 1  2  3  4  5
2 | 2  3  4  5  6
3 | 3  4  5  6  7
4 | 4  5  6  7  8
5 | 5  6  7  8  9

Count the number of 5 in the table, and count the number of 1 and 9. The problem should be obvious.

By multiplying one random number by the range and adding the second, you're keeping the contribution of each number independent. There are exactly 25 different outcomes, each with a 1/25 probability.

score 1 · Accepted Answer · answered Oct 01 '14 at 19:43

Can you guys give me an example of numbers that appears more than others, making my approach non-uniform?

Certainly. Using your method, numbers near the middle of the range are more likely to appear than ones on the end; for example, 5 is five times more likely to appear than 1.

There is 1 way to make 1.

(1 - 1) + 1 = 1

There are 2 ways to make 2.

(1 - 1) + 2 = 2
(2 - 1) + 1 = 2

There are 3 ways to make 3.

(1 - 1) + 3 = 3
(2 - 1) + 2 = 3
(3 - 1) + 1 = 3

There are 4 ways to make 4.

(1 - 1) + 4 = 4
(2 - 1) + 3 = 4
(3 - 1) + 2 = 4
(4 - 1) + 1 = 4

There are 5 ways to make 5.

(1 - 1) + 5 = 5
(2 - 1) + 4 = 5
(3 - 1) + 3 = 5
(4 - 1) + 2 = 5
(5 - 1) + 1 = 5

There are 4 ways to make 6.

(2 - 1) + 5 = 6
(3 - 1) + 4 = 6
(4 - 1) + 3 = 6
(5 - 1) + 2 = 6

There are 3 ways to make 7.

(3 - 1) + 5 = 7
(4 - 1) + 4 = 7
(5 - 1) + 3 = 7

There are 2 ways to make 8.

(4 - 1) + 5 = 8
(5 - 1) + 4 = 8

There is 1 way to make 9.

(5 - 1) + 5 = 9

Understanding uniform random number generation

2 Answers2