Weighted Random Selection With Dynamic Probabilities

Question

I've been looking for a good algorithm for selecting a random object from a list of objects with differently weighted probabilities, and have found a veritable trove of possibilities, from putting each object in an array n times, to performing a binary search on an array containing the discrete cumulative density function (CDF), to putting the CDF in buckets, and a few more confusing responses, especially courtesy of Weighted random selection from array.

But the responses all seem to focus on efficiency of making the random selection instead of the cost of building or adjusting the weights dynamically. As my application seems that it might require the weights being adjusted at runtime nearly as often as a selection is made, what would be the most efficient algorithm allowing for dynamic adjustments to the probability weights? Adding new objects to the list will probably only be done at initialization, but removal of objects could be done a bit more infrequently than merely changing the values (perhaps setting the probability to zero would suffice).

My initial impression is that using an array of CDFs is my best bet; applying the same adjustment to everything after the probability being targeted seems trivial enough, but I'm not seeing anything quite so easy for the CDF bucket, for example. Any ideas?

If anyone cares, I'm implementing this with haxe.

• David Eisenstat: You could use a Fenwick tree for O(log n)-time samples and updates, but depending on what the adjustments are, you may be able to do better.

Answer 1

Suppose you have and array of objects {O.1, O.2, ... , O.N} and an array of associated probability weights {w.1, w.2, ..., w.N}

You can setup ranges of values ("buckets") between 0 and 1 that are sized according to each of the weights, then just pick a random value (with uniform distribution) between 0 and 1. The random value will fall in one of the buckets you've defined. If it falls in the i'th bucket, pick the i'th object from the array.

sorry, I don't know haxe, but here is some java code to illustrate:

 Random mRandom = new Random();
double[] weights = {0.3, 0.2, 0.1, 0.5}; //Make sure these sum to 1!! But at least you can change these at run-time.
int getRandomObject() {
 double randNum = mRandom.nextDouble();
 double sumOfWeightSoFar = 0;
 int currentIndex = 0;
 while (true) {
 if (randNum < weights[currentIndex] + sumOfWeightSoFar)
 return currentIndex;
 else {
 currentIndex++;
 sumOfWeightSoFar = sumOfWeightSoFar + weights[currentIndex];
 }
 }
 //If your weights don't sum to 1 or more, then "currentIndex" will eventually exceed your array bounds. But you get the idea.
}

• erickson: This doesn't address the problem. His probabilities are changing, so he'd need to rebuild this table every time he does a selection. And, even if you have fixed probabilities, this isn't a good implementation; a binary tree gives you quicker lookups and most libraries will have an API to perform the selection without extra code.
• rothloup: I thought that his point was that existing implementations work best with fixed probabilities, and he wanted something he could change at runtime. Setting the value of the "weights[]" array can be done at runtime. Certainly someone can come up with a more efficient implementation, but the concept is illustrated...unless I've completely missed the question.
• Trevortni: Thanks, but this seems to be a restating of what I stated in my question as what I currently think my best bet is, minus the binary searching and computing the CDF at the time of the alteration.