Balls and bins models with feedback
Lists
Only you see this
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...