Find a random number generator using a given random number generating function

Question

This is an interview question:

Given a function which generates a random number in [1,5],we need to use this function to generate a random number in the range [1,9]. I thought about it a lot but am not able to write an equation where ramdomness is satisfied. People please answer.This might be helpful maybe in some future interviews.

Answer 1

Adapted from "Expand a random range from 1–5 to 1–7"

It assumes rand5() is a function that returns a statistically random integer in the range 1 through 5 inclusive.

int rand9()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 8, 9, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 8, 9, 0, 0 },
        { 0, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result= vals[i-1][j-1];
    }
    return result;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 9, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.

this can run forever in the worst case, but statistically the worst case never happens. :)

Answer 2

int rand9()
{
    int t1,t2,res = 10;
    do {
        t1 = rand5();
        do {
            t2 = rand5();
        }while(t2==5);
        res = t1 + 5* (t2%2);
    }while(res==10);
    return res;
}

now 1 to 9 has the probability of 1/9.

make some explanation:

t1 has probability of 1/5 to be 1 to 5.

t2,too.but when t2==5,discarded.so t2 has probability of 1/4 to be 1 to 4.that' to say, probability of 1/2 to be odd or even,which makes t2%2 has probability of 1/2 to be 0 to 1.

thus, t1 + 5*(t2%2) has probability of 5/10 to be 1 to 5, and 5/10 to be 6 to 10. but 10 is discarded again,so the rest 9 numbers' probability is 1/9.

Answer 3

You need to use rejection sampling. That is, reject results that don't fit your target distribution. In your case you could use the lower three bits of two successive calls to your rand15 function (− 1 if necessary), concatenate them and reject those results that are outside your target interval and retry until you find a number that's inside.