Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T13:32:53.951Z Has data issue: false hasContentIssue false

Asymptotic Analysis of Hoppe Trees

Published online by Cambridge University Press:  30 January 2018

Kevin Leckey*
Affiliation:
Goethe University Frankfurt
Ralph Neininger*
Affiliation:
Goethe University Frankfurt
*
∗ Postal address: Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany.
∗ Postal address: Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Applied Probability Trust 2013