Mathematics – Probability
Scientific paper
2005-10-19
Mathematics
Probability
28 pages, no figures. One author removed from version 2. Version 3 corrects many typos and other minor issues
Scientific paper
Consider a balls-in-bins process in which each new ball goes into a given bin with probability proportional to f(n), where n is the number of balls currently in the bin and f is a fixed positive function. It is known that these so-called balls-in-bins processes with feedback have a monopolistic regime: if f(x)=x^p for p>1, then there is a finite time after which one of the bins will receive all incoming balls. Our goal in this paper is to quantify the onset of monopoly. We show that the initial number of balls is large and bin 1 starts with a fraction \alpha>1/2 of the balls, then with very high probability its share of the total number of balls never decreases significantly below \alpha. Thus a bin that obtains more than half of the balls at a "large time" will most likely preserve its position of leadership. However, the probability that the winning bin has a non-negligible advantage after n balls are in the system is ~ C n^{1-p}, and the number of balls in the losing bin has a power-law tail. Similar results also hold for more general functions f.
No associations
LandOfFree
The Onset of Dominance in Balls-in-Bins Processes with Feedback does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Onset of Dominance in Balls-in-Bins Processes with Feedback, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Onset of Dominance in Balls-in-Bins Processes with Feedback will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-242384