9 ms·

German Tank Problem

64 points by bluesmoon 16y ago

brg 16y ago
Is there a simple derivation or justification for this estimator?
- MarkBook 16y ago
  I think I get part of it n/n+1 means that as n gets bigger it becomes ever more likely that s is close to the real maximum. But I have no idea why 1 is added to s
  - MarkBook 16y ago
    continuing my foolish musings I would have thought originally that getting the mean of the sample and multiplying by 2 would have been a good estimate. But one problem with that is that there is no possibility of the maximum being lower than anything in the sample so there has to be an allowance for uncertainty upwards. Is that the reason for adding 1 to s?
    - mturmon 16y ago
      You can show that the max is a comprehensively better estimator than twice the mean. This is one of the rare cases where you can outperform the mean by a large margin. The standard deviation of the mean-based estimator, which measures its accuracy, will go down like 1/sqrt(n) where n is the number of samples in the finite set. This is the rate standardly seen in lots of estimation problems. But the standard deviation of the max-based estimator will go down like 1/n, a much faster rate. That's one manifestation of the "weirdness" of this problem. It means you can get surprisingly good estimates of the number of tanks considering the small numbers of observations.
      - MarkBook 16y ago
        Thanks, I think I get it on a superficial level. The British seemed to have some pretty useful statisticians during WWII. See this also : http://www.dur.ac.uk/stat.web/bomb.htm http://www.dur.ac.uk/stat.web/bomb.htm EDIT : So there's about a fifty fifty chance that the second observation will be bigger than the first. After the second observation the range of possible future observations will be divided into 3 zones, 1 below the lowest of the previous 2 observations 1 above the higher and 1 between the two previous observations, so there is now only a 1/3 possibility of the next observation being above the higher of the 2 previous observations. Next time that drops to 1/4 then 1/5, so that's how the standard deviation decreases proportional to 1/n
        mturmon 16y ago
        I like that explanation.
- xel02 16y ago
  There is, had to learn it in a probability class. http://en.wikipedia.org/wiki/German_tank_problem http://en.wikipedia.org/wiki/German_tank_problem
  - ckuehne 16y ago
    According to Wikipedia the estimator is (n+1)/ns-1 not (n+1)/n(s+1) as the author stated.
  - brg 16y ago
    To sum up the derivation for those looking for crib notes; model the problem as choosing k items u.a.r. from [1..N]. Compute P(max = i), and from this compute the expectation of the max. After simpliciation this is given in terms of k and N, and hence we have an estimator for N in terms of k and max.
- mturmon 16y ago
  This is a classic question where some of the usual assumptions of the method conventionally applied, the Maximum Likelihood (ML) principle, break down. There's a good explanation at: http://en.wikipedia.org/wiki/German_tank_problem#Example http://en.wikipedia.org/wiki/German_tank_problem#Example In a nut, the ML estimator of N, the number of tanks produced, is the max of the serial numbers. But this is biased, in particular, it tends to systematically underestimate N. (Because you're unlikely to actually observe the top serial number in your random sample.) So you can add a correction term which is, intuitively, the expected gap between the serial numbers in the finite sample. The correction makes up for the fencepost effect. It goes to zero as the number of samples increases.
lmkg 16y ago
Key quote: > The statisticians believed that the Germans, being Germans, had logically numbered their tanks in the order in which they were produced. The moral of the story is, never do anything that could give your opponent information, unless you're controlling what information they receive. It would be better to produce tanks with pseudo-random serial numbers, up to a maximum of whatever you want your enemy to think your production capacity is[1]. Brings back memories of reading the Cryptonomicon. [1] My gut tells me the expected estimate is likely to be slightly different than your max value for small values of n. Bonus points for confirming or denying.
- run4yourlives 16y ago
  Sometimes though, information denial is more of a pain in the ass than a gain. For all the intelligence directed at Nazi Germany during WWII, the outcome of the war was decided by a few Russian snowflakes, really.
  - InclinedPlane 16y ago
    BS. Sure, the Russian winters harmed the German war machine greatly, but it's not as though that alone was the sole determiner of the outcome of the war. Even had the winters been milder the Russian forces would still have taken a heavy toll on the Germans and were nearly guaranteed to win that conflict by benefit of logistics alone. Moreover, even had Russia fallen to Germany the American/UK military might by 1945 was far too great even for a Germany backed by the natural resources of Russia to withstand. By mid-1945 the allies had put together a machine in the Pacific theater in the form of bombers, submarines, and combined forces capable of razing cities, ravaging shipping, and conquering territory at an incredible rate. It would have been perfectly possible to direct some or all of that apparatus at an unbowed Nazi regime in mid to late 1945 through 1946 and visit utter devastation on Germany until it was incapable of fighting any war. And this is sans nuclear weaponry, factoring those into the equation merely accelerates the end of this hypothetical war. Such a war would have been even more brutal than WWII was, but the outcome would not change.
    - 16y ago
leelin 16y ago
There are a few "flaws" to this solution actually, although the flaws are in assumptions + bayesian vs. frequentist philosophy differences. The solution mentioned in the link solves a different problem: You get a sample of K ints uniform randomly from 1 to N, where N is unknown. Based on your sample, what is your best estimate of N, so that if we repeatedly continue to give you independent random samples, the average answer your algorithm gives will be the correct answer, and provides the minimum variance compared to other algorithms? However, if we can put an upper bound on the number of tanks that could possibly exist, say definitely no more than 100 million tanks, and if we believe it is slightly more likely that older tanks will be on the front lines than newer tanks, or any other prior knowledge, then the proposed solution will be more incorrect. One of my former co-workers proposed computing a posterior distribution for estimates of N based on equally-weighted priors for N = max-observation to N = maximum cap (100 million tanks). Then the estimate is the expected value of the posterior distribution.
- jules 16y ago
  Is there for every commonly used frequentist estimation method a bayesian prior that gives the same answer?
  - mturmon 16y ago
    For every commonly used frequentist estimator, there is an uncountable infinity of intractable Bayesian estimators.
    - aristus 16y ago
      ...probably.
bpick 16y ago
I recall reading that the same kind of thing used to happen with standing field armies, (think Napoleon sized blocks) where you could almost instantly assess an opponents forces based on simply recognizing divisions, regiments, etc. My guess is Napoleon-era field marshals did a cost-benefit analysis and decided that managing their forces simplistically (i.e. no irregular sized units) outweighed whatever inconvenience enemy intelligence posed. Relating this to the OP my guess is the Germans made a mistake and overlooked the serial numbers, rather than simply not caring.
hngryhppos 16y ago
I want to comment on how pretentious that website title is ("three standard deviations to the left"). I took that to imply the author (or his intended audience) is three standard deviations above average (intelligence?). Anyway, he says he am IB teacher... not surprised, this attitude of intellectual superiority is an IB hallmark.
- Devilboy 16y ago
  Wouldn't that be 3 SDs to the RIGHT instead?
  - thefool 16y ago
    Yeah I took it as meaning a website for the brain-dead, which was much wittier than pretentious. Unless he meant right and said left, which is even funnier.
- cema 16y ago
  Could be the political left, you know.
deleted 16y ago
[deleted]
alex_h 16y ago
I guess one might also want to take into account the probability of capturing 5 tanks with all odd serial numbers (3.125%) vs the probability that the Germans had numbered their tanks in increments of 2
JadeNB 16y ago
As someone who spends a lot of time working with future high-school math teachers, I'd be really interested in reading some more by this author; but I can't find any contact information, and the blog moved to an 'invitation-only' Blogspot account in 2007. Does anyone know how to get in touch with the author to request an invitation?

German Tank Problem

64 points by bluesmoon 16y ago

brg 16y ago

Is there a simple derivation or justification for this estimator?

MarkBook 16y ago
I think I get part of it n/n+1 means that as n gets bigger it becomes ever more likely that s is close to the real maximum. But I have no idea why 1 is added to s
- MarkBook 16y ago
  continuing my foolish musings I would have thought originally that getting the mean of the sample and multiplying by 2 would have been a good estimate. But one problem with that is that there is no possibility of the maximum being lower than anything in the sample so there has to be an allowance for uncertainty upwards. Is that the reason for adding 1 to s?
  - mturmon 16y ago
    You can show that the max is a comprehensively better estimator than twice the mean. This is one of the rare cases where you can outperform the mean by a large margin. The standard deviation of the mean-based estimator, which measures its accuracy, will go down like 1/sqrt(n) where n is the number of samples in the finite set. This is the rate standardly seen in lots of estimation problems. But the standard deviation of the max-based estimator will go down like 1/n, a much faster rate. That's one manifestation of the "weirdness" of this problem. It means you can get surprisingly good estimates of the number of tanks considering the small numbers of observations.
    - MarkBook 16y ago
      Thanks, I think I get it on a superficial level. The British seemed to have some pretty useful statisticians during WWII. See this also : http://www.dur.ac.uk/stat.web/bomb.htm http://www.dur.ac.uk/stat.web/bomb.htm EDIT : So there's about a fifty fifty chance that the second observation will be bigger than the first. After the second observation the range of possible future observations will be divided into 3 zones, 1 below the lowest of the previous 2 observations 1 above the higher and 1 between the two previous observations, so there is now only a 1/3 possibility of the next observation being above the higher of the 2 previous observations. Next time that drops to 1/4 then 1/5, so that's how the standard deviation decreases proportional to 1/n
      - mturmon 16y ago
        I like that explanation.
xel02 16y ago
There is, had to learn it in a probability class. http://en.wikipedia.org/wiki/German_tank_problem http://en.wikipedia.org/wiki/German_tank_problem
- ckuehne 16y ago
  According to Wikipedia the estimator is (n+1)/ns-1 not (n+1)/n(s+1) as the author stated.
- brg 16y ago
  To sum up the derivation for those looking for crib notes; model the problem as choosing k items u.a.r. from [1..N]. Compute P(max = i), and from this compute the expectation of the max. After simpliciation this is given in terms of k and N, and hence we have an estimator for N in terms of k and max.
mturmon 16y ago
This is a classic question where some of the usual assumptions of the method conventionally applied, the Maximum Likelihood (ML) principle, break down. There's a good explanation at: http://en.wikipedia.org/wiki/German_tank_problem#Example http://en.wikipedia.org/wiki/German_tank_problem#Example In a nut, the ML estimator of N, the number of tanks produced, is the max of the serial numbers. But this is biased, in particular, it tends to systematically underestimate N. (Because you're unlikely to actually observe the top serial number in your random sample.) So you can add a correction term which is, intuitively, the expected gap between the serial numbers in the finite sample. The correction makes up for the fencepost effect. It goes to zero as the number of samples increases.

lmkg 16y ago

Key quote: > The statisticians believed that the Germans, being Germans, had logically numbered their tanks in the order in which they were produced. The moral of the story is, never do anything that could give your opponent information, unless you're controlling what information they receive. It would be better to produce tanks with pseudo-random serial numbers, up to a maximum of whatever you want your enemy to think your production capacity is[1]. Brings back memories of reading the Cryptonomicon. [1] My gut tells me the expected estimate is likely to be slightly different than your max value for small values of n. Bonus points for confirming or denying.

run4yourlives 16y ago
Sometimes though, information denial is more of a pain in the ass than a gain. For all the intelligence directed at Nazi Germany during WWII, the outcome of the war was decided by a few Russian snowflakes, really.
- InclinedPlane 16y ago
  BS. Sure, the Russian winters harmed the German war machine greatly, but it's not as though that alone was the sole determiner of the outcome of the war. Even had the winters been milder the Russian forces would still have taken a heavy toll on the Germans and were nearly guaranteed to win that conflict by benefit of logistics alone. Moreover, even had Russia fallen to Germany the American/UK military might by 1945 was far too great even for a Germany backed by the natural resources of Russia to withstand. By mid-1945 the allies had put together a machine in the Pacific theater in the form of bombers, submarines, and combined forces capable of razing cities, ravaging shipping, and conquering territory at an incredible rate. It would have been perfectly possible to direct some or all of that apparatus at an unbowed Nazi regime in mid to late 1945 through 1946 and visit utter devastation on Germany until it was incapable of fighting any war. And this is sans nuclear weaponry, factoring those into the equation merely accelerates the end of this hypothetical war. Such a war would have been even more brutal than WWII was, but the outcome would not change.
  - 16y ago

leelin 16y ago

There are a few "flaws" to this solution actually, although the flaws are in assumptions + bayesian vs. frequentist philosophy differences. The solution mentioned in the link solves a different problem: You get a sample of K ints uniform randomly from 1 to N, where N is unknown. Based on your sample, what is your best estimate of N, so that if we repeatedly continue to give you independent random samples, the average answer your algorithm gives will be the correct answer, and provides the minimum variance compared to other algorithms? However, if we can put an upper bound on the number of tanks that could possibly exist, say definitely no more than 100 million tanks, and if we believe it is slightly more likely that older tanks will be on the front lines than newer tanks, or any other prior knowledge, then the proposed solution will be more incorrect. One of my former co-workers proposed computing a posterior distribution for estimates of N based on equally-weighted priors for N = max-observation to N = maximum cap (100 million tanks). Then the estimate is the expected value of the posterior distribution.

jules 16y ago
Is there for every commonly used frequentist estimation method a bayesian prior that gives the same answer?
- mturmon 16y ago
  For every commonly used frequentist estimator, there is an uncountable infinity of intractable Bayesian estimators.
  - aristus 16y ago
    ...probably.

bpick 16y ago

I recall reading that the same kind of thing used to happen with standing field armies, (think Napoleon sized blocks) where you could almost instantly assess an opponents forces based on simply recognizing divisions, regiments, etc. My guess is Napoleon-era field marshals did a cost-benefit analysis and decided that managing their forces simplistically (i.e. no irregular sized units) outweighed whatever inconvenience enemy intelligence posed. Relating this to the OP my guess is the Germans made a mistake and overlooked the serial numbers, rather than simply not caring.

hngryhppos 16y ago

I want to comment on how pretentious that website title is ("three standard deviations to the left"). I took that to imply the author (or his intended audience) is three standard deviations above average (intelligence?). Anyway, he says he am IB teacher... not surprised, this attitude of intellectual superiority is an IB hallmark.

Devilboy 16y ago
Wouldn't that be 3 SDs to the RIGHT instead?
- thefool 16y ago
  Yeah I took it as meaning a website for the brain-dead, which was much wittier than pretentious. Unless he meant right and said left, which is even funnier.
cema 16y ago
Could be the political left, you know.

deleted 16y ago

[deleted]

alex_h 16y ago

I guess one might also want to take into account the probability of capturing 5 tanks with all odd serial numbers (3.125%) vs the probability that the Germans had numbered their tanks in increments of 2

JadeNB 16y ago

As someone who spends a lot of time working with future high-school math teachers, I'd be really interested in reading some more by this author; but I can't find any contact information, and the blog moved to an 'invitation-only' Blogspot account in 2007. Does anyone know how to get in touch with the author to request an invitation?