A Scaling Result for Explosive Processes

M. Mitzenmacher, R. Oliveira, J. Spencer

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) = n^p$ 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) = n^p$. We then demonstrate the effectiveness of this approximation with some examples and demonstrate how it generalizes to a wide class of functions $f$.


Full Text: PDF