Choose item from a list with bias?

Question

Given a list of items x1 ... xn and associated probabilties p1 ... pn that sum up to 1 there's a well known procedure to select a random item with its associated proabability by sorting the list according to weight, choosing a random value between 1 and 0, and adding up to a culmination sum until it exceeds the value selected and return the item at this point.

So if we have x1 -> 0.5, x2 -> 0.3, x3 -> 0.2, if the randomly chosen value is less than 0.5 x1 will be chosen, if between 0.5 and 0.8, x2, and else x3.

This requires sorting so it needs O(nlogn) time. Is there anything more efficient than that?

Answer 1

I don't think you would actually need to sort the list for the algorithm to work.

x1 = 0.2, x2 = 0.7, x3 = 0.1

If you sort then you have:

x3: 0.0 to 0.1 = 10%
x1: 0.1 to 0.3 = 20%
x2: 0.3 to 1.0 = 70%

If you dont, you instead get:

x1: 0.0 to 0.2 = 20%
x2: 0.2 to 0.9 = 70%
x3: 0.9 to 1.0 = 10%

Just eliminating the sort and iterating through would make it O(n).