Problem 588384 · medium · Level 05 Advanced Algorithms & Graphs

How Many Wristbands Were Sold?

estimator · bias · root mean square error · seeded simulation

A festival numbers its wristbands 1, 2, ..., N, but will not say how many it sold. You walk around and read the numbers of n different random wristbands. Three rules turn those numbers into a guess of N:

  • "max": the largest number seen, m,
  • "double_mean": twice the mean of the numbers seen, minus 1,
  • "gap": m + m / n - 1 (the largest number plus the average gap between the numbers seen).

Which rule is best? Simulate it. Write serial_estimators(N, n, reps, seed) that follows these rules exactly:

  • Create one generator rng = random.Random(seed).
  • Repeat reps times: draw the n numbers seen with one call rng.sample(range(1, N + 1), n) and apply all three rules to them.

For each rule, its bias is the mean of its reps guesses minus N, and its RMSE (root mean square error) is the square root of the mean of (guess - N) ** 2. Return a dict mapping each rule's name to the tuple (bias, rmse), plus the key "best" naming the rule with the smallest RMSE (on a tie, the first in the order max, double_mean, gap).

Examples

Input:  N = 10, n = 3, reps = 4, seed = 1
Output: {"max": (-2.5, 2.9154759474226504), "double_mean": (-1.1666666666666679, 3.0731814857642954),
         "gap": (-1.0, 2.2360679774997894), "best": "gap"}
Explanation: the four samples are [3, 2, 5], [2, 8, 9], [8, 7, 4] and [2, 8, 1]. The rule
"max" guesses 5, 9, 8 and 8: on average 7.5, which is 2.5 too low.

Input:  N = 300, n = 5, reps = 10000, seed = 2
Output: {"max": (-49.452799999999996, 64.8587542279375), "double_mean": (0.343119999999999, 76.89742716112158),
         "gap": (-0.3433600000000183, 50.35941858282322), "best": "gap"}
Explanation: "max" is always too low. "double_mean" is unbiased but scatters widely;
"gap" is unbiased and the most accurate.

Constraints

  • 1 <= n <= N <= 10**6, 1 <= reps, n * reps <= 3 * 10**5
  • floats are compared with a tolerance of 1e-6; use no randomness other than rng

Goals

  • Compare several estimators of the same quantity by simulation
  • Measure an estimator's bias and its root mean square error
  • See that an unbiased estimator is not automatically the most accurate one
Starting Python…