Help Generating Weighted Random Numbers

I want to generate a random number between 1 and 1000 where the number 1000 only has a 1 in 1000 chance to be picked.

I know I need to somehow weight the lowest numbers but I really have no idea how to approach this sort of math. Hoping someone smarter than me can point me in the right direction

This is actually a common Computer Science interview question. However, if you want â€śdynamicâ€ť weighting where there is a decimal weight for every single number between 1 and 1000 then you are looking for an â€śexponentialâ€ť equation and that isnâ€™t as intuitive as weight sets.

This solution will use static weight sets.

We will assign numbers 1,100 with a 50% chance
Numbers 101,500 with a 25% chance
Numbers 501,950 with a 15% chance
Numbers 951, 1000 with a 10% chance

``````local weights = {}
local sumOfAllWeight = 0;
for i = 1,1000 do
local chanceInteger = 0;
if (i <= 100) then
chanceInteger = 50;
elseif (i <= 500) then
chanceInteger = 25;
elseif (i <= 950) then
chanceInteger = 15;
else
chanceInteger = 10;
end
sumOfAllWeight += chanceInteger;
weights[i] = chanceInteger;
end
``````

Now, we use the algorithm below to choose a weighted integer.

1. Pick a random number [0,sumOfAllWeights]
2. Iterate through all of the numbers, keeping track of every weight we pass by
3. When the total weight we have iterated over is greater than our random from (1), return that number
``````local function getRandomWeightedNumber()
local randomWeight = math.random(0, sumOfAllWeight);
local iteratedWeight = 0;
for i = 1, #weights do
iteratedWeight += weights[i];
if (iteratedWeight >= randomWeight) then
return i
end
end
end
``````

We now have our random, weighted number.

2 Likes