Algorithms · LESSON 6 · Method ②
Weighted key draw — Efraimidis–Spirakis
Compute a "Key value" for each entrant from a random number. A bigger weight tends to give a smaller Key, and wins go in ascending Key order. A single sort picks several with no duplicates.
Concept
Key = −ln(u) / w
For each entrant, draw one random number u between 0 and 1 and compute Key = −ln(u) / w from the weight w. Here, ln is the natural log. A bigger w makes a smaller Key. Sort all entrants by ascending Key, and the front of the list is the win priority.
key = −ln(u) / wu: a random number between 0 and 1 · w: the entrant's weight. A bigger weight gives a smaller Key and a higher rank.
Why does it work? −ln(u) turns the random number into a value suited to applying weight. As a result, win probability stays proportional to weight, yet it finishes in one sort with no collisions or redraws.
Experiment
Follow an example — 2 of 4
Here are the u and Key of 4 people with different weights. The 2 with the smallest Key win.
| Entrant | Weight w | Random u | Key = −ln(u)/w | Rank |
|---|
Verify
Is it really by weight? — draw 5,000×
Draw 2 of 4 people with weights 1·2·3·4 many times and compare the win counts. Does a bigger weight win more often?
A bigger weight is more likely to yield a small Key, so it wins more often. But since the numbers are random, a lower-weight person can win too — that is what makes it a fair "draw."
menu_bookReferences · Weighted key draw
- Efraimidis, P. S., & Spirakis, P. G. (2006). Weighted Random Sampling with a Reservoir. Information Processing Letters, 97(5), 181–185.