Bins and balls: Large deviations of the empirical occupancy process

DOI10.1214/aoap/1026915618zbMath1013.60017OpenAlexW2021028294WikidataQ58374472 ScholiaQ58374472MaRDI QIDQ1872378

Fabrice Gamboa, Stéphane Boucheron, Christian Léonard

Publication date: 6 May 2003

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

Full work available at URL: https://doi.org/10.1214/aoap/1026915618

zbMATH Keywords

occupancyrandom graphsOrlicz spaceslarge deviationsPoisson approximationSanov theorem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Large deviations (60F10)

Related Items

Large deviation analysis of a droplet model having a Poisson equilibrium distribution, Large deviation asymptotics for occupancy problems., Nature-inspired algorithms for real-world optimization problems, Refined large deviation asymptotics for the classical occupancy problem, Information Transmission under Random Emission Constraints, Large deviation principles for empirical measures of colored random graphs, Conditional large and moderate deviations for sums of discrete random variables. Combinatoric applications, Large Deviations Principle for Occupancy Problems with Colored Balls, Large deviations of empirical neighborhood distribution in sparse random graphs, Space-time large deviations in capacity-constrained relay networks, On the power of two choices: balls and bins in continuous time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A functional central limit theorem for a generalized occupancy problem
• On general minimax theorems
• Normal approximations to sums of scores based on occupancy numbers
• A Berry-Esseen bound for an occupancy problem
• Compound Poisson approximation for nonnegative random variables via Stein's method
• Central limit theorems for multinomial sums
• On large deviations for particle systems associated with spatially homogeneous Boltzmann type equations
• Sudden emergence of a giant \(k\)-core in a random graph
• Integrals which are convex functionals
• An urn model from learning theory
• Almost all graphs with 1.44n edges are 3-colorable
• On the number of vertices of given degree in a random graph
• The degree sequence of a random graph. I. The models
• The Characteristic Function of a Conditional Statistic