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 \(\beta(t)\in(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-\beta(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).