On the expected number of different records in a random sample

Abstract

Given a discrete distribution, an interesting problem is to determine the minimum size of a random sample drawn from this distribution, in order to observe a given number of different records. This problem is related with many applied problems, like the Heaps' Law in linguistics and the classical Coupon-collector's problem. In this note we are able to compute theoretically the expected size of such a sample and we provide an approximation strategy in the case of the Mandelbrot distribution.