German Tank Problem
threestandarddeviationstotheleft.wordpress.com
German Tank Problem
1–10 of 73 posts
Re: German Tank Problem
#2Is there a simple derivation or justification for this estimator?
Re: German Tank Problem
#3Key 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.
Re: German Tank Problem
#4Is there a simple derivation or justification for this estimator?
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
Re: German Tank Problem
#5Is there a simple derivation or justification for this estimator?
There is, had to learn it in a probability class.
http://en.wikipedia.org/wiki/German_tank_problem
Re: German Tank Problem
#6Is there a simple derivation or justification for this estimator?
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
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?
Re: German Tank Problem
#7Is there a simple derivation or justification for this estimator?
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
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.
Re: German Tank Problem
#8Earlier quoted context omitted.
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
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?
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.
Re: German Tank Problem
#9Is there a simple derivation or justification for this estimator?
There is, had to learn it in a probability class. http://en.wikipedia.org/wiki/German_tank_problem
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.
Re: German Tank Problem
#10There 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.