Expected waiting time to Move Balls across Bins

58 Views Asked by At

I have a set of $n$ bins $b_1, \cdots, b_n$, and $k$ balls, all initially placed in $b_1$. In each round, I pick a set of $m$ ($m \le k$) balls uniformly at random, independently, and move them "one bin up." So if a ball is in $b_3$, say, and is picked, then it is moved to $b_4$.

Importantly, when a ball is in $b_n$ and is picked in some round, then it stays in $b_n$.

I want to know the expected time for all the balls to reach $b_n$. What kind of process is this called?

1

There are 1 best solutions below

1
On

Not a full answer, but to answer your second question: this is a variation on coupon collector problem. (When n=2 and m=1, it is exactly the classical coupon collector). Varying n corresponds to asking how many sets of coupons you want (in classical, you just want one set), and varying m asks how many disjoint coupons you pull (with the added requirement that in a given round, you can only pull unique coupons).

When m=1, you should be able to give an exact answer using Poisson processes (If I sketched it right, it should correspond to the expected value of max of k independent Erlang(n-1)s.) I do not know how to do it for general m, but hopefully this answer helps you search for it (though I doubt for general m, there is a clean analytic solution; you might get more mileage out of just running simulations, or analyzing certain asymptotics (for instance, if m is constant but n and k go to infinity so that pulling 2 of the same ticket in a given round has vanishingly small probability).