The Crosby projectWeighted random choice and the alias method
Pick a Crosby resident at random. Which small census area are they in?
The census divides the country into output areas, small patches of a few streets each. The Crosby built-up area is made of 169 of them, and the 2021 count of residents in each one runs from 129 to 546. The learner's job is to write a Python function that returns the area of a randomly chosen resident. An area with 546 people should come up more than four times as often as one with 129. We use the area counts only as weights. Their sum is our own working figure, not an official population; the published figure for the town is the 50,215 above.
The first attempt most people write is wrong: pick one of the 169 areas with equal chance. Over a million draws that gave the largest area 5,879 picks when its fair share is 10,873, and gave the smallest 5,842 when it is due 2,569. Every area is treated alike, so residents of crowded areas are under-counted. The fix is to weight the choice, and there are three ways to do it.
Three correct ways to draw a weighted random area, 169 Crosby output areas, 1,000,000 draws each (our Python count)| Method | Comparisons per draw | Set-up work |
|---|
| Walk down the running totals | 86.3 on average | One pass to add up |
| Binary search the running totals (bisect) | 7.51 on average | One pass to add up |
| Alias table | 1, always | 168 pairing steps |
The walk is the obvious method: draw a random number up to the total and step through the list until the running total passes it, 86.3 comparisons on average. Sorting the areas largest first only trims that to 75.3, because the areas are all much the same size. Binary search halves the list each time and needs 7.51. The alias method changes the picture. Imagine 169 equal columns, one per area. Areas with more than the average spill their extra into the columns of areas with less, until every column is full and holds at most two areas: its owner and one alias. Building that table took 168 pairing steps. After that, a draw is one random column and one comparison to decide between owner and alias, no matter how many areas there are.
Fast is no use if it is unfair, so the learner checks. Per million draws the largest area should appear 10,873 times and the alias table gave 10,899; the smallest should appear 2,569 times and got 2,539. A chi-square test across all 169 areas scored 184.6 for the alias table and 166.1 for binary search, both ordinary values for 168 degrees of freedom, against 48,808 for the wrong uniform method. One more result surprises people: the area of a random resident holds 310.0 people on average, while a random area holds 297.1. Sampling by person tilts you towards bigger areas.
Ages 8 to 11
Make a spinner with unequal slices, then a fair-looking one with two colours per slice, and compare tallies.
Ages 11 to 15
Write the running-total walk in Python, count its comparisons, then swap in bisect.
Ages 15 and up
Build the alias table, prove each column sums to one share, and test a million draws for fairness.
About the data
Census 2021 output-area counts are from the Office for National Statistics through Nomis, read 30 September 2026, under the Open Government Licence. The sampling methods, the comparison counts and the checks are our own work with a fixed random seed; a different seed would move the tallies slightly.
