Counting tanks from serial numbers · Problem 107

s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.

Idea. The largest serial seen is too small on average: the true maximum is at least as large. Compute how much too small, then correct for it.

Step 1: the mean of the maximum. With $k$ tanks drawn, $P (M = m) = (k - 1 m - 1) / (k N)$ . Using $m (k - 1 m - 1) = k (k m)$ and $\sum_{m \leq N} (k m) = (k + 1 N + 1)$ , $E [M] = \frac{k ( k + 1 N + 1 )}{( k N )} = \frac{k ( N + 1 )}{k + 1} .$

Step 2: unbias. Solving $E [M] = \frac{k ( N + 1 )}{k + 1}$ for $N$ gives the unbiased estimator $N^= \frac{k + 1}{k} M - 1 = M + \frac{M}{k} - 1.$

Step 3: the data. With $M = 60$ and $k = 4$ : $N^= 60 + 15 - 1 = 74.$

Intuition. The four serials split $[0, N]$ into gaps, and on average the gap above the maximum is as long as the others: about $\frac{M}{k} - 1$ . So the estimate adds one average gap to the maximum.

The trap. The maximum likelihood estimate is $M = 60$ itself, which can only underestimate $N$ . Among unbiased estimators, $N^$ has the smallest variance.