Expected coalescence time for a nonuniform allocation process

We study a process where balls are repeatedly thrown into n boxes independently according to some probability distribution p. We start with n balls, and at each step, all balls landing in the same box are fused into a single ball; the process terminates when there is only one ball left (coalescence). Let c := .jpj2, the collision probability of two fixed balls. We show that the expected coalescence time is asymptotically 2c.1, under two constraints on p that exclude a thin set of distributions p. One of the constraints is c = o(ln.2n). This ln.2n is shown to be a threshold value: for c = .(ln.2n), there exists p with c(p) = c such that the expected coalescence time far exceeds c.1. Connections to coalescent processes in population biology and theoretical computer science are discussed.