Large deviations principle for occupancy problems with colored balls

Paul Dupuis*, Carl Nuzman, Phil Whiting

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


A large deviations principle (LDP), demonstrated for occupancy problems with indistinguishable balls, is generalized to the case in which balls are distinguished by a finite number of colors. The colors of the balls are chosen independently from the occupancy process itself. There are r balls thrown into n urns with the probability of a ball entering a given urn being 1 / n (i.e. Maxwell-Boltzmann statistics). The LDP applies with the scale parameter, n, tending to infinity and r increasing proportionally. The LDP holds under mild restrictions, the key one being that the coloring process by itself satisfies an LDP. This includes the important special cases of deterministic coloring patterns and colors chosen with fixed probabilities independently for each ball.

Original languageEnglish
Pages (from-to)115-141
Number of pages27
JournalJournal of Applied Probability
Issue number1
Publication statusPublished - Mar 2007
Externally publishedYes


  • Circuit-switched network
  • Coloring process
  • Maxwell-boltzmann statistics
  • Occupancy model
  • Optical packet switching
  • Population estimation
  • Sample path large deviations principle


Dive into the research topics of 'Large deviations principle for occupancy problems with colored balls'. Together they form a unique fingerprint.

Cite this