How to pick an item by its probability?

Ruzanna picture Ruzanna · Feb 17, 2012 · Viewed 57.8k times · Source

I have a list of items. Each of these items has its own probability.

Can anyone suggest an algorithm to pick an item based on its probability?

Answer

Brent Worden picture Brent Worden · Feb 17, 2012
  1. Generate a uniformly distributed random number.
  2. Iterate through your list until the cumulative probability of the visited elements is greater than the random number

Sample code:

double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability) {
        return item;
    }
}