On martingale tail sums for the path length in random trees

DOI10.1002/rsa.20674zbMath1364.05067arXiv1412.3508OpenAlexW2963468965MaRDI QIDQ5739101

Henning Sulzbach

Publication date: 2 June 2017

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.3508

zbMATH Keywords

law of the iterated logarithmrandom treesmartingale central limit theorems

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Central limit and other weak theorems (60F05) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Related Items (3)

Distribution of tree parameters by martingale approach ⋮ Logarithmic integrals, zeta values, and tiered binomial coefficients ⋮ General Edgeworth expansions with applications to profiles of random trees

Uses Software

• Quicksort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees
• On the asymptotic internal path length and the asymptotic Wiener index of random Split trees
• The total path length of split trees
• Martingales and profile of binary search trees
• Large deviations for the weighted height of an extended class of trees
• A functional limit theorem for the profile of \(b\)-ary trees
• Uniform convergence of martingales in the branching random walk
• Distances in random plane-oriented recursive trees
• The profile of binary search trees
• A functional limit theorem for the profile of search trees
• Martingales and large deviations for binary search trees
• Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract)
• Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees
• On mixing sequences of random variables
• Width of a scale-free tree
• Limiting Distributions for Path Lengths in Recursive Trees
• Random Trees
• A limiting distribution for quicksort
• Large Deviations for Quicksort
• The convergence of moments in the martingale central limit theorem
• On central limit and iterated logarithm supplements to the martingale convergence theorem
• Universal Limit Laws for Depths in Random Trees
• On the internal path length ofd-dimensional quad trees
• Note on the heights of random recursive trees and random m‐ary search trees
• Total Path Length for Random Recursive Trees
• Quicksort asymptotics
• Rates of convergence for Quicksort
• Hypergeometrics and the cost structure of quadtrees
• Poisson approximations for functionals of random trees
• Refined quicksort asymptotics
• A note on the quicksort asymptotics
• A limit theorem for “quicksort”

This page was built for publication: On martingale tail sums for the path length in random trees