Balls and Bins and the Infinite Process with Random Deletions

We consider an infinite balls-into-bins process with deletions where in each discrete step t a coin is tossed as to whether, with probability β(t) ∈ (0, 1), a new ball is allocated using the Greedy[2] strategy (which places the ball in the lower loaded of two bins sampled uniformly at random) or, with remaining probability 1 -β(t), a ball is deleted from a non-empty bin chosen uniformly at random. Let n be the number of bins and m(t) the total load at time t. We are interested in bounding the discrepancy x max (t) -m(t)/n (current maximum load relative to current average) and the overload x max (t) -m max (t)/n (current maximum load relative to highest average observed so far).

We prove that at an arbitrarily chosen time t the total number of balls above the average is O(n) and that the discrepancy is O(log(n)). For the discrepancy, we provide a matching lower bound. Furthermore we prove that at an arbitrarily chosen time t the overload is log log(n) + O(1). For "good" insertion probability sequences (in which the average load of time intervals with polynomial length increases in expectation) we show that even the discrepancy is bounded by log log(n) + O(1).

One of our main analytical tools is a layered induction, as per [ABKU99]. Since our model allows for rather more general scenarios than what was previously considered, the formal analysis requires some extra ingredients as well, in particular a detailed potential analysis. Furthermore, we simplify the setup by applying probabilistic couplings to obtain certain "recovery" properties, which eliminate much of the need for intricate and careful conditioning elsewhere in the analysis.