10
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ What you're asking is how to show that the sample maximum is sufficient for the parameter $\theta$ specifying the upper bound of a discrete uniform distribution from 1 to $\theta$. $\endgroup$ – Scortchi - Reinstate Monica Aug 12 at 9:10
  • 2
    $\begingroup$ Fisher Neyman factorization theorem The likelihood function, probability of the $k$ observed samples (summarized by the maximum $m$) given the parameters $n$ (the number of tanks) can be completely written in terms of the $k$ and $m$ $$\Pr(M=m | n,k) = \begin{cases} 0 &\text{if } m > n \\ \frac{\binom{m - 1}{k - 1}}{\binom n k} &\text{if } m \leq n, \end{cases}$$ Would that be an answer? $\endgroup$ – Sextus Empiricus Aug 12 at 9:22
  • $\begingroup$ @Scortchi that is correct, thank you for rephrasing it in a clearer way for me. $\endgroup$ – Bogdan Alexandru Aug 12 at 9:53
  • $\begingroup$ @MartijnWeterings no; essentially I am asking (quoting Scortchi's comment above) for a proof that the sample maximum is sufficient for the solution without actually computing the solution. $\endgroup$ – Bogdan Alexandru Aug 12 at 9:55
  • $\begingroup$ So you are not looking for the Fisher Neyman factorization theorem as the proof? $\endgroup$ – Sextus Empiricus Aug 12 at 9:58
15
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Awesome, exactly what I needed! Just one comment on your last parenthesis: you're saying "these high values close to hundred occur more often...", which I understand why it's true, but just to clarify: any value between 1 and 100 is more likely to occur when if the parameter is 100 (essentially the probability for each number in 1-100 is 1/parameter). $\endgroup$ – Bogdan Alexandru Aug 14 at 20:23
  • $\begingroup$ Also, now your initial comment to my post makes sense -- if I knew how to apply these concepts, your comment would have been exactly the hint I'd have needed to obtain the proof. Thanks again! $\endgroup$ – Bogdan Alexandru Aug 14 at 20:28
  • $\begingroup$ @BogdanAlexandru you are right; it is true for any value between 1-100. That is the counterintuitive idea, we tend to think that higher observed values are somehow more proof for some parameter value than low observed values, but for any number is equally likely and thus does/should not contribute anything to our believes about the model parameter (Except the maximum value that we observe. But even in the game that I made with only a choice between two values. It is such that even the maximum does not provide more information when it is higher or lower, except around the hundred boundary). $\endgroup$ – Sextus Empiricus Aug 15 at 0:07
  • $\begingroup$ My initial comment might have been too heavy, but I was just poking to see what sort of answer was necessary. Especially I find the term 'proof' a bit strong and was wondering whether you were just looking for the factorization theorem (which would be a question answered by yes when you would not know that theorem) or whether you were looking for something more vague and philosophical, like even challenging concepts of statistics/likelihood and going beyond such a theorem to look for a different type of "proof". $\endgroup$ – Sextus Empiricus Aug 15 at 0:10
  • $\begingroup$ Good read on my intentions then! Thanks again. $\endgroup$ – Bogdan Alexandru Aug 15 at 11:23
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This example depends a lot on the situation and the statements are not general. For instance, if the prior is 50% for 13 and 50% for 15 then the observation of 13 is not such that "our posteriors for N = 13, 15 will be larger than their prior" Observations can decrease the posterior relative to the prior. $\endgroup$ – Sextus Empiricus Aug 13 at 19:20
  • $\begingroup$ Also, the observation of more additional numbers can change the inference. In the case "if the next number we see is 5..." then the posterior will still change, even when numbers have already been 'helped out', additional numbers can increase this "helping out' (E.g. when you sample all numbers 1,2, ... 12, 13 then this will increase the posterior for 13 more than when you only sample 13) $\endgroup$ – Sextus Empiricus Aug 13 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.