Search code examples
arraysalgorithmrandom

Weighted random selection from array

I would like to randomly select one element from an array, but each element has a known probability of selection.

All chances together (within the array) sums to 1.

What algorithm would you suggest as the fastest and most suitable for huge calculations?

Example:

id => chance
array[
    0 => 0.8
    1 => 0.2
]

for this pseudocode, the algorithm in question should on multiple calls statistically return four elements on id 0 for one element on id 1.

Solution

  • Compute the discrete cumulative density function (CDF) of your list -- or in simple terms the array of cumulative sums of the weights. Then generate a random number in the range between 0 and the sum of all weights (might be 1 in your case), do a binary search to find this random number in your discrete CDF array and get the value corresponding to this entry -- this is your weighted random number.