Large deviation asymptotics for occupancy problems
Open Access
- 1 July 2004
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 32 (3B), 2765-2818
- https://doi.org/10.1214/009117904000000135
Abstract
In the standard formulation of the occupancy problem one considers the distribution of r balls in n cells, with each ball assigned independently to a given cell with probability 1/n. Although closed form expressions can be given for the distribution of various interesting quantities (such as the fraction of cells that contain a given number of balls), these expressions are often of limited practical use. Approximations provide an attractive alternative, and in the present paper we consider a large deviation approximation as r and n tend to infinity. In order to analyze the problem we first consider a dynamical model, where the balls are placed in the cells sequentially and “time” corresponds to the number of balls that have already been thrown. A complete large deviation analysis of this “process level” problem is carried out, and the rate function for the original problem is then obtained via the contraction principle. The variational problem that characterizes this rate function is analyzed, and a fairly complete and explicit solution is obtained. The minimizing trajectories and minimal cost are identified up to two constants, and the constants are characterized as the unique solution to an elementary fixed point problem. These results are then used to solve a number of interesting problems, including an overflow problem and the partial coupon collector’s problem.Keywords
This publication has 17 references indexed in Scilit:
- Large Deviations with Diminishing RatesMathematics of Operations Research, 2005
- Bins and balls; Large deviations of the empirical occupancy processThe Annals of Applied Probability, 2002
- Optical switch dimensioning and the classical occupancy problemInternational Journal of Communication Systems, 2002
- A large deviations analysis of the transient of a queue with many Markov fluid inputsACM Transactions on Modeling and Computer Simulation, 2002
- A Unified Derivation of Occupancy and Sequential Occupancy DistributionsPublished by Springer Science and Business Media LLC ,1997
- Tail bounds for occupancy and the satisfiability threshold conjectureRandom Structures & Algorithms, 1995
- Large Deviations for Markov Processes with Discontinuous Statistics, I: General Upper BoundsThe Annals of Probability, 1991
- On Birthday, Collectors', Occupancy and Other Classical Urn ProblemsInternational Statistical Review, 1986
- Some Asymptotic Results for Occupancy ProblemsThe Annals of Probability, 1977
- Sequential occupancyBiometrika, 1959