pith. sign in

arxiv: 1202.2439 · v3 · pith:6BZW6JIVnew · submitted 2012-02-11 · 🧮 math.PR · cs.DM

Asymptotic analysis of Hoppe trees

classification 🧮 math.PR cs.DM
keywords treenodehoppenodesanalyzeasymptoticexistingrandom
0
0 comments X
read the original abstract

We introduce and analyze a random tree model associated to Hoppe's urn. The tree is built successively by adding nodes to the existing tree when starting with the single root node. In each step a node is added to the tree as a child of an existing node where these parent nodes are chosen randomly with probabilities proportional to their weights. The root node has weight $\vartheta>0$, a given fixed parameter, all other nodes have weight 1. This resembles the stochastic dynamic of Hoppe's urn. For $\vartheta=1$ the resulting tree is the well-studied random recursive tree. We analyze the height, internal path length and number of leaves of the Hoppe tree with $n$ nodes as well as the depth of the last inserted node asymptotically as $n\to \infty$. Mainly expectations, variances and asymptotic distributions of these parameters are derived.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.