On martingale tail sums for the path length in random trees

Abstract

For a martingale $(X_n)$ converging almost surely to a random variable $X$, the sequence $(X_n-X)$ is called martingale tail sum. Recently, Neininger [Random Structures Algorithms, 46 (2015), 346-361] proved a central limit theorem for the martingale tail sum of R{é}gnier's martingale for the path length in random binary search trees. Gr{ü}bel and Kabluchko [to appear in Annals of Applied Probability, (2016), arXiv 1410.0469] gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane-oriented recursive trees.

arXiv commentResults generalized to broader tree model; convergence of moments in the CLT