| We study a so-called coalescent process that can be described as follows: start with a set of n boxes and b0 balls. Let p = (p 1; p2, . . . , p n) be any probability vector. Throw each ball into box j with probability pj, independently for each ball. Any balls that land in the same box are fused into a single ball, and the process is repeated with this (possibly smaller) number of balls. Continue this process until there is only one ball left; the time at which this happens is called the coalescence time, denoted T. This problem can also be phrased in the context of population genetics, where it is referred to as the Generalized Wright-Fisher Model. In that formulation, the balls represent ancestral lineages, and T is the number of generations back in time one has to go to find a common ancestor for b0 individuals from the current generation. We shall mainly study the expected coalescence time E[T]. For b0 = n, and p nonuniform, little is known about the expected time spent when the number of balls is relatively large. We show that for vectors p satisfying a mild uniformity condition, this quantity is negligible compared to the expected time spent when the number of balls is "small", which is asymptotically 2jp2 j-1 . We further show that this condition is sharp, in that if it is not met, there are vectors p which give rise to processes which do not have this qualitative behavior, and thus where the expected coalescence time far exceeds 2jp2 j-1 . |
