Asymptotische Eigenschaften von Hoppe-Bäumen

The Hoppe tree is a family of randomly growing tree models, where the growth dynamic is given by the evolution of the Hoppe urn as follows: The distinguished ball that initializes the Hoppe urn corresponds to the root of
The Hoppe tree is a family of randomly growing tree models, where the growth dynamic is given by the evolution of the Hoppe urn as follows: The distinguished ball that initializes the Hoppe urn corresponds to the root of the  Hoppe tree. In the Hoppe urn this balls has probability proportional to a parameter theta>0 to be drawn, all other balls have probability proportional to 1. Whenever a ball is drawn it is placed back to the urn together with a new ball which corresponds to a node being inserted in the Hoppe tree as a child of the node that corresponds to the ball drawn. For the special case theta=1 the Hoppe tree coincides with the random recursive tree. We give asymptotic results on mean, variance and limit laws for the depth of nodes, the height, the path length and the number of leaves of the Hoppe tree and clarify the dependence upon the parameter theta.
show moreshow less
Der Hoppe-Baum ist eine zufällig wachsende, diskrete Baumstuktur, wobei die stochastische Dynamik durch die Entwicklung der Hoppe Urne wie folgt gegeben ist: Die ausgezeichnete Kugel mit der die Hoppe Urne startet entspr
Der Hoppe-Baum ist eine zufällig wachsende, diskrete Baumstuktur, wobei die stochastische Dynamik durch die Entwicklung der Hoppe Urne wie folgt gegeben ist: Die ausgezeichnete Kugel mit der die Hoppe Urne startet entspricht der Wurzel des Hoppe Baumes. In der Hoppe Urne wird diese Kugel mit Wahrscheinlichkeit proportional zu einem Parameter theta>0 gezogen, alle anderen Kugeln werden mit Wahrscheinlichkeit proportional zu 1 gezogen. Wann immer eine Kugel gezogen wird, wird sie zusammen mit einer neuen Kugel in die Urne zurückgelegt, was in unserem Baum dem Einfügen eines neuen Kindes an den gezogenen Knoten entspricht. Im Spezialfall theta=1 erhält man einen zufälligen rekursiven Baum.
In der Arbeit werden Erwartungswerte, Varianzen und Grenzwertsätze für Tiefe, Höhe, Pfadlänge und die Anzahl der Blätter gegeben.
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Kevin Leckey
URN:urn:nbn:de:hebis:30:3-242142
Referee:Ralph Neininger, Anton Wakolbinger
Advisor:Ralph Neininger
Document Type:Master's Thesis
Language:German
Date of Publication (online):2012/01/22
Year of first Publication:2012
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Granting Institution:Johann Wolfgang Goethe-Univ.
Date of final exam:2011/08/01
Release Date:2012/01/22
Pagenumber:40
HeBIS PPN:289760917
Institutes:Mathematik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $