Large deviation asymptotics for occupancy problems.
From MaRDI portal
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.
Urn occupancy problems center on the distribution of \(r\) balls in \(n\) cells, typically with each ball independently assigned to a given cell with probability \(1/n\). The present paper focuses on finite-dimensional occupancy measures in which urn occupancies above a given level are not distinguished. In this finite case, the authors provide a concise large deviations proof along with explicit, insightful and computable expressions for the rate functions and for the large deviations extremals. The rate function for the occupancy model after all the balls have been thrown is shown to have a simple and fairly explicit rate function, which can be defined in terms of relative entropy with respect to the Poisson distribution. Many different problems can be solved in this framework simply by changing the set over the rate function is minimized. The authors also present some sample path results for the evolution of the urn occupancies toward a particular event.
Recommendations
- Refined large deviation asymptotics for the classical occupancy problem
- Large-Deviation Approximations for General Occupancy Models
- Bins and balls: Large deviations of the empirical occupancy process
- Large Deviations Principle for Occupancy Problems with Colored Balls
- On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem
Cites work
- A large deviations analysis of the transient of a queue with many Markov fluid inputs: approximations and fast simulation
- Bins and balls: Large deviations of the empirical occupancy process
- Explicit solutions for variational problems in the quadrant
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 3548141 (Why is no real title available?)
- scientific article; zbMATH DE number 1058057 (Why is no real title available?)
- scientific article; zbMATH DE number 1153603 (Why is no real title available?)
- scientific article; zbMATH DE number 3798532 (Why is no real title available?)
- scientific article; zbMATH DE number 847278 (Why is no real title available?)
- scientific article; zbMATH DE number 3236539 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3274494 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- scientific article; zbMATH DE number 3050690 (Why is no real title available?)
- Large deviations for Markov processes with discontinuous statistics. I: General upper bounds
- Large Deviations with Diminishing Rates
- On Birthday, Collectors', Occupancy and Other Classical Urn Problems
- Optical switch dimensioning and the classical occupancy problem
- Sequential occupancy
- Some asymptotic results for occupancy problems
- Tail bounds for occupancy and the satisfiability threshold conjecture
Cited in
(26)- On the perturbation problem for occupation densities
- Finite sample properties of the mean occupancy counts and probabilities
- Bins and balls: Large deviations of the empirical occupancy process
- Empirical measure large deviations for reinforced chains on finite spaces
- Rare event asymptotics for exploration processes for random graphs
- Application of the occupancy problem to wireless local area network establishments
- Large deviation analysis of a droplet model having a Poisson equilibrium distribution
- On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem
- Information Transmission under Random Emission Constraints
- Convergence properties in certain occupancy problems including the Karlin-Rouault law
- Nature-inspired algorithms for real-world optimization problems
- Explicit Solutions for a Class of Nonlinear PDEs that Arise in Allocation Problems
- Large-Deviation Approximations for General Occupancy Models
- Large deviations for the leaves in some random trees
- Certain Occupancy Numbers Via an Algorithm for Computing Their Ratios
- Optical switch dimensioning and the classical occupancy problem
- Large Deviations Principle for Occupancy Problems with Colored Balls
- scientific article; zbMATH DE number 2240007 (Why is no real title available?)
- Asymptotics of the overflow in urn models
- Large deviations for empirical measures of self-interacting Markov chains
- A nearly degenerate random variable occurring in an occupancy problem
- Analysis and optimization of recruitment stocking problems
- Refined large deviation asymptotics for the classical occupancy problem
- Optimal sampling strategies in the coupon collector's problem with unknown population size
- A new method of normal approximation
- Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
This page was built for publication: Large deviation asymptotics for occupancy problems.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1889799)
