Stochastic process of balls and bins

Question

Suppose I have $n$ balls in a bag and $an$ bins, for some integer $a>2$. I draw a ball from the bag and throw it to one of the bins at random. If the bin is empty then the ball stays in the bin. However, if the bin is occupied by another ball then I take both of the balls out of the bin and put them back in the bag. Then I draw another ball from the bag and follow the same procedure. I keep doing this until the bag is empty (note that in this case all bins are either empty or occupied by one ball). What is the expected number of times I draw a ball from the bag (can be approximately, assume n is large)? I feel that it can be upper bounded by nlog(n) but I am not sure how to do that

Answer 1

In each draw, the number of balls in the bag decreases by 1 with probability at least $(a-1)/a$ and increases by 1 with probability at most $1/a$, so (given the past) it decreases in expectation at least by $(a-2)/a$. By comparing to a biased random walk, or using the Azuma-Hoeffding inequality, it follows that for every $\epsilon>0$, after at most $na(1+\epsilon)/(a-2)$ draws, the bag will be empty with high probability.