Limit laws for two distance-based indices in random recursive tree models

Abstract

In this paper, we derive several results related to total path length and Sackin index in two classes of random recursive trees. A limiting distribution of the normalized version of the Sackin index is given by the contraction method in random recursive trees. Also, we show the normalized total path length converges in L2 and almost surely to a limiting random variable in plane-oriented recursive trees via martingales.

Keywords

• recursive trees
• sackin index
• total path length
• contraction method
• martingale
• 05c05
• 60f05