Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $x$ times, is there an unbiased estimator for the total number of books in the library and what is the variance of this estimator? Is there another biased estimator with lower variance?

In my cousin's case, in the first $30$ weeks he received a book he had received before $3$ times.

share|improve this question
    
Is "in first 30 weeks he received a book he had received before 3 times" talking about the worst example, or about what happened on the 30th week? –  Henry Dec 22 '13 at 10:14
    
This is a variant of the Birthday problem, where instead of knowing the number of days in a year and estimating when you get your first collision, you look at how many collisions you get and estimate the total number of "days in a year" (books in the library). There are ways of doing this, but I haven't had any real statistics, so I don't know them too well. @Henry I assume it means that for 3 of the 30 weeks he didn't have anything interesting to read, since he got a book he had already read. –  Arthur Dec 22 '13 at 10:17
    
@Henry I meant that over the course of the first 30 weeks, on three occasions he was given a book that he had been given in some previous week (as Arthur also said). Can you improve the estimate if you also know on exactly which of the first 30 weeks he was given these duplicate books? It would make sense that knowing the date of the most recent duplicate book would tell you something. –  Anush Dec 22 '13 at 10:22
    
@Anush: why do you think the timing affects anything? I suspect that the number of weeks and the number of originals would be a sufficient statistic on the assumption that books are random –  Henry Dec 25 '13 at 23:12
    
@Henry In all honesty I don't know. Getting 3 duplicates in the first 4 weeks and then none for 26 weeks might give the same as 3 duplicates evenly spread out over 30 weeks. –  Anush Dec 26 '13 at 9:27

3 Answers 3

up vote 4 down vote accepted

Given there are $N$ books in total and $t$ weeks, the probability of having received $x$ duplicates (i.e. $t-x$ unique books) is $$S_2(t,t-x) \frac{ N!}{(N-(t-x))! N^t}$$ where $S_2$ denotes a Stirling number of the second kind. In your example $S_2(30,27)=10359090$.

The maximum likelihood estimate of $N$ given $t=30$ and $x=3$ is $135$. If there really were $N=135$ books then the expected number of duplicates would be about $3.01017$, while if there were $N=136$ books then the expected number of duplicates would be about $2.98951$. The value for $N$ which would give exactly $3$ is about $135.4907$ though of course this is not an integer.

So $135$ is a reasonable estimate. But there is still considerable uncertainty: any value for $N$ from $56$ to $601$ would have a likelihood for $3$ duplicates out of $30$ more than a tenth of the likelihood resulting from $N=135$. The variance for the number of duplicates if $N=135$ is about $2.26258$.

share|improve this answer
    
Thank you. How do you compute the standard error (or variance) for this maximum likelihood estimate? –  Anush Dec 25 '13 at 15:56
    
Assuming there are at least 30 books, there will be a positive probability of no duplicates in 30 weeks, with an unbounded maximum likelihood estimate. So what do you mean by "the standard error (or variance)" ? –  Henry Dec 26 '13 at 9:50
    
I may have got things confused but in your answer you give a maximum likelihood estimate of $135$. I was asking about the standard error for this estimator (see for example unc.edu/courses/2010fall/ecol/563/001/docs/lectures/… point 4.). –  Anush Dec 27 '13 at 14:06
    
I may have misunderstood what you are thinking about, but I am suggesting that, for any actual number of books of 30 or more, there is is a positive probability that there will be no duplicates and so there is is a positive probability that the maximum likelihood estimator will be infinite, and so there is is a positive probability that the error will be infinite. So the standard error of the maximum likelihood estimator will also be infinite.... –  Henry Dec 28 '13 at 22:39
    
... This is of course not what you want. You know in this case that the maximum liklihood estimate (not estimator) is finite. One way round this would be to use Bayesian methods, assuming a prior for the number of books and using the fact of three duplicates to produce a posterior distribution, and then finding the standard deviation of that posterior distribution. But I do not think that is what you are asking for. –  Henry Dec 28 '13 at 22:41

The Good-Turing estimate is given by $$\hat M ={N \over {1-{N_1 \over K}}}$$ where $N$ is the number of different names observed, $N_1$ is the number of names seen once, and $K$ is the total number of observations. For your data, assuming 24 observations were unique and the 3 duplicates were all seen twice, this yields $$\hat M = {27 \over {1-{24 \over 30}}}= 135.$$ I don't know about the standard error of this estimate; look up Good-Turing and see what you can find.

share|improve this answer

The book picked on week $t$ was never picked before if, independently and $t-1$ times, another book was picked. This happens with probability $p^{t-1}$, where $p=1-N^{-1}$. Thus, the mean number of weeks up to week $t$ when the book picked was not a new one is $$ W_t=\sum_{s=1}^t\left(1-p^{s-1}\right)=t-\frac{1-p^t}{1-p}, $$ that is, $$ t-W_t=N\cdot(1-(1-N^{-1})^t).\tag{$\ast$} $$ The RHS increases from $1$ when $N=1$ to $t$ when $N=\infty$ and the book picked on week $1$ is always a new one, hence $0\leqslant W_t\leqslant t-1$. For every observed $W_t$ in $\{0,1,\ldots,0,t-1\}$, there exists a unique $\hat N_t$ such that $(\ast)$ holds.

The exact value of $\hat N_t$ has no algebraic expression when $t$ is large but, in the limit $t\to\infty$ and $W_t/t\to\mathtt w$, one knows that $\hat N_t/t$ converges to the unique solution $\nu$ of the equation $$ \nu\cdot(1-\mathrm e^{-1/\nu})=1-\mathtt w.\tag{$\dagger$} $$ Numerically, if $t=30$ and $W_t=3$, $(\ast)$ yields $\hat N_t=135.49$ hence one would conclude that $N=135$ or $N=136$, and the approximation $(\dagger)$ with $\mathtt w=1/10$ yields $\nu t=139.8$, which is not too far off the mark even though $t=30$ is relatively small (note that $\nu t$ always overestimates $\hat N_t$, due to convexity).

share|improve this answer
    
Thank you. Is it possible to compute the standard error for this estimator? Also, is it in fact sufficent just to count how many books have been duplicated after 30 weeks or could it help to know exactly when the duplicates occurred? –  Anush Dec 25 '13 at 16:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.