Why does the distribution of pseudorandom numbers change when operating like this?

Question

We were introduced to the standard C rand() function, and how to use it.

At some point during the class we were asked how to roll a die. The simple answer was to create a random number, take its modulo 6, and add 1.

rand()%6 + 1

However, the right answer was building a function that returns a value in the range [0,1) and then operating with that function to get a random number between 1 and 6.

Since most people in my class haven't seen probability yet, we weren't told why this was the right answer, but the class's assistant told us that taking the modulo of the random number produces a normal distribution of the numbers, while the other function we built:

rand / ((double) RAND_MAX + 1)

produces a uniform distribution.

Could anyone explain why this happens? I'm not a CS student myself so my knowledge is very basic

Thanks in advance.

Answer 1

rand() returns an integer uniformly distributed between 0 (inclusive) and RAND_MAX (exclusive).

When using modulo to partition those possibilities into 6 buckets you will end up with a few buckets that has 1 more possibility than the others. This means the random result ends up biased.

However the exact same thing happens if you use divide. The only difference lies in which buckets get biased.

This is due to pigeon stuffing. There is no way to divide a population of $2^n$ individuals into 6 groups perfectly evenly.

Instead you should check whether one of the biassing results is returned from rand() and generate a new number if so:

int bias = RAND_MAX % 6;
int divisor = (RAND_MAX - bias)/6;

while(true){
    int random = rand();
    if(random < RAND_MAX - bias) 
        return random / divisor;
}

The difference between divide and modulo for partitioning the data has to do with which bits are more random. Many implementations of rand() use a simple linear congruential generator where the more significant bits have better randomness than the lesser significant bits. In a good RNG every bit is equally random and it does not matter whether you use modulo or divide.

Having said all that if you really cared about randomness you would use a proper high quality random number generator that doesn't have some of the well known issues you'll find in a LCG.

Answer 2

If your class assistant is indeed telling you that rand() % 6 + 1 produces a normal distributed random variable, that’s total and utter nonsense. Please check that this is indeed what he has been telling you.

Fact is that pseudo random number generators often produce reasonably well distributed numbers in a large range, but the lowest bits are often not very random. You might have 64 but random numbers where the lowest bits alternate between 0 and 1.. rand() % 6 + 1 would then alternate between 1/3/5 and 2/4/6 - not very random, but not random distributed either. That’s why you would avoid using the lowest bits.

In reality, you would write code that picks numbers from 1 to 6 using any method you like, and then test it. (The first random number generator u ever used had the nice property that out of any two consecutive random numbers, the second one was larger 60% of the time).