How to choose an item by its probability?

Question

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

Can anyone suggest an algorithm for selecting an element based on its probability?

Answer 1

Thus, each element stores a number that marks its relative probability, for example, if you have 3 elements, you should be twice as likely as one of the other two, then your list will have:

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

Then we summarize the list numbers (i.e. 4 in our case). Now create a random number and select this index. int index = rand.nextInt (4); return the number so 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

• Create a uniformly distributed random number.
• Iterate over the list until the cumulative probability of the items visited is greater than a random number.

Code example:

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

Answer 3

pretend that we have the following list

 Item A 25% Item B 15% Item C 35% Item D 5% Item E 20% 

Let's pretend that all the probabilities are integers and assign each element a "range", which is calculated as follows.

 Start - Sum of probability of all items before End - Start + own probability 

The new numbers are as follows

 Item A 0 to 25 Item B 26 to 40 Item C 41 to 75 Item D 76 to 80 Item E 81 to 100 

Now select a random number from 0 to 100. Suppose you select 32. 32 falls into item range B.

Mj

Answer 4

You can try Choosing a roulette wheel .

Add all the probabilities first, then scale all the probabilities on a scale of 1, dividing each by the sum. Assume that the probabilities A(0.4), B(0.3), C(0.25) and D(0.05) . Then you can create a random floating point number in the range [0, 1]. Now you can solve the following:

 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 this with random integers - let's say you generate a random integer from 0 to 99 (inclusive), then you can make a decision as described above.

Answer 5

The algorithm described in Ushman's , Brent and @kaushaya answers is implemented in the Apache commons-math library .

Take a look at the EnumeratedDistribution class (groovy code follows):

 def probabilities = [ new Pair<String, Double>("one", 25), new Pair<String, Double>("two", 30), new Pair<String, Double>("three", 45)] def distribution = new EnumeratedDistribution<String>(probabilities) println distribution.sample() // here you get one of your values 

Please note that the sum of the probabilities should not be equal to 1 or 100 - it will be automatically normalized.

Answer 6

My method is pretty simple. Create a random number. Now, since the probabilities of your items are known, simply iterate over the sorted probability list and select an element whose probability is less than a random number.

See my answer here for more details.

Answer 7

A slow but easy way to do this is so that each member can choose a random number based on its probability and choose the one that matters the most.

Analogy:

Imagine that you need to choose 1 out of 3 people, but they have different probabilities. You let them die with a different number of faces. The first person of the bone has 4 faces, the 2nd person is 6 and the third person is 8. They roll their dice, and the one with the most victories wins.

Let's say we have the following list:

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

pseudo code:

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

We choose the one that matters the most.

This method above does not accurately represent probabilities. For example, 100 will not have a double chance of 50. But we can do this by slightly changing the method.

Method 2

Instead of choosing a number from 0 to weight, we can limit them from the upper limit of the previous variable to adding the current variable.

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

pseudo code:

  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 

end limits

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

Then we select a random number from 0 to 352 and compare it with each variable limit to see if the random number is within it.

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

Other answers have a similar method, but this method does not require the sum to be 100 or 1.00.

Answer 8

The Brent answer is good, but it does not take into account the possibility of erroneous selection of an element with probability 0 in cases where p = 0. It is quite easy to cope by checking the probability (or, possibly, not adding an element 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 9

You can use 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 effectively returns the index of the element.