Inverse Coupon Collector’s Problem

This is motivated by a recent blog post by John D. Cook [2] discussing the problem of estimating the number of words in an author’s vocabulary, given an observation of the number of distinct words in the author’s work of length words.

The blog post references a paper by Brainerd [1], suggesting that it gives an estimate of as the root of the following equation:

However, although Brainerd discusses several different estimation methods, I was unable to find any mention of this particular one, either explicitly or in derivation.

At any rate, the motivation for this post is simply to note that this is essentially the “inverse” of the coupon collector’s problem, discussed several times here before, which is usually stated in terms of expectation: if each purchased box of cereal contains one of types of coupon, what is the expected number of boxes we must purchase to obtain all types of coupon?

This expected value is the above sum evaluated at . More generally, even when , the above sum is the expected number of boxes we must purchase to first observe distinct coupon types. This suggests a nicely intuitive, although not rigorous, argument for using the above equation to solve the “inverse” problem: if we have observed distinct coupon types among purchased coupons, then a reasonable estimate for the unknown is that value for which our number of observations is the expected number of coupons needed to first observe distinct types.

It’s interesting that this actually works. Sort of, anyway. That is, Dawkins [3] solves this inverse problem by computing the maximum likelihood estimate for , which turns out to be one of the integer values on either side of the (generally non-integral) root of the equation above.

References:

1. Brainerd, B., On the Relation between Types and Tokens in Literary Text, Journal of Applied Probability, 9(3) September 1972, p. 507-518 [JSTOR]
2. Cook, John D., Estimating an author’s vocabulary [HTML]
3. Dawkins, B., Siobhan’s Problem: The Coupon Collector Revisited, The American Statistician, 45(1) February 1991, p. 76-82 [JSTOR]