On martingale tail sums for the path length in random trees1. Issue 3 (6th September 2016)

• Record Type: Journal Article
• Authors: Sulzbach, Henning
• Is Part Of: Random structures & algorithms. Volume 50:Issue 3(2017)
• Page Start: 493
• Page End: 508
• Publication Date: 2016-09-06
• Subjects: Martingale central limit theorems -- law of the iterated logarithm -- random trees; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20674
• Languages: English
• ISSNs: 1042-9832

Abstract

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