Estimating number of balls by successively selecting a ball and marking it

Question

Lets say I have N balls in a bag. On my first draw, I mark the ball and replace it in the bag. On my second draw, if I pick up a marked ball I return it to the bag. If, however I pick up a non-marked ball then I mark it and return it to the bag. I continue this for any number of draws. What is the expected number of balls in the bag given a number of draws and the marked/unmarked history of draws?

Answer 1

Here is an idea. Let $\mathcal{I}$ be a finite subset of the natural numbers which will serve as the possible values for $N$. Suppose we have a prior distribution over $\mathcal{I}$. Fix a non-random positive integer $M$. Let $k$ be the random variable denoting the number of times we mark a ball in $M$ draws from the bag. The goal is to find $E(N|k)$. This will be function of $M,k$ and the prior.

By Bayes rule we have

$$ \begin{align} P(N=j|k) &= \frac{P(k|N=j)P(N=j)}{P(k)}\\ &= \frac{P(k|N=j)P(N=j)}{\sum_{r \in \mathcal{I}} P(k|N=r)P(N=r)} \end{align} $$

Computing $P(k|N=j)$ is a known calculation which is a variant on the coupon collectors problem. $P(k|N=j)$ is the probability that we observe $k$ distinct coupons in $M$ draws when there are $j$ coupons in total. See here for an argument for

$$ P(k|N=j) = \frac{\binom{j}{k}k!S(M,k)}{j^M} $$

where $S$ denotes a stirling number of the second kind. We can then calculate

$$ E(N|k) = \sum_{j \in \mathcal{I}}jP(N=j|k) $$

Below are some calculations for various $k$ and $M$. In each case we use a uniform prior on $[k,10k]$

\begin{array}{|c|c|c|} \hline M & k & E(N)\\\hline 10 & 5 & 7.99 \\ 15 & 5 & 5.60 \\ 15 & 10 & 23.69\\ 30 & 15 & 20.00\\ 30 & 20 & 39.53 \\ \hline \end{array}