On martingale tail sums for the path length in random trees |
| |
Authors: | Henning Sulzbach |
| |
Affiliation: | School of Computer Science, McGill University, Montreal, Canada |
| |
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 |
| |
Keywords: | Martingale central limit theorems law of the iterated logarithm random trees |
|
|