Avoiding defeat in a balls-in-bins process with feedback
| dc.creator | Oliveira, Roberto | |
| dc.creator | Spencer, Joel | |
| dc.date | 2005-10-31 | |
| dc.date | 2005-11-01 | |
| dc.date.accessioned | 2026-07-07T06:48:08Z | |
| dc.date.available | 2026-07-07T06:48:08Z | |
| dc.description | Imagine that there are two bins to which balls are added sequentially, and each incoming ball joins a bin with probability proportional to the p-th power of the number of balls already there. A general result says that if p>1/2, there almost surely is some bin that will have more balls than the other at all large enough times, a property that we call eventual leadership. In this paper, we compute the asymptotics of the probability that bin 1 eventually leads when the total initial number of balls $t$ is large and bin 1 has a fraction α<1/2 of the balls; in fact, this probability is \exp(c_p(α)t + O{t^{2/3}}) for some smooth, strictly negative function c_p. Moreover, we show that conditioned on this unlikely event, the fraction of balls in the first bin can be well-approximated by the solution to a certain ordinary differential equation. | |
| dc.description | 30 pages; to be submitted. V.2 has some minor corrections | |
| dc.identifier | https://arxiv.org/abs/math/0510663 | |
| dc.identifier | http://arxiv.org/abs/math/0510663 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/103883 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 60C05,60J10,60J20 | |
| dc.title | Avoiding defeat in a balls-in-bins process with feedback | |
| dc.type | text |