Suppose I want to randomly select a number n between 0 and 30, where the distribution is arbitrary, and not uniform. Each number has a corresponding weight P(n): P(0) = 5, P(1) = 1, P(2) = 30, P(3) = 25, and so on and so forth. How do I do a random selection from this set, such that the probability of selecting a number is proportional to its weight?
What is this type of random selection even called?
I can see one way of implementing it:
- Make a lookup table V where V(n) = V(n-1) + P(n); with base case V(0) = P(0).
- Generate a random number X with a uniform distribution between 0 and the maximum value of V.
- Find the smallest value of n such that V(n) > X.
Is something like this already implemented in a library? (Using Perl.)