On martingale tail sums for the path length in random trees1. Issue 3 (6th September 2016) - Sulzbach, Henning
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 (in press) 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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017