Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-74728
URL: http://www.freidok.uni-freiburg.de/volltexte/7472/


Munsonius, Götz Olaf

Limit theorems for functionals of recursive trees

Grenzwertsätze für Funktionale rekursiver Bäume

Dokument1.pdf (1.311 KB) (md5sum: 8e3216104cbcd6514c62a9f72cdc5dc8)

Kurzfassung in Englisch

The first part is devoted to the analysis of random b-ary recursive trees with weighted edges. We investigate functionals related to distances with regard to limit theorems. We show central limit theorems for the depth of a random node and distances between two random nodes. Further, we prove limit theorems for the internal path length, the Wiener index and its generalisation -- the total Steiner k-distance -- with the aid of the contraction method using recursion formulae. To do this, the asymptotic expansion of the expectation of the considered functionals has to be determined.
Moreover, an upper tail bound for the distribution of the total Steiner k-distance is proved by considering the Laplace transform. A lower tail bound is shown for the Wiener index.

In the second part, the results for the tree model of the first part are transfered to the random linear recursive tree by choosing special edge weights. In particular, we obtain the asymptotic expansions of the expectations and limit theorems for the Wiener index of the plane-oriented recursive tree, and for the total Steiner k-distance as well as for the k-th internal path length of the random binary search tree, the random recursive tree and the plane-oriented recursive tree.


Kurzfassung in Deutsch

Gegenstand des ersten Teils der Arbeit ist ein zufälliger b-närer Baum mit gewichteten Kanten. Es werden Funktionale, die von den Abständen der Knoten abhängen, untersucht. Wir zeigen zentrale Grenzwertsätze für die Tiefe eines zufälligen Knotens und für den Abstand zwischen zwei zufälligen Knoten. Mit der Kontraktionsmethode werden Grenzwertsätze für die interne Pfadlänge, den Wiener Index und seine Verallgemeinerung, den totalen Steiner k-Abstand, bewiesen. Dazu wird zunächst die asymptotische Entwicklung des Erwartungswertes der betrachteten Funktionale bestimmt.
Desweiteren wird eine obere Tailschranke für die Verteilung des totalen Steiner k-Abstandes mit Hilfe der Laplace-Transformierten gezeigt. Eine untere Tailschranke wird für den Wiener Index bewiesen.

Im zweiten Teil werden durch eine spezielle Wahl der Kantengewichte die Ergebnisse für das Baummodell aus dem ersten Teil auf den zufälligen, linearen, rekusiven Baum übertragen. Dies liefert insbesondere die asymptotische Entwicklung der Erwartungswerte und Grenzwertsätze für den Wiener Index des zufälligen, planaren, geordneten Baumes, sowie für den totalen Steiner k-Abstand und die k-te interne Pfadlänge des zufälligen, binären Suchbaumes, des zufälligen, rekusiven Baumes und des zufälligen, planaren, geordneten Baumes.


SWD-Schlagwörter: Baum <Mathematik> , Rekursion , Grenzwertsatz , Steiner-Baum , Erwartungswert , Asymptotik
Freie Schlagwörter (deutsch): Distanz , Pfadlänge , Wiener Index , Tailschranke , Kontraktionsmethode
Freie Schlagwörter (englisch): distance , path length , Wiener index , tail bound , contraction method
MSC Klassifikation 60F05 , 60C05 , 05C12 , 05C05
Institut: Institut für Mathematische Stochastik
Fakultät: Fakultät für Mathematik und Physik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Erstgutachter: Rüschendorf, Ludger (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 12.04.2010
Erstellungsjahr: 2010
Publikationsdatum: 06.05.2010
Indexliste