Algorithms · LESSON 6 · Method ①
Weighted interval draw
Give each entrant a "winning interval" as wide as their weight. Draw one random number from 1 to the total weight, and the owner of the interval it lands in wins.
Concept
What is a "winning interval"?
Line the entrants up and let each take a stretch (an interval) as long as their weight. A bigger weight means a wider interval. Then draw a random number (the "target value") between 1 and the total weight, and the entrant whose interval contains it is the winner.
Why is it fair? The wider the interval (= the bigger the weight), the more likely a random number lands in it. So the win probability is exactly proportional to weight.
Experiment
Try it yourself — the win interval
These are the winning intervals of 4 people (A·B·C·D) with different weights. Press "Draw target value" and the owner of the interval a random number between 1 and 10 lands in wins.
Entrant info
Weight interval per entrant
110
A random number is more likely to land in a wide interval (a higher-weight person). So a bigger weight wins more often.
Verify
Is it really by weight? — draw 5,000×
Draw 4 people with weights 1·2·3·4 many times and count the wins. When the bar heights approach the weight ratio (1:2:3:4), it is fair.
menu_bookReferences · Weighted interval draw
- Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3rd ed.), §3.4.1. Addison-Wesley.