Loading...
Please wait, while we are loading the content...
Time-dependent balls and bins model with positive feedback
| Content Provider | arXiv |
|---|---|
| Author | Sidorova, Nadia |
| Date of Submission | 2018-09-06 |
| Abstract | 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\'olya urn, where the probability of a new ball choosing a bin with $m$ balls is proportional to $m^{\alpha}$, with $\alpha$ being the feedback parameter. It is known that if the feedback is positive (i.e. $\alpha>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 $\sigma_n$ independent balls are added at time $n$ instead of just one. We show that if $\alpha>1$ then one of the bins gets all but a negligible number of balls, and identify a phase transition in the growth of $(\sigma_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 $\alpha=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. |
| Related Links | https://arxiv.org/pdf/1809.02221.pdf |
| arXiv | 1809.02221 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics - Probability Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
