András Antos' abstracts

of book chapters

[In Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Trends in Mathematics, Birkhäuser Verlag, Basel, 3-15, 2000]

Rawa trees

András Antos and Luc Devroye


A rawa tree is a binary search tree for an ordinary random walk 0,S1 ,S2,S3,..., where Sn=\sumi=1n Xi and the Xi 's are i.i.d. distributed as X. We study the height Hn of the rawa tree, and show that if X is absolutely continuous with bounded symmetric density, if X has finite variance, and if the density of X is bounded away from zero near the origin, then Hn / \sqrt{2n} tends to the Erdõs-Kac-Rényi distribution.

Keywords and phrases. Random binary search tree, probabilistic analysis, random walk, Catalan constant, limit distributions.

CR Categories: 3.74, 5.25, 5.5.

Back to the publications

© András Antos
Updated: Feb 7, 2021
aantos NOSPAMkukacNOSPAM gmail pont com