Coalescing particles on an interval
type: Item
instance of: scholarly article
title: Coalescing particles on an interval
zbMATH Open document ID: 0922.60061
DOI: 10.1023/A:1021704912660
author: Russell Lyons
author: Michael Larsen
published in: Journal of Theoretical Probability
publication date: 1999-10-14T00:00:00Z
review text: 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.
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1275653
zbMATH Keywords: self-organizing balanced binary search trees
zbMATH Keywords: coalescing particles
zbMATH Keywords: time estimation and variance
MaRDI profile type: Publication
full work available at URL: a:1021704912660
OpenAlex ID: W1542432931
description: scientific article; zbMATH DE number 1275653