3
$\begingroup$

Consider you have an initial bag of unique and identifiable items $(1.. K)$. From this bag, someone used an arbitrary criteria to tag $N$ items. You don't know the chosen criteria (which can be anything, from odd numbers, to just the item 65) but you know $K$. Your job is to estimate how many items were tagged (i.e. the cardinality of the tagged set, which is $N$). For that, you can sample (with and/or without replacement[1]), any arbitrary amount of items from the bag and verify the criteria at will.

I know how to estimate $N$ using a monte-carlo method (basically I keep drawing items and use the ratio of tagged/non-tagged to approximate the real cardinality). But I would like to provide an estimation as soon as one item is drawn, along with a confidence value (i.e. the probability of $N=n$). You can also assume that I can make an informed guess as a prior PDF of $N=n$ (e.g. uniform, or gaussian).


  1. Each method has a different computational cost, so I would love to get an answer for both methods, as to provide a chance on deciding the tradeoff.
$\endgroup$
7
  • 1
    $\begingroup$ en.wikipedia.org/wiki/German_tank_problem $\endgroup$
    – Tim
    Commented Jun 17, 2020 at 12:05
  • $\begingroup$ It's an amazing problem, and the bayesian tretament is simple and mind-blowing. But AFAIK there's a small difference here. Altough the elements are unique and identifiable, the tagging does not follow any know criteria. For example, in the geraman tank problem, if we observe tank number 3456, then we know there are at least 3456 tanks. Here, we already have that information (which is given by $x$, but observing item number 34 doesn't give us any more information than observing item 43). Failing to observe 3 non-tagged items in a sample of 4, does though... $\endgroup$ Commented Jun 17, 2020 at 12:10
  • $\begingroup$ Capture-recapture. $\endgroup$
    – Xi'an
    Commented Jun 17, 2020 at 12:13
  • $\begingroup$ Yes, coding is arbitrary. And capture-recapture seems like an interesting approach. But now that I've skimmed through the article, isn't this basically estimating the credibility of $N = n$, knowing only $K$? $\endgroup$ Commented Jun 17, 2020 at 12:21
  • $\begingroup$ And I think we gain information from just one sample, depending if we fail to observe the tag. For example, if I sample one item, and the tag isn't present, then I know for sure that $N < K$ and $p(N = K) = 0$. $\endgroup$ Commented Jun 17, 2020 at 12:27

1 Answer 1

2
$\begingroup$

Let's say that you take a sample of $s$ elements, with replacement, out of the $K$ items. Then the number of tagged item, $t$, that you get follow a binomial distribution $\mathcal{B}(\frac{N}{K}, s)$. You easily get that the posterior distribution of $N$ given $t$ is : $$\pi_s(N \mid t)\propto \pi(N) \left( \begin{array}\;s\\t\end{array} \right){\left(\frac{N}{K}\right)} ^ t {\left(1 -\frac{N}{K}\right)}^{s - t}$$

Where $\pi$ denotes the prior distribution on $N$ that you chose, and $\pi_s(.\mid t)$ denotes the posterior distribution obtained from $s$ draws given that $t$ of them where tagged. This formula works from the first draw that you make (i.e. $s = 1$), and you can apply it at each draw, i.e. for $s = 1, 2,...$ .

In general, to get an estimate (such as maximum a posteriori or expectation a posteriori), you need to use numerical methods (typically use a sampler or an approximation of the posterior) which is a bit computationally expensive.

If you want to avoid using numerical method for finding estimates and confidence intervals, you can use as a prior the conjugate prior of the binomial model, which is a Beta distribution. So if you assume that a priori $\frac{N}{K} \sim Beta(\alpha, \beta)$, then you know that the posterior distribution of $\frac{N}{K}$ is $Beta(\alpha + t, \beta + s - t)$. This leads to the following iterative procedure to get estimates and confidence interval at each draw:

  • Select prior parameters $\alpha$, $\beta$ of a Beta distribution.
  • At each draw that you make :
    • update $\alpha \leftarrow \alpha + 1$ and $\beta \leftarrow \beta$ if item is tagged,
    • update $\alpha \leftarrow \alpha$ and $\beta \leftarrow \beta + 1$ if item is not tagged,
    • compute estimate : expectation a posteriori is $\frac{\alpha}{\alpha + \beta}$, or maximum a posteriori is $\frac{\alpha - 1}{\alpha + \beta - 2}$,
    • compute confidence interval (e.g. using qbeta() function in R).

I guess the same could be done with better efficiency by using draws without replacements. In this case the binomial distribution would be replaced by a hypergeometric distribution and the adequate conjugate prior would then be a beta binomial distribution instead of a Beta. I cowardly refer you to this discussion to get details on how to make the update then.

$\endgroup$
1
  • 1
    $\begingroup$ I'm curious - if instead of trying to estimate the size of the population we were just interested in knowing the probability that at least one item is tagged, would we be able to find a more tractable formula in the scenario of sampling with replacement? $\endgroup$ Commented Jun 25, 2020 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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