Generating a random number from 0 to 9 based on a series of coin flips

Question

What method can I use to minimize the amount of coin flips needed to generate a uniformly distributed number from 0 to 9?

I've done some research, but I haven't been able to figure out how to adapt it to this specific problem:

• Expand a random range from 1–5 to 1–7
• https://www.quora.com/How-do-I-use-a-fair-6-sided-die-to-generate-a-random-number-from-1-to-20-with-each-outcome-occurring-with-the-same-probability
• https://cs.stackexchange.com/questions/570/generating-uniformly-distributed-random-numbers-using-a-coin

Answer 1

You would need atleast 10 possible combinations while flipping the coin. We would have 16 permutations if the coins are flipped 4 times. So, the minimum number of flips required would be 4.

By referring to the algorithms mentioned in your reference, we can implement the problem as follows.

The variable randNum returns a uniformly distributed random number between 0-9.

The function rand2 simulates the coin flipping exercise by assigning 0 and 1 value to T and H or vice versa.

int[][][][] fourDimArr = { { { {1, 2},{3, 4} }, {{5, 6} ,{7, 8} } }, { { {9,10},{0,0} }, { {0,0},{0,0} } } };
int result = 0;
    while (result == 0)
    {
        int i = rand2();
        int j = rand2();
        int k = rand2();
        int l = rand2();
        result = fourDimArr[i][j][k][l];
    }
int randNum = result-1;

A simpler and more intuitive implementation is suggested by James K Polk in the comments below. It involves using the outcomes of the coin flips as bits of a four bit number.

By rejecting values >= 10 , we would generate a uniformly distributed random number between 0-9. For implementation, refer the code snippet below.

int result = 11;
        while(result>=10){
            result = 0;
            for(int j = 0; j < 4; j++){
                result = (result<<1)|rand2();
            }
        }
randNum = result;

An example implementation of rand2 is as follows:

private static int rand2() {
    if(Math.random()>0.5)return 1;
    return 0;
}

Note: The minimum number of flips required is 4. The number of flips required in the worst case is still infinite, but this condition never arises.