Solution to German Tank Problem

Question

Is there a formal mathematical proof that the solution to the German Tank Problem is a function of only the parameters k (number of observed samples) and m (maximum value among observed samples)? In other words, can one prove that the solution is independent of the other sample values besides the maximum value?

Answer 1

Likelihood

Common problems in probability theory refer to the probability of observations $x_1, x_2, ... , x_n$ given a certain model and given the parameters (let's call them $\theta$) involved. For instance the probabilities for specific situations in card games or dice games are often very straightforward.

However, in many practical situations we are dealing with an inverse situation (inferential statistics). That is: the observation $x_1, x_2, ... , x_k$ is given and now the model is unknown, or at least we do not know certain parameters $\theta$.

In these type of problems we often refer to a term called the likelihood of the parameters, $\mathcal{L(\theta)}$, which is a rate of believe in a specific parameter $\theta$ given observations $x_1, x_2, .. x_k$. This term is expressed as being proportional to the probability for the observations $x_1, x_2, .. x_k$ assuming that a model parameter $\theta$ would be hypothetically true. $$\mathcal{L}(\theta,x_1, x_2, .. x_k) \propto \text{probability observations $x_1, x_2, .. x_k$ given $\theta$ }$$

For a given parameter value $\theta$ the more probable a certain observation $x_1, x_2, .. x_n$ is (relative to the probability with other parameter values), the more the observation supports this particular parameter (or theory/hypothesis that assumes this parameter). A (relative) high likelihood will reinforce our believes about that parameter value (there's a lot more philosophical to say about this).

---

Likelihood in the German tank problem

Now for the German tank problem the likelihood function for a set of samples $x_1, x_2, .. x_k$ is:

$$\mathcal{L}(\theta,x_1, x_2, .. x_k ) = \Pr(x_1, x_2, .. x_k, \theta) = \begin{cases} 0 &\text{if } \max(x_1, x_2, .. x_k) > \theta \\ {{\theta}\choose{k}}^{-1} &\text{if } \max(x_1, x_2, .. x_k) \leq \theta, \end{cases}$$

Whether you observe samples {1, 2, 10} or samples {8, 9, 10} should not matter when the samples are considered from a uniform distribution with parameter $\theta$. Both samples are equally likely with probability ${{\theta}\choose{3}}^{-1}$ and using the idea of likelihood the one sample does not tell more about the parameter $\theta$ than the other sample.

The high values {8, 9, 10} might make you think/believe that $\theta$ should be higher. But, it is only the value {10} That truly gives you relevant information about the likelihood of $\theta$ (the value 10 tells you that $\theta$ will be ten or higher, the other values 8 and 9 do not contribute anything to this information).

---

Fisher Neyman factorization theorem

This theorem tells you that a certain statistic $T(x_1, x_2, … , x_k)$ (ie some function of the observations, like the mean, median, or as in the German tank problem the maximum) is sufficient (contains all information) when you can factor out, in the likelihood function, the terms that are dependent on the other observations $x_1, x_2, … , x_k$, such that this factor does not depend on both the parameter $\theta$ and $x_1, x_2, … , x_k$ (and the part of the likelihood function that relates the data with the hypothetical parameter values is only dependent on the statistic but not the whole of the data/observations).

The case of the German tank problem is simple. You can see above that the entire expression for the Likelihood above is already only dependent on the statistic $\max(x_1, x_2, .. x_k)$ and the rest of the values $x_1, x_2, .. x_k$ does not matter.

---

Little game as example

Let's say we play the following game repeatedly: $\theta$ is itself a random variable and drawn with equal probability either 100 or 110. Then we draw a sample $x_1,x_2,...,x_k$.

We want to choose a strategy for guessing $\theta$, based on the observed $x_1,x_2,...,x_k$ that maximizes our probability to have the right guess of $\theta$.

The proper strategy will be to choose 100 unless one of the numbers in the sample is >100.

We could be tempted to choose the parameter value 110 already when many of the $x_1,x_2,...,x_k$ tend to be all high values close to hundred (but none exactly over hundred), but that would be wrong. The probability for such an observation will be larger when the true parameter value is 100 than when it is 110. So if we guess, in such situation, 100 as the parameter value, then we will be less likely to make a mistake (because the situation with these high values close to hundred, yet still below it, occurs more often in the case that the true value is 100 rather than the case that the true value is 110).

Answer 2

Sextus Empiricus gives a great explanation, but the description of the game is not quite right. (This should be a comment on his answer, but I don't have enough status points for that.)

The game example talks of the "proper" strategy, and all other strategies are "wrong". This should read the "maximum likelihood" strategy, and all others are "not maximum likelihood".

The whole point of the German Tank problem is to look beyond the trivial maximum likelihood estimate (which is simply the maximum number observed). The usual frequentist solution uses the minimum variance unbiased estimate (MVUE), which in this case is much more informative; it indicates the typical gap between the maximum observed value and the upper bound on the support.

I believe that the maximum observed is again a sufficient statistic for the MVUE, although I don't know how to prove that. Since the MVUE isn't based on the likelihood, I assume that the Fisher Neyman factorization theorem will not help. As such, I believe that the original poster's question is still open.

Answer 3

You haven't presented a precise formulation of "the problem", so it's not exactly clear what you're asking to be proved. From a Bayesian perspective, the posterior probability does depend on all the data. However, each observation of a particular serial number will support that number the most. That is, given any observation $n$, the odds ratio between posterior and prior will be greater for the hypothesis "the actual number of tanks is $n$" than it will be for "the actual number of tanks is [number other than $n$]". Thus, if we start with a uniform prior, then $n$ will have the highest posterior after seeing that observation.

Consider a case where we have the data point $13$, and hypotheses $N=10,13,15$. Obviously, the posterior for $N=10$ is zero. And our posteriors for $N=13,15$ will be larger than their prior. The reason for this is that in Bayesian reasoning, absence of evidence is evidence of absence. Any time we have an opportunity where we could have made an observation that would have decreased our probability, but don't, the probability increases. Since we could have seen $16$, which would have set our posteriors for $N=13,15$ to zero, the fact that we didn't see it means that we should increase our posteriors for $N=13,15$. But note that the smaller the number, the more numbers we could have seen that would have excluded that number. For $N=13$, we would have rejected that hypothesis after seeing $14,15,16,...$. But for $N=15$, we would have needed at least $16$ to reject the hypothesis. Since the hypothesis $N=13$ is more falsifiable than $N=15$, the fact that we didn't falsify $N=13$ is more evidence for $N=13$, than not falsifying $N=15$ is evidence for $N=15$.

So every time we see a data point, it sets the posterior of everything below it to zero, and increases the posterior of everything else, with smaller numbers getting the largest boost. Thus, the number that gets the overall largest boost will be the smallest number whose posterior wasn't set to zero, i.e. the maximum value of the observations.

Numbers less than the maximum affect how much larger a boost the maximum gets, but it doesn't affect the general trend of the maximum getting largest boost. Consider the above example, where we've already seen $13$. If the next number we see is $5$, what effect will that have? It helps out $5$ more than $6$, but both numbers have already been rejected, so that's not relevant. It helps out $13$ more than $15$, but $13$ already has been helped out more than $15$, so that doesn't affect which number has been helped out the most.