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.
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:
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:
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:
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:
Run this a few times and look at the output to see if the ratio is what it should be.
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!Learn how to generate weighted random numbers in Ruby with some easy to implement algorithms.
Randomly Choosing a Winner from a Weighted List with Excel
Quote of the Day
Fashion is architecture: it is a matter of proportions.
— Coco Chanel. I hold the same view of product design. There is a balance that must be achieved between price, features, and schedule.
Figure 1: Randomly Choosing a Winner. (Source)
My wife is participating in a friendly contest at work that encourages employees to exercise. The employees record how many laps they walk around a set course during a month. At the end of the month, an Excel “drawing” is held to award a prize to one of the exercisers. To encourage more exercising, the likelihood of winning is to be proportional to the number of laps each person walked during the month. I was asked if I could write an Excel worksheet that would perform this task. I thought it was an interesting spreadsheet that was worth sharing here. There is a simple macro in the worksheet that controls when the worksheet re-calculates (otherwise it re-calculates a winner every time you change anything on the worksheet).
To make things simple for the users, the worksheet has the following features:
- It uses a table that allows my wife to add people as new participants arrive with no change in the random chooser.
- No “helper” columns are used, which are confusing to some folks.
- The key calculation uses an array formula that generates a cumulative sum, which is a useful thing to have in your toolbox.
- When you press the count button, it actually performs the randomizing six times. I wanted to make sure I avoided any random number start-up issues.