A factory numbers its tanks in order: 1, 2, 3 and so on. You come across four of them, with serial numbers 4, 10, 15 and 60. How many tanks has the factory built? Lock in your estimate, then check it in a game, against 100,000 simulations and with the explanations.
A factory numbers its tanks in order: 1, 2, 3 and so on. You come across four of them, with serial numbers 4, 10, 15 and 60. The best estimate is 60 + 60/4 − 1 = 74: the largest number plus the average gap between numbers. This is how the Allies counted German tanks in World War II, and the statistics were off by one tank a month where intelligence was off almost sixfold.
This problem came up during World War II. The Western Allies wanted to know how many tanks Germany built each month. Besides conventional intelligence, they tried statistics: they looked at the factory serial numbers on parts of captured tanks.
The factory stamps a number on each tank: the first gets 1, the second 2, and so on up to the last one, N. We do not know N. That is what we want to estimate.
We have come across four tanks. Here are their numbers, sorted:
Numbers start at 1 and have no gaps. Every tank was equally likely to fall into our hands, and we see each number only once. We know nothing else.
What single number N is the best estimate of how many tanks the factory built?
"60, because we never saw a higher number"
Or "twice the average": the four numbers average 22.25, so N ≈ 2 · 22.25 − 1 = 43.5. That is even below 60, though tank number 60 certainly exists. The largest number is almost always below N, so something has to be added to it. The best estimate is 74.
Rounds 2 and 3 compare the methods on thousands of samples, and round 4 explains where the formula comes from.
Serial numbers: 4, 10, 15, 60. Lock in your estimate before reading on.
A breakdown of your estimate will appear here.
The computer has made up a factory with an unknown number of tanks, between 50 and 500. Capture tanks one at a time: each shows a random serial number you have not seen yet. When you are ready, type your estimate. The game then shows the true N and the formula's estimate m + m/k − 1, where m is the largest number and k is the number of tanks.
Tip: with 2–3 tanks it is hard, since even the formula scatters widely. With 8–10 tanks the formula is usually off by just a few percent.
The factory built N = 300 tanks. For each k from 1 to 20 we take k random distinct serial numbers and estimate N three ways: the largest number m, twice the average 2 · x̄ − 1, and the formula m + m/k − 1. Lines show the exact values, dots show the simulation.
The maximum is too low on average: its mean is exactly k(N + 1)/(k + 1). The other two average exactly 300.
Root-mean-square distance from the estimate to 300. For every k ≥ 2 the formula is the most accurate and twice the average the worst. At k = 1 these two coincide.
The distribution of each estimate for k = 4 and N = 300. Bars show the exact distribution, dots show the simulation. The vertical tick marks the true N = 300.
The whole formula rests on one idea: random serial numbers cut the row 1, 2, …, N into gaps that are equal on average.
Four numbers cut the row from 1 to N into five gaps: one before the first number, three between numbers and one after the last. Random numbers have no reason to bunch up on the left or the right, so all five gaps are equal on average. We see four of them; the fifth, above 60, is hidden.
From 1 to 60 there are 60 numbers. We saw four, and the other 56 hide in the four visible gaps: 3 + 5 + 4 + 44 = 56. That is 56/4 = 14 missing numbers per gap on average. As many again hide above 60, so N ≈ 60 + 14 = 74.
In general the average gap is (m − k)/k = m/k − 1. Hence the formula: N ≈ m + m/k − 1. The "−1" appears because the numbers we saw are not part of any gap.
Number N makes it into the sample with chance only k/N. The rest of the time the largest number seen is below N, never above it. So the maximum is systematically too low. For example, if N = 100 and you see 4 tanks, the largest number averages 4 · 101/5 = 80.8.
On average that shortfall is exactly one gap. The formula puts it back.
The average number from 1 to N is (N + 1)/2, so 2 · x̄ − 1 gives exactly N on average. But it depends on every number, and a single number that happens to be small drags it down. Its spread is √((k + 2)/3) times that of the formula: 1.41 times for 4 tanks.
Worse, it can contradict the facts. In our example it gives 43.5, though we saw tank number 60. With N = 300 and 4 tanks this happens in 16.8% of samples.
One number does not say how sure we are. A simple 95% interval runs from m to m · 201/k. For our 4 tanks that is from 60 to 60 · 201/4 ≈ 127. The lower end is hard, because tank 60 exists. The upper end is soft, because a big factory could also produce small numbers by chance.
Where the 20 comes from: the chance that all k numbers fall in the lowest fraction p of the row is about pk. The bound sits where that chance equals 5% = 1/20.
An estimate is called unbiased if it gives exactly N on average. There are many unbiased estimates, twice the average among them. Of all unbiased estimates, m + m/k − 1 has the smallest spread. Statisticians call it the minimum-variance unbiased estimator.
The reason is that all the useful information about N sits in m and k. The other numbers only confirm that the sample is random.
The first line counts samples: for the maximum to be j, the other k − 1 numbers must come from the j − 1 smaller ones. That gives the mean E[m]. Solve the equation for N and plug in the observed m for E[m]. The formula's typical error is about N/k: to be within 10%, you need about 10 tanks.
How the Allies used the idea, what to do when numbering does not start at 1, and how many tanks you need to be sure.
German tanks per month. Figures from the table in Ruggles and Brodie (1947), as given by Wikipedia.
| Month | Serials | Intel | Actual |
|---|---|---|---|
| Jun 1940 | 169 | 1,000 | 122 |
| Jun 1941 | 244 | 1,550 | 271 |
| Aug 1942 | 327 | 1,550 | 342 |
"Serials" is the statisticians' estimate from serial numbers, "Actual" means German production records the Allies obtained after the war.
Conventional intelligence put German production from June 1940 to September 1942 at about 1,400 tanks a month. The statisticians, working from serial numbers, got 246. After the war, records from Albert Speer's ministry showed 245. Intelligence was off almost sixfold, statistics by one tank.
The main source was gearbox numbers, because they ran in two unbroken sequences. Chassis and engine numbers were used too, though they were more complicated. Wheels, which were also numbered in sequence, were analysed separately.
The real work was harder than our puzzle: for instance, the start of the numbering was unknown. The estimate itself appears in the paper only in a footnote: "sample maximum plus average gap".
Sometimes the numbers run from, say, 2001 to 2300, and we do not know the first one either. Then we estimate a gap both below and above. Between the smallest and largest number there are k − 1 gaps holding (max − min) − (k − 1) hidden numbers. The average gap is g = (max − min)/(k − 1) − 1.
We estimate the first number as min − g and the last as max + g. So the total count is:
This estimate also gives exactly N on average (we checked by exact enumeration), but it needs at least two numbers and scatters more: it leans on two edges instead of one.
The interval from m to m · 201/k shrinks fast. With 1 tank the upper end is 20 times m, with 2 it is 4.47 times, with 5 it is 1.82 times, with 10 it is 1.35 times. The formula's typical error is close to N/k.
For comparison: in ordinary polls the error shrinks like 1/√k, so a sample four times larger only halves it. Here a sample four times larger cuts the error almost fourfold. The edge of a numbered row shows up remarkably well.
The interval is derived for sampling with replacement. Without replacement, as here, it is slightly wider than needed and covers N slightly more than 95% of the time. The button checks this for N = 300.
The formula's 74 answers "which rule is right on average". The Bayesian approach asks something else: "which values of N are plausible after seeing these numbers". If every N is treated as equally likely beforehand, the average of the resulting distribution of N for our numbers is 88.5, and the single most likely value is 60.
This is not a contradiction, just different questions. All three numbers, 60, 74 and 88.5, make sense, and all of them are more reliable than a guess by eye.
From the serial numbers of captured tanks, statisticians put German output from June 1940 to September 1942 at 246 tanks a month. Records from Speer's ministry after the war showed 245. Conventional intelligence had said about 1,400.
Analysing the road wheels of just two tanks, 32 on each, gave an estimate of 270 tanks for February 1944. German records after the war showed 276. The wheel numbers revealed how many moulds were in use, and British wheel makers said how many wheels a mould could produce.
The most useful numbers were on gearboxes: they ran in two unbroken sequences. Chassis and engine numbers were used too, but they were harder to work with.
Richard Ruggles and Henry Brodie described the work in "An Empirical Approach to Economic Intelligence in World War II" in the Journal of the American Statistical Association. The paper is mostly practical: the "maximum plus average gap" estimate appears only in a footnote.
The same method was applied to other German equipment. The most successful case was the estimate of V-2 rocket production.
The formula has been used to estimate how many Commodore 64 home computers were built. It gave 12.5 million units, matching the low-end estimates.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.