A scaling result for explosive processes

M. Mitzenmacher, R. Oliveira, J. Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the asymptotic behavior of the following model: balls are sequentially thrown into bins so that the probability that a bin with n balls obtains the next ball is proportional to f(n) for some function f. A commonly studied case where there are two bins and f(n) = np for p > 1. In this case, one of the two bins eventually obtains a monopoly, in the sense that it obtains all balls thrown past some point. This model is motivated by the phenomenon of positive feedback, where the "rich get richer." We derive a simple asymptotic expression for the probability that bin 1 obtains a monopoly when bin 1 starts with x balls and bin 2 starts with y balls for the case f(n) = np. We then demonstrate the effectiveness of this approximation with some examples and demonstrate how it generalizes to a wide class of functions f.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume11
Issue number1 R
DOIs
StatePublished - Apr 13 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A scaling result for explosive processes'. Together they form a unique fingerprint.

Cite this