Probabilistic selection from a set

Question

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

Answer 1

#!/usr/bin/perl

use strict; use warnings;

my @p = map { ($_) x int(1 + rand 50) } 0 .. 30;
my @s = @p[ map rand @p, 1 .. 10 ];
print "@s\n";

Answer 2

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.