On martingale tail sums for the path length in random trees

2014/12/11 by Sulzbach, Henning · 1 citation
#60G42 #68P05 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Primary 60F15 #Probability (math.PR) #secondary 60F05

paper · doi:10.48550/arxiv.1412.3508

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.

Cited by

• Law of iterated logarithm for supercritical non-symmetric branching Markov process

Related

• A functional central limit theorem for branching random walks, almost\n sure weak convergence, and applications to random trees
• On tail bounds for random recursive trees
• Martingales and Profile of Binary Search Trees
• Limit Laws for Functions of Fringe trees for Binary Search Trees and Recursive Trees
• Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees