How to Generate Weighted Random Numbers

Random numbers usually follow what we call a ‘uniform distribution’, meaning that there is the same chance that any of the numbers is picked.

But if you want some numbers to be picked more often than others you will need a different strategy: a weighted random number generator.

Some practical applications include:

• the loot table in a video game, where enemies can drop different items with varying drop rates.
• a raffle, where people with more tickets have more chances to win.

Simple Strategy

If you think about the raffle example you can come up with an obvious solution: generate an array which has one copy of the item for each ‘ticket’.

For example, if John buys 4 raffle tickets and David only buys 1, John will have 4 times more chances to win than David.

Here is a working implementation:

users  = { john: 4, david: 1 }
raffle = []

users.map do |name, tickets|
  tickets.times { raffle << name }
end

p raffle
# [:john, :john, :john, :john, :david]

p raffle.sample
# :john

I'm adding the person's name once for every ticket they bought, and then I pick a random name from that list. By virtue of being on the list more times, it will increase the chances of that name being picked.

I like this approach because it's very simple and once you have your list it's very fast to pick a winner.

Sum of Weights

There is another way you can do this that is more memory-efficient, the trade-off is that picking a random value is slower.

The idea is to pick a random number between 1 and the sum of all the weights, and then loop until you find a weight that is lower or equal than this number.

Here is the code:

def random_weighted(weighted)
  max    = sum_of_weights(weighted)
  target = rand(1..max)

  weighted.each do |item, weight|
    return item if target <= weight
    target -= weight
  end
end

def sum_of_weights(weighted)
  weighted.inject(0) { |sum, (item, weight)| sum + weight }
end

This code takes in a hash where the keys are the items and the values are the weights. You can call this method like this:

random_weighted(cats: 5, dogs: 1)
# :cats

You can test if this works as expected by looking at the distribution of the results after running it many times.

Here is an example:

counts = Hash.new(0)

def pick_number
  random_weighted(cats: 2, dogs: 1)
end

1000.times { counts[pick_number] += 1 }
p counts

Run this a few times and look at the output to see if the ratio is what it should be.

Conclusion

While there are more sophisticated algorithms, these two should serve you well. I hope you found this article useful, please share it with your friends so I can keep writing more!