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