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?

  • 1
    $\begingroup$ Possibly related: have you looked at the capture-recapture method to estimate population abundance? en.wikipedia.org/wiki/Mark_and_recapture $\endgroup$
    – a.arfe
    Oct 3, 2014 at 7:38
  • $\begingroup$ "Expected number" cannot be understood in its usual technical sense of an expected value, because there is no probability distribution for $N$. It sounds like you are asking for an estimator of $N$. $\endgroup$
    – whuber
    Sep 30, 2015 at 0:03

1 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}


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.