On martingale tail sums for the path length in random trees

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

For a martingale (Xn) converging almost surely to a random variable X, the sequence (Xn– 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

Details

Original languageEnglish
Number of pages13
JournalRandom Structures and Algorithms
Volume50
Issue number3
Early online date6 Sep 2016
Publication statusPublished - 23 Mar 2017