How to pick an item by its probability?

Question

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 1

So with each item store a number that marks its relative probability, for example if you have 3 items one should be twice as likely to be selected as either of the other two then your list will have:

 [{A,1},{B,1},{C,2}]

Then sum the numbers of the list (i.e. 4 in our case). Now generate a random number and choose that index. int index = rand.nextInt(4); return the number such that the index is in the correct range.

Java code:

class Item {
    int relativeProb;
    String name;

    //Getters Setters and Constructor
}

...

class RandomSelector {
    List<Item> items = new List();
    Random rand = new Random();
    int totalSum = 0;

    RandomSelector() {
        for(Item item : items) {
            totalSum = totalSum + item.relativeProb;
        }
    }

    public Item getRandom() {

        int index = rand.nextInt(totalSum);
        int sum = 0;
        int i=0;
        while(sum < index ) {
             sum = sum + items.get(i++).relativeProb;
        }
        return items.get(Math.max(0,i-1));
    }
}

Answer 2

My method is pretty simple. Generate a random number. Now since the probabilities of your items are known,simply iterate through the sorted list of probability and pick the item whose probability is lesser than the randomly generated number.

For more details,read my answer here.

Answer 3

Brent's answer is good, but it doesn't account for the possibility of erroneously choosing an item with a probability of 0 in cases where p = 0. That's easy enough to handle by checking the probability (or perhaps not adding the item in the first place):

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

Answer 4

You could use the Julia code:

function selrnd(a::Vector{Int})
    c = a[:]
    sumc = c[1]
    for i=2:length(c)
        sumc += c[i]
        c[i] += c[i-1]
    end
    r = rand()*sumc
    for i=1:length(c)
        if r <= c[i]
            return i
        end
    end
end

This function returns the index of an item efficiently.

Answer 5

A slow but simple way to do it is to have every member to pick a random number based on its probability and pick the one with highest value.

Analogy:

Imagine 1 of 3 people needs to be chosen but they have different probabilities. You give them die with different amount of faces. First person's dice has 4 face, 2nd person's 6, and the third person's 8. They roll their die and the one with the biggest number wins.

Lets say we have the following list:

[{A,50},{B,100},{C,200}]

Pseudocode:

 A.value = random(0 to 50);
 B.value = random(0 to 100);
 C.value = random (0 to 200);

We pick the one with the highest value.

This method above does not exactly map the probabilities. For example 100 will not have twice the chance of 50. But we can do it in a by tweaking the method a bit.

Method 2

Instead of picking a number from 0 to the weight we can limit them from the upper limit of previous variable to addition of the current variable.

[{A,50},{B,100},{C,200}]

Pseudocode:

 A.lowLimit= 0; A.topLimit=50;
 B.lowLimit= A.topLimit+1; B.topLimit= B.lowLimit+100
 C.lowLimit= B.topLimit+1; C.topLimit= C.lowLimit+200 

resulting limits

A.limits = 0,50
B.limits = 51,151
C.limits = 152,352

Then we pick a random number from 0 to 352 and compare it to each variable's limits to see whether the random number is in its limits.

I believe this tweak has better performance since there is only 1 random generation.

There is a similar method in other answers but this method does not require the total to be 100 or 1.00.

Answer 6

You can try the Roulette Wheel Selection.

First, add all the probabilities, then scale all the probabilities in the scale of 1, by dividing each one by the sum. Suppose the probabilities are A(0.4), B(0.3), C(0.25) and D(0.05). Then you can generate a random floating-point number in the range [0, 1]. Now you can decide like this:

random number between 0.00 and 0.40 -> pick A
              between 0.40 and 0.70 -> pick B
              between 0.70 and 0.95 -> pick C
              between 0.95 and 1.00 -> pick D

You can also do it with random integers - say you generate a random integer between 0 to 99 (inclusive), then you can make decision like the above.