Time-dependent balls and bins model with positive feedback
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2018
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915392311525376 |
|---|---|
| author | Sidorova, Nadia |
| author_facet | Sidorova, Nadia |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1809_02221 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Time-dependent balls and bins model with positive feedback Sidorova, Nadia Probability 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. |
| title | Time-dependent balls and bins model with positive feedback |
| topic | Probability |
| url | https://arxiv.org/abs/1809.02221 |