On tail bounds for random recursive trees

DOI10.1239/JAP/1339878805MaRDI QIDQ2897163zbMATH OpenOpenAlexFDO

Authors Götz Olaf Munsonius

Publication date 8 July 2012

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.jap/1339878805

zbMATH Keywords

path lengthprobabilistic analysis of algorithmsrandom treetail boundWiener index

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Inequalities; stochastic orderings (60E15)

Recommendations

• scientific article; zbMATH DE number 5763324
• Limit theorems for functionals of recursive trees.
• Tail behaviour and martingale convergence of random recursive structures and algorithms
• Exponential bounds and tails for additive random recursive sequences
• scientific article; zbMATH DE number 5764927

Cites work

• A limit theorem for “quicksort”
• Approximating the limiting quicksort distribution
• Exponential bounds and tails for additive random recursive sequences
• scientific article; zbMATH DE number 2127728 (Why is no real title available?)
• scientific article; zbMATH DE number 5763324 (Why is no real title available?)
• scientific article; zbMATH DE number 1375579 (Why is no real title available?)
• scientific article; zbMATH DE number 837692 (Why is no real title available?)
• Large Deviations for Quicksort
• Large deviations for the weighted height of an extended class of trees
• Limit theorems for functionals of recursive trees.
• Note on the heights of random recursive trees and random m‐ary search trees
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
• The center of mass of the ISE and the Wiener index of trees
• The height of increasing trees
• The total Steiner k-distance for b-ary recursive trees and linear recursive trees

Cited in

(19)

• Applications of the theory of records in the study of random trees
• Probabilistic recurrence relations revisited
• On a tail bound for analyzing random trees
• Exponential tail bounds for max-recursive sequences
• Tails for (max, plus) recursions under subexponentiality
• Profile of random exponential recursive trees
• Recursive random variables with subgaussian distributions
• scientific article; zbMATH DE number 6522631 (Why is no real title available?)
• Limit theorems for functionals of recursive trees.
• Tail behaviour and martingale convergence of random recursive structures and algorithms
• The Hitting Time for the Height of a Random Recursive Tree
• Random infinite trees and supercritical behavior of collision resolution algorithms
• Probability bounds given by hypercherry trees
• (Probabilistic) recurrence relations revisited
• Random tree recursions: Which fixed points correspond to tangible sets of trees?
• The Wiener index of random digital trees
• Note on a stochastic recursion
• Exponential bounds and tails for additive random recursive sequences
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees

This page was built for publication: On tail bounds for random recursive trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897163)