Large deviation asymptotics for occupancy problems.

DOI10.1214/009117904000000135zbMATH Open1057.60023arXivmath/0410174OpenAlexW2023077134MaRDI QIDQ1889799FDOQ1889799

Authors: Paul Dupuis, Carl J. Nuzman, Phil Whiting 

Publication date: 10 December 2004

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

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.

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

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

zbMATH Keywords

large deviationsEuler-Lagrange equationsurn modelsoccupancy problems

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bins and balls: Large deviations of the empirical occupancy process
• Tail bounds for occupancy and the satisfiability threshold conjecture
• On Birthday, Collectors', Occupancy and Other Classical Urn Problems
• Large Deviations with Diminishing Rates
• Explicit solutions for variational problems in the quadrant
• Large deviations for Markov processes with discontinuous statistics. I: General upper bounds
• Title not available (Why is that?)
• Optical switch dimensioning and the classical occupancy problem
• Title not available (Why is that?)
• Some asymptotic results for occupancy problems
• Sequential occupancy
• A large deviations analysis of the transient of a queue with many Markov fluid inputs: approximations and fast simulation
• Title not available (Why is that?)

Cited In (25)

• Large-Deviation Approximations for General Occupancy Models
• Analysis and optimization of recruitment stocking problems
• Empirical measure large deviations for reinforced chains on finite spaces
• Large deviation analysis of a droplet model having a Poisson equilibrium distribution
• Information Transmission under Random Emission Constraints
• 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
• Title not available (Why is that?)
• Finite sample properties of the mean occupancy counts and probabilities
• 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
• Convergence properties in certain occupancy problems including the Karlin-Rouault law
• Explicit Solutions for a Class of Nonlinear PDEs that Arise in Allocation Problems
• On the perturbation problem for occupation densities
• 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
• Large Deviations Principle for Occupancy Problems with Colored Balls
• Rare event asymptotics for exploration processes for random graphs
• Optical switch dimensioning and the classical occupancy problem
• Large deviations for the leaves in some random trees
• Asymptotics of the overflow in urn models
• On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem

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)