2012/02/11 by Kevin Leckey, Leckey, Kevin, Ralph Neininger +1
Computer Science · Mathematics · #60C05 (Primary) 60G42 #60F05 #68R05 (Secondary) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DM #math.PR #msc:60C05 #msc:60F05 #msc:60G42 #msc:68R05
paper · pdf · doi:10.48550/arxiv.1202.2439
arxiv created 2012/07/05 · arxiv updated 2012/07/06
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 ϑ>0, a given fixed parameter, all other nodes have weight 1. This resembles the stochastic dynamic of Hoppe's urn. For ϑ=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→ ∞. Mainly expectations, variances and asymptotic distributions of these parameters are derived.