## Abstract

Balls-in-bins models describe a random sequential allocation of infinitely many balls into

a finite number of bins. In these models a ball is placed into a bin with probability proportional

to a given function (feedback function), which depends on the number of existing balls in the bin.

Typically, the feedback function is the same for all bins (symmetric feedback), and there are no

constraints on the number of balls in the bins. In this paper we study versions of BB models

with two bins, in which the above assumptions are violated. In the first model of interest the

feedback functions can depend on a bin (BB model with asymmetric feedback). In the case when

both feedback functions are power law and superlinear, a single bin receives all but finitely many

balls almost surely, and we study the probability that this happens for a given bin. In particular,

under certain initial conditions we derive the normal approximation for this probability. This

generalizes the result in Mitzenmacher et al. (2004) obtained in the case of the symmetric feedback.

The main part of the paper concerns the BB model with asymmetric feedback evolving subject to

certain constraints on the numbers of allocated balls. The model can be interpreted as a transient

reflecting random walk in a curvilinear wedge, and we obtain a complete classification of its long

term behavior.

a finite number of bins. In these models a ball is placed into a bin with probability proportional

to a given function (feedback function), which depends on the number of existing balls in the bin.

Typically, the feedback function is the same for all bins (symmetric feedback), and there are no

constraints on the number of balls in the bins. In this paper we study versions of BB models

with two bins, in which the above assumptions are violated. In the first model of interest the

feedback functions can depend on a bin (BB model with asymmetric feedback). In the case when

both feedback functions are power law and superlinear, a single bin receives all but finitely many

balls almost surely, and we study the probability that this happens for a given bin. In particular,

under certain initial conditions we derive the normal approximation for this probability. This

generalizes the result in Mitzenmacher et al. (2004) obtained in the case of the symmetric feedback.

The main part of the paper concerns the BB model with asymmetric feedback evolving subject to

certain constraints on the numbers of allocated balls. The model can be interpreted as a transient

reflecting random walk in a curvilinear wedge, and we obtain a complete classification of its long

term behavior.

Original language | English |
---|---|

Pages (from-to) | 1-19 |

Number of pages | 19 |

Journal | ALEA, Latin American Journal of Probability and Mathematical Statistics |

Volume | 20 |

Publication status | Published - 15 Jan 2023 |