Weighted random integers

Question

I want to assign weightings to a randomly generated number, with the weightings represented below.

  0  |  1  |  2  |  3  |  4  |  5  |  6
─────────────────────────────────────────
  X  |  X  |  X  |  X  |  X  |  X  |  X
  X  |  X  |  X  |  X  |  X  |  X  |   
  X  |  X  |  X  |  X  |  X  |     |   
  X  |  X  |  X  |  X  |     |     |   
  X  |  X  |  X  |     |     |     |   
  X  |  X  |     |     |     |     |   
  X  |     |     |     |     |     |   

What's the most efficient way to do it?

Answer 1

@Kerrek's answer is good.

But if the histogram of weights is not all small integers, you need something more powerful:

Divide [0..1] into intervals sized with the weights. Here you need segments with relative size ratios 7:6:5:4:3:2:1. So the size of one interval unit is 1/(7+6+5+4+3+2+1)=1/28, and the sizes of the intervals are 7/28, 6/28, ... 1/28.

These comprise a probability distribution because they sum to 1.

Now find the cumulative distribution:

P        x
7/28  => 0
13/28 => 1
18/28 => 2
22/28 => 3
25/28 => 4
27/28 => 5
28/28 => 6

Now generate a random r number in [0..1] and look it up in this table by finding the smallest x such that r <= P(x). This is the random value you want.

The table lookup can be done with binary search, which is a good idea when the histogram has many bins.

Note you are effectively constructing the inverse cumulative density function, so this is sometimes called the method of inverse transforms.