On the variance of the number of occupied boxes

Abstract

We consider the occupancy problem where balls are thrown independently at infinitely many boxes with fixed positive frequencies. It is well known that the random number of boxes occupied by the first n balls is asymptotically normal if its variance V_n tends to infinity. In this work, we mainly focus on the opposite case where V_n is bounded, and derive a simple necessary and sufficient condition for convergence of V_n to a finite limit, thus settling a long-standing question raised by Karlin in the seminal paper of 1967. One striking consequence of our result is that the possible limit may only be a positive integer number. Some new conditions for other types of behavior of the variance, like boundedness or convergence to infinity, are also obtained. The proofs are based on the poissonization techniques.

34 pages

References in corpus (4)

• Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
• Local limit theorems for finite and infinite urn models
• Rounding of continuous random variables and oscillatory asymptotics
• Moments of convex distribution functions and completely alternating sequences

Cited by in corpus (7)

• Local limit theorems for finite and infinite urn models
• Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications
• Limit theorems for the number of occupied boxes in the Bernoulli sieve
• Gaps and interleaving of point processes in sampling from a residual allocation model
• Small counts in the infinite occupancy scheme
• Records in the Infinite Occupancy Scheme
• Regeneration in Random Combinatorial Structures