A functional limit law for the profile of plane-oriented recursive trees.

Abstract

We give a functional limit law for the normalized profile of random plane-oriented recursive trees. The proof uses martingale convergence theorems in discrete and continuous-time. This complements results of Hwang (2007).

Keywords

• plane-oriented recursive trees
• random trees
• profile of trees
• preferential attachment
• branching random walk
• martingales
• analysis of algorithms
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-ds] mathematics [math]/dynamical systems [math.ds]
• [math.math-co] mathematics [math]/combinatorics [math.co]