In a variation on the coupon collector's problem, you don't know the number of coupons and must determine this based on data. I will refer to this as the fortune cookie problem:

Given an unknown number of distinct fortune cookie messages $n$, estimate $n$ by sampling cookies one at a time and counting how many times each fortune appears. Also determine the number of samples necessary to get a desired confidence interval on this estimate.

Basically I need an algorithm that samples just enough data to reach a given confidence interval, say $n \pm 5$ with $95\%$ confidence. For simplicity, we can assume that all fortunes appear with equal probability/frequency, but this is not true for a more general problem, and a solution to that is also welcome.

This seems similar to the German tank problem, but in this instance, fortune cookies are not labeled sequentially, and thus have no ordering.

  • 1
    $\begingroup$ Do we know the messages are equally frequent? $\endgroup$ – Glen_b Feb 22 '14 at 11:00
  • $\begingroup$ edited question: Yes $\endgroup$ – goweon Feb 22 '14 at 11:03
  • 2
    $\begingroup$ Can you write down the likelihood function? $\endgroup$ – Zen Feb 22 '14 at 16:41
  • 2
    $\begingroup$ People doing wildlife studies capture, tag, and release animals. They later infer the size of the population based on the frequency with which they recapture already tagged animals. It sounds like your problem is mathematically equivalent to theirs. $\endgroup$ – Emil Friedman Feb 25 '14 at 19:17

For the equal probability/frequency case, this approach may work for you.

Let $K$ be the total sample size, $N$ be the number of different items observed, $N_1$ be the number of items seen exactly once, $N_2$ be the number of items seen exactly twice, $A=N_1(1− {N_1 \over K} )+2N_2,$ and $\hat Q = {N_1 \over K}.$

Then an approximate 95% confidence interval on the total population size $n$ is given by

$$ \hat n_{Lower}={1 \over {1-\hat Q+{1.96 \sqrt{A} \over K} }}$$

$$\hat n_{Upper}={1 \over {1-\hat Q-{1.96 \sqrt{A} \over K} }}$$

When implementing, you may need to adjust these depending on your data.

The method is due to Good and Turing. A reference with the confidence interval is Esty, Warren W. (1983), "A Normal Limit Law for a Nonparametric Estimator of the Coverage of a Random Sample", Ann. Statist., Volume 11, Number 3, 905-912.

For the more general problem, Bunge has produced free software that produces several estimates. Search with his name and the word CatchAll.

  • 1
    $\begingroup$ I took the liberty of adding the Esty reference. Please double check it's the one you meant $\endgroup$ – Glen_b Mar 1 '16 at 0:03
  • $\begingroup$ Is it possible @soakley to get bounds (probably less precise bounds) if you only know $K$ (sample size), and $N$ (number of unique items seen)? i.e. we don't have information about $N_1$ and $N_2$. $\endgroup$ – Basj Nov 7 '17 at 0:45
  • $\begingroup$ I don't know of a way to do it with just $K$ and $N.$ $\endgroup$ – soakley Nov 7 '17 at 18:35

I do not know if it can help but it is the problem of taking $k$ different balls during $n$ trials in an urn with $m$ balls labelled differently with replacement. According to this page (in french) if $X_n$ if the random variable counting the number of different balls the probability function is given by: $P(X_n = k) = {m \choose k} \sum_{i=0}^k {(-1)^{k-i}{k \choose i}}{(\frac{i}{m})^n}$

Then you can use a maximum likelihood estimator.

Another formula with proof is given here to solve the occupancy problem.


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.