Coalescing particles on an interval (Q1283444)

This article presents a study of self-organizing balanced binary search trees. The process begins with a particle at each integer in \([0,n]\). The presence of a particle at a node indicates that it has not updated its parent since the last time that it has itself been updated. Thus, at each positive integer time, one of the particles remaining in \([0,n]\) is chosen at random and moved one to the left, coalescing with any particle that might already be there. The problem investigated by the authors is how long does it take until all particles coalesce (at 0)? This is the time at which all nodes have the correct estimate of their own rank. Let \(T_n\) denote the time until all particles coalesce. Then the main result of the paper is to confirm a previous simulation of N. Schabanel (1996) that the estimation of \(T_n\) is asymptotic to \((4/3\sqrt \pi)n^{3/2}\) and that the variance of \(T_n\) is asymptotic to \(Cn^{5/2}\), for some constant \(C\leq 8/(15 \sqrt\pi)\). Presumably, \(T_n\) obeys a central limit theorem.