Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1809.02221 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Balls and bins models are classical probabilistic models where balls are added to bins at random according to a certain rule. The balls and bins model with feedback is a non-linear generalisation of the Pólya urn, where the probability of a new ball choosing a bin with $m$ balls is proportional to $m^α$, with $α$ being the feedback parameter. It is known that if the feedback is positive (i.e. $α>1$) then the model is monopolistic: there is a finite time after which one of the bins will receive all incoming balls. We consider a time-dependent version of this model, where $σ_n$ independent balls are added at time $n$ instead of just one. We show that if $α>1$ then one of the bins gets all but a negligible number of balls, and identify a phase transition in the growth of $(σ_n)$ between the monopolistic and non-monopolistic behaviour. We also describe the critical regime, where the probability of monopoly is strictly between zero and one. Finally, we show that in the feedback-less case $α=1$ no dominance occurs, that is, each bin gets a non-negligible proportion of balls eventually. This is in sharp contrast with a similar model where new balls added at time $n$ are all placed in the same bin rather than independently.