Balls and bins models with feedback

Eleni Drinea, Alan M. Frieze, Michael MitzenmacherSODA 2002 · OpenReview

Abstract

We examine generalizations of the classical balls and bins models, where the probability a ball lands in a bin is proportional to the number of balls already in the bin raised to some exponent p. Such systems exhibit positive or negative feedback, depending on the exponent p, with a phase transition occurring at p = 1. Similar models have proven useful in economics and chemistry; for example, systems with positive feedback (p > 1) tend naturally toward monopoly. We provide several results and useful heuristics for these models, including showing a bound on the time to achieve monopoly with high probability.
BibTeX
@inproceedings{drinea2002balls,
  author = {Eleni Drinea and Alan M. Frieze and Michael Mitzenmacher},
  title = {{Balls and bins models with feedback}},
  booktitle = {SODA},
  year = {2002},
  url = {https://openreview.net/forum?id=ocTuKPVzCav},
}

Loading related content...

Figure