12 ms·
The German Tank Problem (2010)
- pinaceae 11y agoOk, can someone explain why this method performs so well? Take the highest serial number, add a tenth of it then subtract 1. Presto. What is the underlying logic here?
- sliverstorm 11y agoYou have a key error. Take the highest serial number, add that number divided by the sample size, subtract one. You can then intuitively observe that as sample size increases, the "m/n" component shrinks- our highest serial number is probably going to be a lot closer to the maximum. As sample size decreases all the way to 1, the "m/n" component grows- our largest sampled serial number is probably not very close to the maximum.
- alanh 11y agoTo me, this is the best explanation. Very visual and intuitive. Cheers.
- boxy310 11y agoThe "maximum number" is a statistic both of a population and of a sample drawn from said population. As the sample size goes up, the sample statistic will converge to the population statistic, due to the Law of Large Numbers. Because serial numbers are natural numbers (1, 2, 3, etc.) they are uniformly distributed from 1 through N-hat (the population maximum), and the convergence of the sample statistic to the population statistic will scale inversely to the sample size. Let's take the example in the order it was given in the article: 117, 232, 122, 173, 167, 12, 168, 204, 4, 229 First step we would project the maximum to be 117 + 117 / 1 - 1 = 233. Or, if we drew 1 sample from the population, we would expect the "maximum" to be the average case -- the population mean. We take a minus 1 because there's a degree of freedom lost in using the maximum twice in the same formula (handwaving a bit, but that's a straightforward enough answer for now). With the second case, we have 232 + 232 / 2 - 1, or 347. We would intuitively expect two cases to effectively be distributed evenly across the population, or at 1/3 and 2/3. (The statistics is a bit different due to the MAX operator here, but I won't go into that). With the third case, we have 232 + 232 / 3 -1 = 309. Note that while this statistic is still higher than the actual population statistic, it is still converging due to the additional case that helps us counterbalance the weight of the previous unusually-high sample case we observed. Does that help?
- pinaceae 11y agoso let's say I am being attacked by the first wave of tanks the Germans have fielded. The wave consists of 10 tanks, but from the first batch of tanks produced. 1,5,6,9,12,15,18,20,21,25 how did the allies double check that their sample was not skewed as I described?
- justinsaccount 11y agoYou'd basically be estimating the size of the first batch at that point. Which is fine, until they capture a tank somewhere else that has a number of 230.
- AcerbicZero 11y agoIt should also be noted that there was not one "Tank" SN used, as each component had its own set of serial numbers to be analyzed. In this specific example they used gearbox SN's along with chassis and engine SN to provide the estimate. These statistical estimations were cross-checked with a broad range of other sources, in an attempt to gather data on everything from the number of tanks produced, to the number of factories in use and a variety of supply chain factors.
- mihaifm 11y agodoes this work for consecutive integers that don't start from 1?
- Vraxx 11y agoIt seems that it would trivially work if you knew the number that you start from, you'd just be shifting the uniform distribution (and subtracting whatever number it started from to get the overall estimate). It does seem to be a harder problem if are given that they do not start at 1, but that they are consecutive integers. I imagine you might do a similar sort of statistical estimate on the beginning of the range as well as the end of the range. This introduces more uncertainty, but I see no reason why this wouldn't work
- 11y ago
- justinsaccount 11y agoIt's not "add a tenth": > For example, let’s say 10 tanks were captured It's "add 1/n" where n is the number you collected. Think of this related problem. Numbers are randomly chosen from 1 of 2 ranges. One range is from 0-10, the other is 0-100. The numbers are: 4 3 1 8 5 2 7 Which range were the numbers chosen from? It could be either, but statistically the answer would be from 0-10, since if they were chosen from 0-100 the chances of all of the numbers being lower than 10 is very low. Now, say you didn't know the ranges ahead of time, and the numbers were: 117, 232, 122, 173, 167, 12, 168, 204, 4, 229 Now, the upper bound can't be 100 or 200, since there is a 232. So it is at LEAST 232. Which is more likely, that the upper bound is 256, 500 or 1000 ? Intuitively you can assume that if it was 500+, you would expect at least one number in the 300-500 range. The highest number should be 232 + some amount that is inline with all the other numbers. It could be exactly 232, but the chances that you happened to pick the highest number itself is also low. Basically you are solving this problem: If you were going to select 10 numbers at random from a range of 0 to N, how high should N be so that there is a high probability that the highest number you select is only 232. Since a uniform distribution is assumed, you are basically just adding one more uniformly distributed data point.
- SeriousM 11y agoI had the same question and your answer was pretty clear to me. Thank you!
- JeremyHoward 11y agoIt's actually "add m/n" where n is the number you collected and m is the highest sampled serial number.
- Maultasche 11y agoNote to self: when manufacturing tanks, use UUIDs as identifiers, not sequential integers.
- herge 11y agoThis also matters for user visible ids in applications, like user ids, etc. It's really easy to say your competitor has only 2000 users if you sign up to their service and your id is 1992.
- brianwawok 11y agopks are sequential. If you sign up as 1992 they have 1992 customers.
- jeremysmyth 11y agopks are sequential. If you sign up as 1992 they have 1992 customers. Does not follow. Only follows if: - PKs are sequential - and PKs are non-zero non-negative - and they have not been reset at any point (or the sequence generation otherwise modified) - and all preceding PKs are those of customers (as opposed to test values, invalid PKs due to a sequence number that was generated but the registration did not complete, or customers who have since left the service) If PKs are sequential and natural and the sequence has not been modified, then you know there are no more than 1992 customers. Not exactly 1992.
- dingaling 11y ago> Note to self: when manufacturing tanks, use UUIDs as identifiers, not sequential integers. The post-war Soviet aircraft industry was saddled with ridiculously convoluted Construction Number schemes in order to defeat such analysis. They varied by type, model and factory. Here's an example for one model built in one particular factory: All start with 353 plus three more digits which indicate the sub-type (242=Mi-24V, 246=Mi-24D etc) The seventh digit seems to represent the quarter built while the eighth digit seems to represent the year built. The last five digits as the famous post 1974 random nonsense number. They only abandoned the schemes in the early 1990s.
- bendykstra 11y agoThis reminds me of a popular German graduation prank. Three goats are set loose in a school building. However, before the goats are released, the students paint the numbers 1, 2 and 3 on them to facilitate an orderly recapture procedure.
- justinsaccount 11y agoI think you mean 1,2 and 4.
- AcerbicZero 11y agoYou may have missed the joke...
- justinsaccount 11y agoI May have :-)
- gruez 11y agoExplain? I don't get it
- alanh 11y agoThe joke plays off the one we've all heard before, about pigs being released with numbers implying one is "still at large" — the joke being that the Germans are such industrious and efficient engineer-types that even school pranksters still facilitate an efficient clean-up. I thought it was clever!
- anon4 11y agoNot the worst joke, but it presumes a large amount of domain-specific knowledge on the part of the listener.
- 11y ago
- goodcanadian 11y agoThe moral of the story is to use random serial numbers.
- TearsInTheRain 11y agono you want to just skip numbers randomly to inflate the estimates
- bmmayer1 11y agoThe irony here is that, at the beginning, the Nazi Party started counting members at 500 to make themselves seem bigger than they were.
- Terr_ 11y ago<glances at the UIDs in his system's /etc/passwd>
- a3n 11y agoDepends on why you want to obscure. Works for the context of the article, but what if you want to look non-threatening to your large neighbor, to avoid an attack?
- eggoa 11y agoThus Seal Team "Six".
- yuhong 11y agoReminds me of http://blog.cryptographyengineering.com/2014/10/attack-of-week-unpicking-plaid.html http://blog.cryptographyengineering.com/2014/10/attack-of-we...
- alanh 11y agoCountermeasures* to this problem reminded me of an incident in which the Germans were able to outsmart Allied military intelligence. * https://en.wikipedia.org/wiki/German_tank_problem#Countermeasures https://en.wikipedia.org/wiki/German_tank_problem#Countermea... This is something I read in The American Axis, which discusses how Charles Lindbergh was duped into helping delay American involvement in WWII. The short version: He was taken on a grand, multi-day tour of the Luftwaffe’s large air-force… never the wiser that the planes he saw on airbase after airbase were the same ones, flown in overnight from the last airbase! Naturally the US MI questioned Lindbergh after his travel and grossly overestimated the power and size of the Germain air force, just as they had intended! (As I recall, Lindbergh wasn’t a Nazi sympathizer so much as a dupe; although the other subject of the book – Henry Ford — certainly was. In fact, Ford plants produced the faultiest American war planes, by far, dooming quite a number of American pilots. There’s every reason to think this was intentional.) Update I read this book 8 years ago and my memory isn't 100%. It looks like Lindbergh, per the book, was also a Nazi sympathizer to some degree, although he comes off much more sympathetically than Ford.
- hackuser 11y ago> Ford plants produced the faultiest American war planes, by far, dooming quite a number of American pilots. There’s every reason to think this was intentional. That is quite an assertion to make about someone, even long dead. Could you provide some evidence?
- alanh 11y agoAs I mentioned, I’m pulling this from a book. http://www.amazon.com/The-American-Axis-Charles-Lindbergh/dp/0312290225 http://www.amazon.com/The-American-Axis-Charles-Lindbergh/dp... One reviewer on Amazon says: > This is one of the most carefully researched, extensively footnoted, beautifully written, books on this subject ever published. The sources include entries from Lindbergh's journal, Lindbergh's speeches, FBI files, letters from German archives, Ford company records, and many other primary sources. Every assertion of fact is backed up with unimpeachable documentation. IIRC — by this point it was Ford's son running the plant(s) in question, but Henry Ford himself is not just a known anti-Semite, but quite literally ran and anti-Jewish propaganda paper in Dearborn, MI. It hardly takes a leap to look at the abysmal performance of planes built by Ford and suspect that management there was particularly … lackadaisical in their pursuit of quality.
- UnBe 11y agoAlternative application of the solution. It's an interesting bit of math, with many theoretical and real world applications. http://what-if.xkcd.com/65/ http://what-if.xkcd.com/65/
- mikeash 11y agoI always love this story. I wonder about the potential for error due to bias in the collection process. For example, I would expect older tanks to be more prone to breaking down due to mechanical problems, which might change how likely they are to be captured or destroyed. (I can't tell if that likelihood would go up, because they're more likely to break down in combat, or if it would go down, because they're more likely to be in the shop instead of on the battlefield.) Evidently it didn't affect the accuracy of this technique too badly, but it makes me wonder.
- Peaker 11y agoBut only the single largest serial number, and the number of samples are being used. Not any of the serial numbers seen besides the largest one. That means any such noise as you describe will have no effect. As long as a high-serial number tank is ever destroyed or captured, the method will work. It only takes one.
- mikeash 11y agoYou can get away with only using the count and the maximum because of the assumption of uniformity. Once that assumption goes away, the assumption no longer works. If earlier tanks are much more likely to be captured, then the number of samples will be exaggerated compared to the maximum number seen, so you'll underestimate production. If earlier tanks are much less likely to be captured, then the number of samples will be smaller compared to the maximum, and you'll overestimate.
- wahsd 11y agoAn interesting aspect to this that seems to be overlooked is that the conventional intelligence was probably intentionally fudged in order to garner funds and support and raise anxiety and fear as a means for motivation. You can't overestimate the production of tanks by that much when you are observing the production facilities. You would either have to have been tricked, i.e., knowing that it is being observed the same tanks were "shipped" multiple times or you, for some reason thought there were more factories which you didn't have eyes on. I'm not sure how to judge whether it would have been in the Nazi interest to provide an impression of high productivity or hide the true nature of the numbers. Another interesting aspect to this is that it provides the background for why the US military operates with what would otherwise be seen as abject retardation. There is a strategic value in being aimless, illogical, and confused in your operations for various reasons. One reason is that if you have "random" serial numbers your enemy can't do these kind of calculations.