(Bayesian) estimation of the underlying population size knowing its upper bound after $x$ draws

Question

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.

Answer 1

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.