Probabilistic selection from a set

By : PBJ

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:

  1. Make a lookup table V where V(n) = V(n-1) + P(n); with base case V(0) = P(0).
  2. Generate a random number X with a uniform distribution between 0 and the maximum value of V.
  3. Find the smallest value of n such that V(n) > X.

Is something like this already implemented in a library? (Using Perl.)

By : PBJ


This is actually a very popular problem, and is called weighted random selection (or sometimes weighted random choice). Here's a complete article about it.

This video can help you solving your question :)
By: admin