Probability selection algorithm

[Chad Netzer]

On Sat, 2003-02-01 at 14:43, Noah wrote:
> I'm chewing over a little algorithm problem. It's a simple problem.
> Given a list of probabilities, what is the simplest way to randomly select
> one of the items from the list based on that item's probability?
> For example, here are some lists of probabilities:
>     [0.2, 0.2, 0.2, 0.2, 0.2]
>         items all have equal chance of getting selected (20%)
>     [0.33, 0.33, 0.33]
>         items all have equal chance of getting selected (33%)
>     [0.33, 0.66]
>         item 1 is twice as likely to get selected as item 0.

You have (basically) a pdf (probability density function).  What you
need is a cdf (cumulative density function).

The cdf is the probability of all events before and up to that event.

ie. so if pdf is [0.1, 0.3, 0.2, 0.2, 0.1, 0.1]

the cdf is [0.1, 0.4, 0.6, 0.8, 0.9, 1.0]

You can make a cdf from a pdf easily (I'll leave that as an exercise).

Now, generate a uniform random number, and scan the cdf from the
beginning, finding the first value that is larger than the generated
random number.  That will be the index of the item you want to have
selected.  Given a uniform RNG, the items will be slected w/ a
probability according to their probabilistic weight.

-- 
Bay Area Python Interest Group - http://www.baypiggies.net/

Chad Netzer
(any opinion expressed is my own and not NASA's or my employer's)