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.

Solution 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.

Solution 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)

Solution 3

Assuming that you have a function p(n) that gives you the desired probability for a random number:

r = rand()  // a random number between 0 and 1
for i in A to B do
    if r < p(i) 
      return i
    r = r - p(i)    
done

A faster way is to create an array of (B - A) * 100 elements and populate it with numbers from A to B such that the ratio of the number of each item occurs in the array to the size of the array is its probability. You can then generate a uniform random number to get an index to the array and directly access the array to get your random number.

Solution 4

Here's an implementation of Knuth's Algorithm. As discussed by some of the answers it works by 1) creating a table of summed frequencies 2) generates a random integer 3) rounds it with ceiling function 4) finds the "summed" range within which the random number falls and outputs original array entity based on it

Solution 5

Map your uniform random results to the required outputs according to the probabilities.

E.g., for your example:

If `0 <= Round() <= 0.2`: result = 1.
If `0.2 < Round() <= 0.4`: result = 2.
If `0.4 < Round() <= 0.5`: result = 3.
If `0.5 < Round() <= 0.55`: result = 4.
If `0.55 < Round() <= 0.65`: result = 5.
...

View more solutions

Comments

[SomeWittyUsername]

You probably mean if r > p(i). But this isn't correct. If 1 and 2 both appear with 20% percent probability, you'll always return just one of them and never the other.

[perreal]

in fact for 0.2 < r < 0.4 you will get 2.