generate random numbers within a range with different probabilities

Question

How can i generate a random number between A = 1 and B = 10 where each number has a different probability?

Example: number / probability

1 - 20%

2 - 20%

3 - 10%

4 - 5%

5 - 5%

...and so on.

I'm aware of some hard-coded workarounds which unfortunately are of no use with larger ranges, for example A = 1000 and B = 100000.

Assume we have a

    Rand()

method which returns a random number R, 0 < R < 1, can anyone post a code sample with a proper way of doing this ? prefferable in c# / java / actionscript.

Answer 1

Build an array of 100 integers and populate it with 20 1's, 20 2's, 10 3's, 5 4's, 5 5's, etc. Then just randomly pick an item from the array.

int[] numbers = new int[100];
// populate the first 20 with the value '1'
for (int i = 0; i < 20; ++i)
{
    numbers[i] = 1;
}
// populate the rest of the array as desired.

// To get an item:
// Since your Rand() function returns 0 < R < 1
int ix = (int)(Rand() * 100);
int num = numbers[ix];

This works well if the number of items is reasonably small and your precision isn't too strict. That is, if you wanted 4.375% 7's, then you'd need a much larger array.

Answer 2

There is an elegant algorithm attributed by Knuth to A. J. Walker (Electronics Letters 10, 8 (1974), 127-128; ACM Trans. Math Software 3 (1977), 253-256).

The idea is that if you have a total of k * n balls of n different colors, then it is possible to distribute the balls in n containers such that container no. i contains balls of color i and at most one other color. The proof is by induction on n. For the induction step pick the color with the least number of balls.

In your example n = 10. Multiply the probabilities with a suitable m such that they are all integers. So, maybe m = 100 and you have 20 balls of color 0, 20 balls of color 1, 10 balls of color 2, 5 balls of color 3, etc. So, k = 10.

Now generate a table of dimension n with each entry being a probability (the ration of balls of color i vs the other color) and the other color.

To generate a random ball, generate a random floating-point number r in the range [0, n). Let i be the integer part (floor of r) and x the excess (r – i).

if (x < table[i].probability) output i
else output table[i].other

The algorithm has the advantage that for each random ball you only make a single comparison.

Let me work out an example (same as Knuth).

Consider simulating throwing a pair of dice.

So P(2) = 1/36, P(3) = 2/36, P(4) = 3/36, P(5) = 4/36, P(6) = 5/36, P(7) = 6/36, P(8) = 5/36, P(9) = 4/36, P(10) = 3/36, P(11) = 2/36, P(12) = 1/36.

Multiply by 36 * 11 to get 393 balls, 11 of color 2, 22 of color 3, 33 of color 4, …, 11 of color 12. We have k = 393 / 11 = 36.

Table[2] = (11/36, color 4)

Table[12] = (11/36, color 10)

Table[3] = (22/36, color 5)

Table[11] = (22/36, color 5)

Table[4] = (8/36, color 9)

Table[10] = (8/36, color 6)

Table[5] = (16/36, color 6)

Table[9] = (16/36, color 8)

Table[6] = (7/36, color 8)

Table[8] = (6/36, color 7)

Table[7] = (36/36, color 7)