Tail Bounds for the Wiener Index of Random Trees

Abstract

Upper and lower bounds for the tail probabilities of the Wiener index of random binary search trees are given. For upper bounds the moment generating function of the vector of Wiener index and internal path length is estimated. For the lower bounds a tree class with sufficiently large probability and atypically large Wiener index is constructed. The methods are also applicable to related random search trees.

Keywords

• random trees
• wiener index
• [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-cg] computer science [cs]/computational geometry [cs.cg]