Generate integer from 1-8 with equal probability

Problem:

Write a method to generate a random number between 1 and 8, given a method that generates a random number between 1 and 3. The distribution between each of the numbers must be uniform.

Solution:

Let’s think of this like a decision tree. Each rand3() will be a decision.

If we somehow generate integers from 1 to a-multiple-of-8 (like 8, 16, 24, …) with equal probability, we can use modulo division by 8 followed by adding 1 to get the numbers from 1 to 8 with equal probability.

We try to get maximum bunches of 8 as we can (1 – 16, 2 sets of 8). If we get any of the other values, we just try again. Since the probability of getting each of 16 values are the same every time, trying again won’t affect their probabilities.

We can generate from 1 to 16 with equal probability using the following expression.
6*rand3() + rand3() – 3
See, how this can be used?
1. For each value of first rand3(), there can be 6 possible combinations for values of second rand3(). So, there are total 18 combinations possible.
2. The range of values returned by the above equation is 1 to 18, each integer occurring exactly once.
3. If the value of the equation comes out to be less than 17, return modulo division by 8 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/8.

// returns 1 to 8 with equal probability
int my_rand()
{
    int i;
	while(1)
	{
	    i = 6*rand3() + rand3() - 3;
	    if (i < 17)
	        return i%8 + 1;
	}
}

5 Thoughts on “Generate integer from 1-8 with equal probability

  1. m3th0d.itbhu on August 4, 2013 at 12:00 pm said:

    create a 3X3 matrix and fill the numbers as 1,2,3,4,5,6,7,8,-1. Assume rand3 as dice, roll it twice for i and j in matrix and return the number on i,j th location of matrix. In case the number is -1, repeat the step. probability will be equal as it would be 1/9.

  2. 1,1 and 2,3 will give same result

  3. integer rand8() {
    result = (rand3() – 1) * 3 + rand3();
    if (result != 9)
    return result;
    else
    rand8();
    }

    • That was my idea too. Seems like the same sort of “keep trying until it’s the result you were looking for” philosophy but a lot simpler.

  4. Dan Duncalf on April 7, 2015 at 6:24 pm said:

    I really don't understand the decision tree metaphor at all. This is a just math.

    First a couple nitpicky wording items. Between 1 and 3, doesn't say inclusive or exclusive. So we will assume that both of the betweens are inclusive, because just returning 2 (exclusive) isn't really random. This sort of ambiguity creates fence post errors (like the one on line 8).

    The possible options for 6*rand3()+rand3() – 3 are… 4,5,6.10,11,12,16,17,18 with mod 8, gives, 4,5,6,2,3,4,0,1,2. Since the last two are ignored, because they are 17 or greater, this leaves the possible results as (4,5,6,2,3,4,0)+1. Note this is only 7 probabilities, with one duplicate. So two values will never occur.

    A simpler math solution would be i = 3*(rand3()-1)+rand3(), and don't return any values over 8. However that said, since we are working with pseudo random number generators, skipping one out of 9 values will mess with the pseduorandomness and probably the distribution of these values. Better to go rewrite rand3(), to be rand8().

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation