12 ms·

The German Tank Problem

422 points by eadan 7y ago

coldcode 7y ago
More impressive than using modern tools is that people in WW2 figured this out and modeled it on paper using slide rules.
- dogma1138 7y ago
  Mechanical computers that are designed to solve a single problem aren’t necessarily at a disadvantage, especially when the math isn’t that complex figuring out the variables and all factors was the problem.
- eadan 7y ago
  It's actually fairly straightforward to derive the estimators by hand [0]. It's just a bit tedious to do in a blog post. [0] https://en.wikipedia.org/wiki/Discrete_uniform_distribution#Estimation_of_maximum https://en.wikipedia.org/wiki/Discrete_uniform_distribution#...
- mcenedella 7y ago
  I’m not sure how much higher math you’d really need to answer the question “how many tanks has the other side produced?” if these were the serial numbers of the captured tanks: [689, 341, 386, 741, 982, 414, 845, 241, 180, 447, 880, 21, 583, 993, 812] it’s tough to see an argument for anything other than: a. about 1,000, or b. 1,000ish but there may be a confounding fact pattern we are unaware of....
dooglius 7y ago
This is only the toy version of the actual problems solved by the Allies, which were more nuanced, and involved reasoning about the tank manufacturing pipeline. The write-up [0] doesn't go into the math but makes an interesting read. [0] https://sci-hub.tw/10.2307/2280189 https://sci-hub.tw/10.2307/2280189
- walrus01 7y ago
  I recall something about targeted bombing of ball bearing factories.
  - jabl 7y ago
    There were the infamous raids on the ball bearing factories in Schweinfurt. (At the time the allies didn't have escort fighters with sufficient range, and the bombers suffered heavily.) But AFAIK those targets were selected based on pre-war "traditional" intelligence what the likely bottleneck resources would be, not statistical analysis of captured equipment.
    - sandworm101 7y ago
      Except that the data on the number of tanks, thier increased weight and number of wheels, pointed to a likely increase in the need for bearings. (And all the other wheeled non-tank things too.)
- cortesoft 7y ago
  Yeah, I can't imagine the assumption that tanks captured were "randomly uniformly distributed" is a good one. I can imagine all sorts of reasons that wouldn't be the case.
- Causality1 7y ago
  How accurate did the allies' model turn out to be when compared to the real number?
  - dooglius 7y ago
    Quite well, see pg. 86 for a plot of all predictions
d-- 7y ago
This is also a good (applied, with simple code) example of the use of probabilistic programming. I can't get myself to read full books, but somehow this simple example gave me some intuition and additional pointers to follow.
joker3 7y ago
Given the praise for Bayesian methods here, I'm surprised the author didn't discuss the Bayesian solution. See http://isaacslavitt.com/2015/12/19/german-tank-problem-with-pymc-and-pystan/ http://isaacslavitt.com/2015/12/19/german-tank-problem-with-... for a similar exposition.
- eadan 7y ago
  I implement the Bayesian solution in pymc3 at the end [0]. [0] https://www.eadan.net/blog/german-tank-problem/#probabilistic-programming https://www.eadan.net/blog/german-tank-problem/#probabilisti...
wcoenen 7y ago
See also Doomsday Argument. https://en.wikipedia.org/wiki/Doomsday_argument https://en.wikipedia.org/wiki/Doomsday_argument
- sulam 7y ago
  Take a silly premise, get a silly argument and a really silly conclusion. Confounding question: 1000 years ago, would this argument look any different? Answer: mathematically speaking, it would not. In fact, far more humans have been born than you could have predicted using this method. Conclusion: the argument is flawed.
  - wcoenen 7y ago
    The people living a 1000 years ago indeed could have used the same argument to show that they should be 95% certain to be in the last 95% of all humans to be ever born, and history indeed showed that this was not the case; the dice fell on the other 5% possibility for them and the population increased more than 20x. However, the argument will still give the correct prediction for most humans that try to use it. Just not for the few that were in the special position to be born early in the sequence of all humans. The argument essentially tells you that you have no reason to believe that you are also in that special position.
    - sulam 7y ago
      10's of thousands of years of falling into the 5% group means either the dice are weighted or this isn't a good way to look at the problem.
    - jameshart 7y ago
      You are trying to predict the length of the sequence of all humans, so you have no way to know whether or not you are ‘early in the sequence’. You can’t use the number you are trying to predict as an input to your prediction. The tank problem doesn’t tell you how many tanks Germany will go on to build - it just tells you how many they have already built. ‘Good news! The war is almost over! The chances are these tank serial numbers all fall among the last 95% of the tanks Germany will ever produce!’
nevir 7y ago
FWIW, this is part of why Amazon's product identifiers (ASINs) are obfuscated the way they are
- eadan 7y ago
  People have used a similar strategy to estimate iPhone production [0]. [0] https://www.theguardian.com/technology/blog/2008/oct/08/iphone.apple https://www.theguardian.com/technology/blog/2008/oct/08/ipho...
  - shereadsthenews 7y ago
    There's a zillion things you can estimate this way. A lot of sites use sequential cookies, user IDs, etc. Until about a decade ago UPS tracking numbers were sequential for each shipper which made it trivial to estimate output for online shops. Apple invoice numbers used to be dense and sequential and you only needed the number to retrieve the invoice. The IMEI is actually just about the worst way to have estimated iPhone sales in 2008; at that time you could literally have crawled Apple's website for every invoice whether sold online or in stores.
- dividuum 7y ago
  See also: https://hashids.org/ https://hashids.org/
- dredmorbius 7y ago
  Similarly, Google+ userIDs were assigned as 21-character numeric strings, beginning with '10' or '11', but otherwise appearing to be randomly assigened. A full listing was available through the site's robots.txt sitemaps file, or rather, a listing to the listing of 50,000 user profile sitemap files, with about 44k profiles per file. This worked out to 25 GB of profile listings alone. Rather than download the full set (though I eventually did), I picked an arbitrary file from near the middle of the listing, and ran some spot checks on the profiles, which seemed to be reasonably randomly distributed by age, location, and other characteristics. With as few as 100 profile page downloads, it was clearly evident that active posting to G+ was limited to about 8-11% ofall profiles. The full 50k profile sample, and a third party's independent (and more robustly randomised) 500k profile sample eventually showed this to be 9.7%. (And yes, if I was being more rigorous I could have done much more testing or work, but I was mostly addressing personal curiosity and an online disagreement with someone.) An interesting proof of the power of random sampling. Larger samples do allow for clearer views of rare phenomena -- such as dialing in on the fraction of 1% of G+ users highly active on the site. Or when I later looked at Communities characteristics, the properties of the very largest (about 50 > 1 million members) of the 8 million total. In that case, I eventually got access (also via a third-party) to a comprehensive summary dataset. The userID hashing also made approaches such as exhaustively searching the ID space for user pages nonviable. The search space was trillions pf times larger than the target space.
jackfoxy 7y ago
How ironic that the nation that led the world in the frontiers of maths in the 19th century completely missed the boat in the applied math of signals intelligence in WWII. I'm referring to the tank serial numbers and the lack of care in Enigma codes, except by the Kriegsmarine, but even they eventually lost a code book to the allies, which they apparently considered an impossibility.
- tsss 7y ago
  It certainly didn't help that they killed all the academics and free-thinkers.
  - dmos62 7y ago
    Quote? I'm vague on what went on in Germany in the first half of the century.
    - deleted 7y ago
      [deleted]
    - baobrien 7y ago
      In 1933, the Nazi regime passed a law[1] banning anyone they considered Jewish from holding any civil service job, including positions at universities. A large proportion of German academia was considered Jewish. [1] - https://en.wikipedia.org/wiki/Law_for_the_Restoration_of_the_Professional_Civil_Service https://en.wikipedia.org/wiki/Law_for_the_Restoration_of_the...
      - sadjfkajsdkfj 7y ago
        In addition to this they removed anyone considered a socialist or other political enemy.
    - bbddg 7y ago
      ... is this a joke?
- 7y ago
srean 7y ago
The job interview version: If you are being interviewed for a position by engineers who have their employee ids (serially allocated) on their badge find the number of employees from those ids assuming all engineers are equally likely to be on the panel of 8.
- carlmr 7y ago
  I would guess that the likelihood of older employees should be higher. Although I've never seen a panel of 8 at a job interview.
- HeWhoLurksLate 7y ago
  I read your comment before I read the article, and my head started spinning really hard. Congratulations on your nerd snipe!
- pieterr 7y ago
  42
- chiph 7y ago
  I have looked at my payroll check numbers from contracting firms to see how they're doing as a business. If the interval between check numbers drops in a month, I have a good idea that there aren't as many people working there anymore.
  - feintruled 7y ago
    I worked for a big company and we used to put bug numbers in our change releases. We were told to stop doing this, as some customers would see that their bug would appear to have been given a lower priority when they saw lower numbers coming in first.
- rootw0rm 7y ago
  when i first started a grey-market research chemical company some years ago, i added like 31 or something to each invoice number to make it seem like i did more business.
spectramax 7y ago
Why didn't they use randomized and scrambled serial numbers? Sort of like what Amazon does to their order numbers. I know it can still be cracked but serially numbering military equipment is not very smart. I was setting up a Shopify store the other day and it doesn't allow for a lookup table to be used for order numbers. I don't want competitors to know that I've sold so many X items. Same thing with Squarespace and Square e-commerce stores. It blows my mind that a multi-billion dollar ecom giant has not implemented despite of forum posts and requests from users.
- notinversed 7y ago
  Because they were Germans.
- gumby 7y ago
  First, they probably didn't consider that serial numbers might be an information leak. Second, all calculations were done by hand in those days (and documents that weren't printed in bulk had tp be retyped by hand) so sequential numbers were not only easier to issue but to track (e.g. if you have a production problem you can say "let's check all tanks with S/Ns between A and B" rather than having to maintain a list mapping production dates to serial numbers that might be in a file cabinet somewhere distant from where you are.
- terramex 7y ago
  >Why didn't they use randomized and scrambled serial numbers? Because it happened 80 years ago, when German army (or any other) did not understand statistics as well as they do today. It was a groundbreaking achievement by allies.
  - spectramax 7y ago
    They did know about encryption and developed the Enigma machine. I don't think you need deep statistics knowledge to know that if the enemy captured Serial # 0020, 0120, 0439, 1293 and 1356; they would at least have some hint that the lower bound is 1356 tanks.
mhh__ 7y ago
For anyone else interested in WW2 reverse engineering and design etc., https://www.youtube.com/watch?v=GJCF-Ufapu8 https://www.youtube.com/watch?v=GJCF-Ufapu8 "The secret war" is a huge documentary covering british efforts to counter german electronic warfare and V-weapons.
dang 7y ago
Related from 2016: https://news.ycombinator.com/item?id=13095178 https://news.ycombinator.com/item?id=13095178 2015: https://news.ycombinator.com/item?id=10517882 https://news.ycombinator.com/item?id=10517882 2009: https://news.ycombinator.com/item?id=670065 https://news.ycombinator.com/item?id=670065
squeakynick 7y ago
It depends on how you intend to 'score' the estimate. Are you looking for the answer that is the 'most likely', or one that has the 'lowest least squared error', or maybe one that is 'unbiased' (mean error)? http://datagenetics.com/blog/march22014/index.html http://datagenetics.com/blog/march22014/index.html
tzury 7y ago
More about Frequentist and Bayesian analysis can be found here: https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem Matter of fact... According to conventional Allied intelligence estimates, the Germans were producing around 1,400 tanks a month between June 1940 and September 1942. Applying the formula below to the serial numbers of captured tanks, the number was calculated to be 246 a month. After the war, captured German production figures from the ministry of Albert Speer showed the actual number to be 245.
- debbiedowner 7y ago
  I was actually surprised that MVUEs and the fellow point estimators are called frequentist (though it makes sense). In school we always referred to them as non-Bayesian, at the same time frequentist always seemed like a dirty word to us students so maybe that's why
laGrenouille 7y ago
Interesting article, though I think it incorrectly leaves the reader thinking that there is some interesting informating hidden in the average spacing of the numbers. In fact, all you need to know is that maximum observation and the number of observations. Once you simplify the average spacing goes away. If M is the maximum serial number of N is the total number of observations, using the formula in the post: M + (avg. spacing) = M + M / N - 1 = (N + 1) / N * M To me that gives a more clear picture of what the unbiased estimator is doing: inflate the maximum value by a factor that limits towards one as the sample size grows.
- ptero 7y ago
  To be the devils advocate: what you say is true if you know the distribution. If spacing looks weird (e.g. clustered) it might indicate that the number is, for example a pairing of model and serial numbers, etc.
  - popotamonga 7y ago
    Distribution of manufacturing date or distribution of rate of tank capture? Or does it make a difference?
- comicjk 7y ago
  If you just assume that the sample mean = the population mean, then you get the right answer, at least for this example. I don't see why the article fools around with the maximum at all - isn't the maximum a much more noisy statistic than the mean?
  - skosch 7y ago
    The range matters – had they found 10 serial numbers between 100000 and 101000, would the mean still be a meaningful estimate of the production rate? In this case, the author just tacitly assumes the minimum to be zero.
matchagaucho 7y ago
Moral of the story: Don't auto-increment serial numbers :-)
- mehta_rohan 7y ago
  hahah
kevingrahl 7y ago
Since no one else commented on that yet; I just wanted to say that I like the simple layout OP is using. Not much clutter & straight to the point. Loads fast and it’s under 630KB. Could certainly be improved but it’s nice not having to load >25MB just to read an article.
jaimex2 7y ago
Was there only one tank factory?
- jandrese 7y ago
  No but each tank also had a manufacturer code, so this technique still worked.
mruts 7y ago
Seeing that it's a uniform distribution, let's start out with assuming our sample mean (the average serial number we find) has the same distribution as the true mean (the actual number of tanks in existence). If this is true, then: 2 x mean should be an unbiased estimator of the true mean. But because we are probably under sampling the extremes, we could use the Bessel correction: 1/(n-1) x summation_{i=1}^n(sample_i) I would guess this comes out to a better estimation than what the article says. Bessel's correction might be a bit of overkill, since it's intended to work with normal distributions. But I still suspect it comes out to a better estimation that what the blog post says.
- comicjk 7y ago
  I thought the same, and tried it. The mean sample mean after 10 million runs is 500.47, which is very close to the true mean, 500.5. Bessel's correction is not correct here - it's effectively multiplying by n/(n-1), so your estimate would be 536. Bessel's correction is made for estimating true variance using a sample, not for estimating true mean.
  - mruts 7y ago
    Yes of course, the mean is the first moment and a Bessel correction would be inappropriate. Now I feel stupid. The mean calculated by sum(p_t x_i) or 1/n sum(x_i) is already the best linear unbiased estimate. Maybe we can't get better than twice the mean?
- nestorD 7y ago
  What if you get into the war at a later point ? Most tank with a small serial number will have been destroyed (tanks tend to have a short life) and, using the mean instead of the maximum, you will get a seriously biaised result. You could adjust for such problems but it seems much easier to use the maximum.
debbiedowner 7y ago
Nice write up. Little bit of a funny though: Note how num_tanks ~ Unif(max(captured),2000) was defined, so you already have p[ parameter | data ]. Isn't this already a posterior? I get however how if you had the r.v.s num_tanks ~ Unif(M,2000), observed | num_tanks ~ Unif(1,num_tanks), M some constant, that you could find a posterior distribution num_tanks | vector<observed> by first finding the joint via E[ 1[num_tanks < t]P[observed | num_tanks] ]
salty_biscuits 7y ago
Why call it probabilistic programming? It is bayesian inference with mcmc (or am I missing something).
ngneer 7y ago
I remember studying this problem in the context of anonymity a few years back, defining immeasurability as the property whereby an adversary cannot distinguish between different node counts, for example. The tank problem is related to mark recapture techniques for animal population size estimation. Shameless plug, http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2011/MSC/MSC-2011-06.pdf http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2...
RickJWagner 7y ago
"the Germans, being Germans, had numbered their parts in the order they rolled off the production line" Probably in today's world this is racist or nationalist or something. But (as someone of German descent) I have to admit it's funny.
Nomentatus 7y ago
This all seems to assume the tank serial numbers would be captured at one moment in time ("captured 15 of these tanks uniformly at random.") But in fact the tank shells dribble in over time which biases the gap, the gaps at the highest numbers are going to be greater. Earlier tanks have had many more chances to be destroyed or captured. So using average gap is clearly not going to give the best estimate. If you restrict yourself to tanks from the latest large battle, that will cancel out the dribble effect though.
slyu 7y ago
I recommend Think Bayes by Allen Downey if you want to study more. It's a free book available online. http://www.greenteapress.com/thinkbayes/thinkbayes.pdf http://www.greenteapress.com/thinkbayes/thinkbayes.pdf
ngcc_hk 7y ago
Very interesting. Especially the three links and in particular https://github.com/CamDavidsonPilon/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers https://github.com/CamDavidsonPilon/Probabilistic-Programmin...

422 points by eadan 7y ago

More impressive than using modern tools is that people in WW2 figured this out and modeled it on paper using slide rules.

dogma1138 7y ago
Mechanical computers that are designed to solve a single problem aren’t necessarily at a disadvantage, especially when the math isn’t that complex figuring out the variables and all factors was the problem.
eadan 7y ago
It's actually fairly straightforward to derive the estimators by hand [0]. It's just a bit tedious to do in a blog post. [0] https://en.wikipedia.org/wiki/Discrete_uniform_distribution#Estimation_of_maximum https://en.wikipedia.org/wiki/Discrete_uniform_distribution#...
mcenedella 7y ago
I’m not sure how much higher math you’d really need to answer the question “how many tanks has the other side produced?” if these were the serial numbers of the captured tanks: [689, 341, 386, 741, 982, 414, 845, 241, 180, 447, 880, 21, 583, 993, 812] it’s tough to see an argument for anything other than: a. about 1,000, or b. 1,000ish but there may be a confounding fact pattern we are unaware of....

dooglius 7y ago

This is only the toy version of the actual problems solved by the Allies, which were more nuanced, and involved reasoning about the tank manufacturing pipeline. The write-up [0] doesn't go into the math but makes an interesting read. [0] https://sci-hub.tw/10.2307/2280189 https://sci-hub.tw/10.2307/2280189

walrus01 7y ago
I recall something about targeted bombing of ball bearing factories.
- jabl 7y ago
  There were the infamous raids on the ball bearing factories in Schweinfurt. (At the time the allies didn't have escort fighters with sufficient range, and the bombers suffered heavily.) But AFAIK those targets were selected based on pre-war "traditional" intelligence what the likely bottleneck resources would be, not statistical analysis of captured equipment.
  - sandworm101 7y ago
    Except that the data on the number of tanks, thier increased weight and number of wheels, pointed to a likely increase in the need for bearings. (And all the other wheeled non-tank things too.)
cortesoft 7y ago
Yeah, I can't imagine the assumption that tanks captured were "randomly uniformly distributed" is a good one. I can imagine all sorts of reasons that wouldn't be the case.
Causality1 7y ago
How accurate did the allies' model turn out to be when compared to the real number?
- dooglius 7y ago
  Quite well, see pg. 86 for a plot of all predictions

d-- 7y ago

This is also a good (applied, with simple code) example of the use of probabilistic programming. I can't get myself to read full books, but somehow this simple example gave me some intuition and additional pointers to follow.

joker3 7y ago

Given the praise for Bayesian methods here, I'm surprised the author didn't discuss the Bayesian solution. See http://isaacslavitt.com/2015/12/19/german-tank-problem-with-pymc-and-pystan/ http://isaacslavitt.com/2015/12/19/german-tank-problem-with-... for a similar exposition.

eadan 7y ago
I implement the Bayesian solution in pymc3 at the end [0]. [0] https://www.eadan.net/blog/german-tank-problem/#probabilistic-programming https://www.eadan.net/blog/german-tank-problem/#probabilisti...

wcoenen 7y ago

See also Doomsday Argument. https://en.wikipedia.org/wiki/Doomsday_argument https://en.wikipedia.org/wiki/Doomsday_argument

sulam 7y ago
Take a silly premise, get a silly argument and a really silly conclusion. Confounding question: 1000 years ago, would this argument look any different? Answer: mathematically speaking, it would not. In fact, far more humans have been born than you could have predicted using this method. Conclusion: the argument is flawed.
- wcoenen 7y ago
  The people living a 1000 years ago indeed could have used the same argument to show that they should be 95% certain to be in the last 95% of all humans to be ever born, and history indeed showed that this was not the case; the dice fell on the other 5% possibility for them and the population increased more than 20x. However, the argument will still give the correct prediction for most humans that try to use it. Just not for the few that were in the special position to be born early in the sequence of all humans. The argument essentially tells you that you have no reason to believe that you are also in that special position.
  - sulam 7y ago
    10's of thousands of years of falling into the 5% group means either the dice are weighted or this isn't a good way to look at the problem.
  - jameshart 7y ago
    You are trying to predict the length of the sequence of all humans, so you have no way to know whether or not you are ‘early in the sequence’. You can’t use the number you are trying to predict as an input to your prediction. The tank problem doesn’t tell you how many tanks Germany will go on to build - it just tells you how many they have already built. ‘Good news! The war is almost over! The chances are these tank serial numbers all fall among the last 95% of the tanks Germany will ever produce!’

nevir 7y ago

FWIW, this is part of why Amazon's product identifiers (ASINs) are obfuscated the way they are

eadan 7y ago
People have used a similar strategy to estimate iPhone production [0]. [0] https://www.theguardian.com/technology/blog/2008/oct/08/iphone.apple https://www.theguardian.com/technology/blog/2008/oct/08/ipho...
- shereadsthenews 7y ago
  There's a zillion things you can estimate this way. A lot of sites use sequential cookies, user IDs, etc. Until about a decade ago UPS tracking numbers were sequential for each shipper which made it trivial to estimate output for online shops. Apple invoice numbers used to be dense and sequential and you only needed the number to retrieve the invoice. The IMEI is actually just about the worst way to have estimated iPhone sales in 2008; at that time you could literally have crawled Apple's website for every invoice whether sold online or in stores.
dividuum 7y ago
See also: https://hashids.org/ https://hashids.org/
dredmorbius 7y ago
Similarly, Google+ userIDs were assigned as 21-character numeric strings, beginning with '10' or '11', but otherwise appearing to be randomly assigened. A full listing was available through the site's robots.txt sitemaps file, or rather, a listing to the listing of 50,000 user profile sitemap files, with about 44k profiles per file. This worked out to 25 GB of profile listings alone. Rather than download the full set (though I eventually did), I picked an arbitrary file from near the middle of the listing, and ran some spot checks on the profiles, which seemed to be reasonably randomly distributed by age, location, and other characteristics. With as few as 100 profile page downloads, it was clearly evident that active posting to G+ was limited to about 8-11% ofall profiles. The full 50k profile sample, and a third party's independent (and more robustly randomised) 500k profile sample eventually showed this to be 9.7%. (And yes, if I was being more rigorous I could have done much more testing or work, but I was mostly addressing personal curiosity and an online disagreement with someone.) An interesting proof of the power of random sampling. Larger samples do allow for clearer views of rare phenomena -- such as dialing in on the fraction of 1% of G+ users highly active on the site. Or when I later looked at Communities characteristics, the properties of the very largest (about 50 > 1 million members) of the 8 million total. In that case, I eventually got access (also via a third-party) to a comprehensive summary dataset. The userID hashing also made approaches such as exhaustively searching the ID space for user pages nonviable. The search space was trillions pf times larger than the target space.

jackfoxy 7y ago

How ironic that the nation that led the world in the frontiers of maths in the 19th century completely missed the boat in the applied math of signals intelligence in WWII. I'm referring to the tank serial numbers and the lack of care in Enigma codes, except by the Kriegsmarine, but even they eventually lost a code book to the allies, which they apparently considered an impossibility.

tsss 7y ago
It certainly didn't help that they killed all the academics and free-thinkers.
- dmos62 7y ago
  Quote? I'm vague on what went on in Germany in the first half of the century.
  - deleted 7y ago
    [deleted]
  - baobrien 7y ago
    In 1933, the Nazi regime passed a law[1] banning anyone they considered Jewish from holding any civil service job, including positions at universities. A large proportion of German academia was considered Jewish. [1] - https://en.wikipedia.org/wiki/Law_for_the_Restoration_of_the_Professional_Civil_Service https://en.wikipedia.org/wiki/Law_for_the_Restoration_of_the...
    - sadjfkajsdkfj 7y ago
      In addition to this they removed anyone considered a socialist or other political enemy.
  - bbddg 7y ago
    ... is this a joke?
7y ago

srean 7y ago

The job interview version: If you are being interviewed for a position by engineers who have their employee ids (serially allocated) on their badge find the number of employees from those ids assuming all engineers are equally likely to be on the panel of 8.

carlmr 7y ago
I would guess that the likelihood of older employees should be higher. Although I've never seen a panel of 8 at a job interview.
HeWhoLurksLate 7y ago
I read your comment before I read the article, and my head started spinning really hard. Congratulations on your nerd snipe!
pieterr 7y ago
42
chiph 7y ago
I have looked at my payroll check numbers from contracting firms to see how they're doing as a business. If the interval between check numbers drops in a month, I have a good idea that there aren't as many people working there anymore.
- feintruled 7y ago
  I worked for a big company and we used to put bug numbers in our change releases. We were told to stop doing this, as some customers would see that their bug would appear to have been given a lower priority when they saw lower numbers coming in first.
rootw0rm 7y ago
when i first started a grey-market research chemical company some years ago, i added like 31 or something to each invoice number to make it seem like i did more business.

spectramax 7y ago

Why didn't they use randomized and scrambled serial numbers? Sort of like what Amazon does to their order numbers. I know it can still be cracked but serially numbering military equipment is not very smart. I was setting up a Shopify store the other day and it doesn't allow for a lookup table to be used for order numbers. I don't want competitors to know that I've sold so many X items. Same thing with Squarespace and Square e-commerce stores. It blows my mind that a multi-billion dollar ecom giant has not implemented despite of forum posts and requests from users.

notinversed 7y ago
Because they were Germans.
gumby 7y ago
First, they probably didn't consider that serial numbers might be an information leak. Second, all calculations were done by hand in those days (and documents that weren't printed in bulk had tp be retyped by hand) so sequential numbers were not only easier to issue but to track (e.g. if you have a production problem you can say "let's check all tanks with S/Ns between A and B" rather than having to maintain a list mapping production dates to serial numbers that might be in a file cabinet somewhere distant from where you are.
terramex 7y ago
>Why didn't they use randomized and scrambled serial numbers? Because it happened 80 years ago, when German army (or any other) did not understand statistics as well as they do today. It was a groundbreaking achievement by allies.
- spectramax 7y ago
  They did know about encryption and developed the Enigma machine. I don't think you need deep statistics knowledge to know that if the enemy captured Serial # 0020, 0120, 0439, 1293 and 1356; they would at least have some hint that the lower bound is 1356 tanks.

mhh__ 7y ago

For anyone else interested in WW2 reverse engineering and design etc., https://www.youtube.com/watch?v=GJCF-Ufapu8 https://www.youtube.com/watch?v=GJCF-Ufapu8 "The secret war" is a huge documentary covering british efforts to counter german electronic warfare and V-weapons.

dang 7y ago

Related from 2016: https://news.ycombinator.com/item?id=13095178 https://news.ycombinator.com/item?id=13095178 2015: https://news.ycombinator.com/item?id=10517882 https://news.ycombinator.com/item?id=10517882 2009: https://news.ycombinator.com/item?id=670065 https://news.ycombinator.com/item?id=670065

squeakynick 7y ago

It depends on how you intend to 'score' the estimate. Are you looking for the answer that is the 'most likely', or one that has the 'lowest least squared error', or maybe one that is 'unbiased' (mean error)? http://datagenetics.com/blog/march22014/index.html http://datagenetics.com/blog/march22014/index.html

tzury 7y ago

More about Frequentist and Bayesian analysis can be found here: https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem Matter of fact... According to conventional Allied intelligence estimates, the Germans were producing around 1,400 tanks a month between June 1940 and September 1942. Applying the formula below to the serial numbers of captured tanks, the number was calculated to be 246 a month. After the war, captured German production figures from the ministry of Albert Speer showed the actual number to be 245.

debbiedowner 7y ago
I was actually surprised that MVUEs and the fellow point estimators are called frequentist (though it makes sense). In school we always referred to them as non-Bayesian, at the same time frequentist always seemed like a dirty word to us students so maybe that's why

laGrenouille 7y ago

Interesting article, though I think it incorrectly leaves the reader thinking that there is some interesting informating hidden in the average spacing of the numbers. In fact, all you need to know is that maximum observation and the number of observations. Once you simplify the average spacing goes away. If M is the maximum serial number of N is the total number of observations, using the formula in the post: M + (avg. spacing) = M + M / N - 1 = (N + 1) / N * M To me that gives a more clear picture of what the unbiased estimator is doing: inflate the maximum value by a factor that limits towards one as the sample size grows.

ptero 7y ago
To be the devils advocate: what you say is true if you know the distribution. If spacing looks weird (e.g. clustered) it might indicate that the number is, for example a pairing of model and serial numbers, etc.
- popotamonga 7y ago
  Distribution of manufacturing date or distribution of rate of tank capture? Or does it make a difference?
comicjk 7y ago
If you just assume that the sample mean = the population mean, then you get the right answer, at least for this example. I don't see why the article fools around with the maximum at all - isn't the maximum a much more noisy statistic than the mean?
- skosch 7y ago
  The range matters – had they found 10 serial numbers between 100000 and 101000, would the mean still be a meaningful estimate of the production rate? In this case, the author just tacitly assumes the minimum to be zero.

matchagaucho 7y ago

Moral of the story: Don't auto-increment serial numbers :-)

mehta_rohan 7y ago
hahah

kevingrahl 7y ago

Since no one else commented on that yet; I just wanted to say that I like the simple layout OP is using. Not much clutter & straight to the point. Loads fast and it’s under 630KB. Could certainly be improved but it’s nice not having to load >25MB just to read an article.

jaimex2 7y ago

Was there only one tank factory?

jandrese 7y ago
No but each tank also had a manufacturer code, so this technique still worked.

mruts 7y ago

Seeing that it's a uniform distribution, let's start out with assuming our sample mean (the average serial number we find) has the same distribution as the true mean (the actual number of tanks in existence). If this is true, then: 2 x mean should be an unbiased estimator of the true mean. But because we are probably under sampling the extremes, we could use the Bessel correction: 1/(n-1) x summation_{i=1}^n(sample_i) I would guess this comes out to a better estimation than what the article says. Bessel's correction might be a bit of overkill, since it's intended to work with normal distributions. But I still suspect it comes out to a better estimation that what the blog post says.

comicjk 7y ago
I thought the same, and tried it. The mean sample mean after 10 million runs is 500.47, which is very close to the true mean, 500.5. Bessel's correction is not correct here - it's effectively multiplying by n/(n-1), so your estimate would be 536. Bessel's correction is made for estimating true variance using a sample, not for estimating true mean.
- mruts 7y ago
  Yes of course, the mean is the first moment and a Bessel correction would be inappropriate. Now I feel stupid. The mean calculated by sum(p_t x_i) or 1/n sum(x_i) is already the best linear unbiased estimate. Maybe we can't get better than twice the mean?
nestorD 7y ago
What if you get into the war at a later point ? Most tank with a small serial number will have been destroyed (tanks tend to have a short life) and, using the mean instead of the maximum, you will get a seriously biaised result. You could adjust for such problems but it seems much easier to use the maximum.

debbiedowner 7y ago

Nice write up. Little bit of a funny though: Note how num_tanks ~ Unif(max(captured),2000) was defined, so you already have p[ parameter | data ]. Isn't this already a posterior? I get however how if you had the r.v.s num_tanks ~ Unif(M,2000), observed | num_tanks ~ Unif(1,num_tanks), M some constant, that you could find a posterior distribution num_tanks | vector<observed> by first finding the joint via E[ 1[num_tanks < t]P[observed | num_tanks] ]

salty_biscuits 7y ago

Why call it probabilistic programming? It is bayesian inference with mcmc (or am I missing something).

ngneer 7y ago

I remember studying this problem in the context of anonymity a few years back, defining immeasurability as the property whereby an adversary cannot distinguish between different node counts, for example. The tank problem is related to mark recapture techniques for animal population size estimation. Shameless plug, http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2011/MSC/MSC-2011-06.pdf http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2...

RickJWagner 7y ago

"the Germans, being Germans, had numbered their parts in the order they rolled off the production line" Probably in today's world this is racist or nationalist or something. But (as someone of German descent) I have to admit it's funny.

Nomentatus 7y ago

This all seems to assume the tank serial numbers would be captured at one moment in time ("captured 15 of these tanks uniformly at random.") But in fact the tank shells dribble in over time which biases the gap, the gaps at the highest numbers are going to be greater. Earlier tanks have had many more chances to be destroyed or captured. So using average gap is clearly not going to give the best estimate. If you restrict yourself to tanks from the latest large battle, that will cancel out the dribble effect though.

slyu 7y ago

I recommend Think Bayes by Allen Downey if you want to study more. It's a free book available online. http://www.greenteapress.com/thinkbayes/thinkbayes.pdf http://www.greenteapress.com/thinkbayes/thinkbayes.pdf

ngcc_hk 7y ago

Very interesting. Especially the three links and in particular https://github.com/CamDavidsonPilon/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers https://github.com/CamDavidsonPilon/Probabilistic-Programmin...