Algorithms · LESSON 6
Weighted draw — two methods
Among entrants with different weights, winners are picked in proportion to their weight. Unipicker can now draw using one of two methods.
Pick a method
Which method to draw with?
In both methods, a bigger weight wins more often. Only the "path" to the result differs; the fairness is the same.
Method ①Weighted interval drawGive each entrant a "winning interval" as wide as their weight, then pick the owner of the interval where a random number between 1 and the total lands. Feels like spinning a roulette wheel.See details →
Method ②Weighted key drawCompute a "Key value" for each entrant from a random number, then win in ascending order. This is the Efraimidis–Spirakis method, picking several with a single sort.See details →
In common
What both methods uphold equally
Fisher–Yates shuffle of the draw settingsThe "seats" like 1st, 2nd, 3rd are shuffled at random, so which seat a winner takes is decided fairly too.
Wins proportional to weightThe higher an entrant's weight, the more often they win. But luck plays a part too, so a lower-weight person sometimes wins.
Reproduce & verify by seedWith the same seed, anyone can recompute identically and verify the result.