My cousin is at elementary school and every week is given a book by his teacher. He then reads it and returns it in time to get another one the next week. After a while we started noticing that he was getting books he had read before and this became gradually more common over time. Naturally, I started to wonder how one could estimate the total number of books in their library.

Say the true number of books in the library is $N$ and the teacher picks one uniformly at random (with replacement) to give to you each week. If at week $t$ you have received a book you have read before on $x$ occasions, then I can produce a maximum likelihood estimate for the number of books in the library following How many books are in a library? .

Clarification. If the books he receives are named $A,B,C,B, A, D$ then $x$ will be $0,0,0,1,2,2$ at successive weeks.

However, is there a mathematical formula as a function of $t$ and $x$ which will give me a 95% confidence interval for this estimate?

  • $\begingroup$ How about the number of students? That should be important too, because if there are more students more books are checked out. $\endgroup$ – Alt Feb 5 '14 at 22:16
  • $\begingroup$ Well yes but let's assume only my cousin gets books for the moment. I still don't know how to solve that simplified version. $\endgroup$ – Anush Feb 5 '14 at 22:26

I'll use the framework of the library book problem. Let $K$ be the total sample size, $N$ be the number of different items observed, $N_1$ be the number of items seen once, $N_2$ be the number of items seen 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 $M$ is given by

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

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

As noted in the discussion of the library problem, at times the upper bound will be infinite, especially for small samples. Similarly, the lower bound may need to be capped at zero.

This approach is due to Good and Turing. A reference with the confidence interval is Esty, The Annals of Statistics, 1983.

  • $\begingroup$ Could you explain or how you derived $A$ and $\hat {Q}$ $\endgroup$ – user92612 Jun 6 '15 at 22:22
  • $\begingroup$ The reference is publicly available through Project Euclid. $\endgroup$ – soakley Jun 7 '15 at 0:51
  • $\begingroup$ Thanks for the reference. Are you aware of any estimates that do not assume uniform probability? $\endgroup$ – user92612 Jun 7 '15 at 15:23
  • $\begingroup$ No, I don't know of any. $\endgroup$ – soakley Jun 7 '15 at 20:41

Yes and no. An EXACT confidence interval would be best approximated via simulation. However, you can get an approximate 95% CI using Wilks likelihodd ratio statistic on the sample likelihood function. This assumes that the likelihood function value of the true value (normalized so that the maximum value is 1) follows a chi-square distribution, so you can get a specified value of the likelihood to use as as cutoff.

  • $\begingroup$ I would be happy with something approximate. How exactly can I do this for my problem? $\endgroup$ – Anush Jan 30 '14 at 8:52

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.