How do I select a random key from a hash using the probability distribution stored within the corresponding values?

Question

When I create a new opal, I want to randomly assign it one of many possible features. However, I want some qualities to be more common than others. I have a hash with possible features and their relative probability (out of a total of 1).

How do I choose a feature at random, but weighted according to the probability?

'possible_features': 
    {
        'white_pin_fire_green': '0.00138', 
        'white_pin_fire_blue': '0.00138', 
        'white_pin_fire_yellow': '0.00144', 
        'white_pin_fire_purple': '0.00144', 
        'white_pin_fire_pink': '0.00036',
        'white_straw_green': '0.01196', 
        'white_straw_blue': '0.01196', 
        'white_straw_yellow': '0.01248', 
        'white_straw_purple': '0.01248', 
        'white_straw_pink': '0.00312', 
        'white_ribbon_green': '0.01196', 
        'white_ribbon_blue': '0.01196', 
        'white_ribbon_yellow': '0.01248', 
        'white_ribbon_purple': '0.01248', 
        'white_ribbon_pink': '0.00312',  
        'white_harlequin_green': '0.0069', 
        'white_harlequin_blue': '0.0069', 
        'white_harlequin_yellow': '0.0072', 
        'white_harlequin_purple': '0.0072', 
        'white_harlequin_pink': '0.0018',
        'white_no_fire': '0.06', 
        'black_pin_fire_green': '0.00552', 
        'black_pin_fire_blue': '0.00552', 
        'black_pin_fire_yellow': '0.00576', 
        'black_pin_fire_purple': '0.00576', 
        'black_pin_fire_pink': '0.00144',
        'black_straw_green': '0.04784', 
        'black_straw_blue': '0.04784', 
        'black_straw_yellow': '0.04992', 
        'black_straw_purple': '0.04992', 
        'black_straw_pink': '0.01248', 
        'black_ribbon_green': '0.04784', 
        'black_ribbon_blue': '0.04784', 
        'black_ribbon_yellow': '0.04992', 
        'black_ribbon_purple': '0.04992', 
        'black_ribbon_pink': '0.01248', 
        'black_harlequin_green': '0.0276', 
        'black_harlequin_blue': '0.0276', 
        'black_harlequin_yellow': '0.0288', 
        'black_harlequin_purple': '0.0288', 
        'black_harlequin_pink': '0.0072',
        'black_no_fire': '0.24'
    }

For example, if I randomly generate 100 opals, I'd like for approximately 24 of them to have the "black_no_fire" feature.

Thank you for any help!

Answer 1

If I can assume that the hash values do indeed add up to exactly 1.0, then the solution is little simpler. (Otherwise, this approach would still work, but requires a little extra effort to first sum all the values - and use them as a weighting, but not a direct probability.)

First, let's choose a random value between 0 and 1, to represent a "fair selection". You may wish to use SecureRandom.random_number in your implementation.

Then, I loop through the possibilities, seeing when the cumulative sum reaches the chosen value.

possible_features = {
  white_pin_fire_green: "0.00138",
  white_pin_fire_blue: "0.00138",
  # ...
}

r = rand
possible_features.find { |choice, probability| (r -= probability.to_f) <= 0 }.first

This effectively treats each possibility as covering a range: 0 .. 0.00138, 0.00138 .. 0.00276, 0.00276 .. 0.00420, ..., 0.76 .. 1.

Since the original random value (r) is was chosen from an even distribution, its value will lie within one of those ranges with the desired weighted probability.

Answer 2

Suppose your hash were as follows.

pdf = {
  white_pin_fire_green:  0.21, 
  white_pin_fire_blue:   0.25, 
  white_pin_fire_yellow: 0.23, 
  white_pin_fire_purple: 0.16, 
  white_pin_fire_pink:   0.15
}

pdf.values.sum
  #=> 1.0

I've made the values floats rather than strings merely to avoid the need for a boring conversion. Note that the keys, which are symbols, do not require single quotes here.

We can assume that all of the values in pdf are positive, as any that are zero can be removed.

Let's first create a method that converts pdf (probability density function) to cdf (cumulative probability distribution).

def pdf_to_cdf(pdf)
  cum = 0.0
  pdf.each_with_object({}) do |(k,v),h|
    cum += v
    h[cum] = k
  end
end

cdf = pdf_to_cdf(pdf)
  #=> {0.21=>:white_pin_fire_green,
  #    0.45999999999999996=>:white_pin_fire_blue,
  #    0.69=>:white_pin_fire_yellow,
  #    0.85=>:white_pin_fire_purple,
  #    1.0=>:white_pin_fire_pink}

Yes, I've inverted the cdf by flipping the keys and values. That's not a problem, since all pdf values are positive, and it's more convenient this way, for reasons to be explained.

For convenience let's now create an array of cdf's keys.

cdf_keys = cdf.keys
  #=> [0.21, 0.46, 0.69, 0.85, 1.0]

We sample a single probability-weighted value by generating a (pseudo-) random number p between 0.0 and 1.0 (e.g., p = rand #=> 0.793292984248818) and then determine the smallest index i for which

cdf_keys[i] >= p

Suppose p = 0.65. then

cum_prob = cdf_keys.find { |cum_prob| cum_prob >= 0.65 }  
  #=> 0.69

Note that, because cdf_keys is an increasing sequence the operation

cum_prob = cdf_keys.find { |cum_prob| cum_prob >= rand }  

could be sped up by using Array#bsearch.

So we select

selection = cdf[cum_prob]
  #=> :white_pin_fire_yellow

Note that the probability that rand will be between 0.46 and 0.69 equals 0.69 - 0.46 = 0.23, which, by construction, is the desired probability of selecting :white_pin_fire_yellow.

If we wish to sample additional values "with replacement", we simply generate additional random numbers between zero and one and repeat the above calculations.

If we wish to sample additional values "without replacement" (no repeated selections), we must first remove the element just drawn from the pdf. First, however, let's note the probability of selection:

selection_prob = pdf[selection]
  #=> 0.23

Now delete selection from pdf.

pdf.delete(:white_pin_fire_yellow)
pdf
  #=> {:white_pin_fire_green=>0.21,
  #    :white_pin_fire_blue=>0.25,
  #    :white_pin_fire_purple=>0.16,
  #    :white_pin_fire_pink=>0.15}

As pdf.values.sum #=> 0.77 we must normalize the values so they sum to 1.0. To do that we don't actually have to sum the values as that sum equals

adj = 1.0 - selection_prob
  #=> 1.0 - 0.23 => 0.77

Now normalize the new pdf:

pdf.each_key { |k| pdf[k] = pdf[k]/adj }
  #=> {:white_pin_fire_green=>0.2727272727272727, 
  #    :white_pin_fire_blue=>0.3246753246753247, 
  #    :white_pin_fire_purple=>0.20779220779220778, 
  #    :white_pin_fire_pink=>0.1948051948051948}
pdf.values.sum
  #=> 1.0

We now repeat the steps described above when selecting the first element at random (construct cdf, generate a random number between zero and one, and so on).