Large deviation asymptotics for occupancy problems.

DOI10.1214/009117904000000135MaRDI QIDQ1889799zbMATH OpenOpenAlexFDO

Authors Paul Dupuis, Carl J. Nuzman, Phil Whiting

Publication date 10 December 2004

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0410174

zbMATH Keywords

large deviationsEuler-Lagrange equationsurn modelsoccupancy problems

Mathematics Subject Classification ID

Large deviations (60F10) Combinatorial probability (60C05) Sample path properties (60G17)

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.

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

• 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?)
• 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
• Large Deviations with Diminishing Rates
• Large deviations for Markov processes with discontinuous statistics. I: General upper bounds
• 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

(25)

• On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem
• Asymptotics of the overflow in urn models
• Analysis and optimization of recruitment stocking problems
• Large-Deviation Approximations for General Occupancy Models
• Empirical measure large deviations for reinforced chains on finite spaces
• Large deviation analysis of a droplet model having a Poisson equilibrium distribution
• Refined large deviation asymptotics for the classical occupancy problem
• Certain Occupancy Numbers Via an Algorithm for Computing Their Ratios
• A new method of normal approximation
• Finite sample properties of the mean occupancy counts and probabilities
• scientific article; zbMATH DE number 2240007 (Why is no real title available?)
• Bins and balls: Large deviations of the empirical occupancy process
• Optimal sampling strategies in the coupon collector's problem with unknown population size
• A nearly degenerate random variable occurring in an occupancy problem
• Nature-inspired algorithms for real-world optimization problems
• On the perturbation problem for occupation densities
• Convergence properties in certain occupancy problems including the Karlin-Rouault law
• Explicit Solutions for a Class of Nonlinear PDEs that Arise in Allocation Problems
• Application of the occupancy problem to wireless local area network establishments
• Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
• Rare event asymptotics for exploration processes for random graphs
• Large Deviations Principle for Occupancy Problems with Colored Balls
• Information Transmission under Random Emission Constraints
• Optical switch dimensioning and the classical occupancy problem
• Large deviations for the leaves in some random trees

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)