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-53865
URL: http://www.freidok.uni-freiburg.de/volltexte/5386/


Schopp, Eva-Maria

Tail behaviour and martingale convergence of random recursive structures and algorithms

Martingalstrukturen in zufälligen Bäumen und Tail Schranken rekursiver Strukturen und Algorithmen

Dokument1.pdf (1.346 KB) (md5sum: 631763d7d6a638f6d08806861d2223b4)

Kurzfassung in Englisch

In the first part of this work we study exponential and polynomial tail bounds of random recursive structures and algorithms and give various criteria. In the second part a functional limit theorem for the profile of a class of trees, including binary search trees and random recursive trees, is proven. This result is obtained by embedding these discrete-time trees in a continuous-time weighted tree model and by using corresponding martingales. The third part is concerned with the proof of polynomial tail behaviour of the limit-profiles of part 2 of random recursive trees and binary search trees. We use asymptotics of Laplace transforms at zero and a connection to solutions of differential-difference equations to obtain this tail result.


Kurzfassung in Deutsch

Im ersten Teil der Arbeit untersuchen wir exponentielle und polynomielle tail Schranken für zufällige rekursive Strukturen und Algorithmen und geben verschiedene Kriterien an. Im zweiten Teil der Arbeit beweisen wir einen funktionalen Grenzwertsatz für die Profile von verschiedenen Bäumen, wie z.B. für den zufälligen binären Suchbaum oder den zufälligen rekursiven Baum. Dieses Resultat wird gezeigt, indem wir eine Einbettung der diskreten Bäume in ein zeitstetiges Baummodell mit Gewichten vornehmen und in diesem Zusammenhang auf Konvergenz entsprechender Martingale zurückgreifen. Der dritte Teil beschäftigt sich mit dem Nachweis von polynomiellem tail Verhalten für die Limes-Profile aus Teil 2 für den zufälligen binären Suchbaum und den zufälligen rekursiven Baum. Wir zeigen dies durch Asymptotiken der Laplacetransformierten und Differenzen-Differential-Gleichungen.


SWD-Schlagwörter: Algorithmus , Martingal , Fixpunkt
Freie Schlagwörter (deutsch): Profil , rekursiv
Freie Schlagwörter (englisch): tails , trees , differential-difference equation
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: 26.06.2008
Erstellungsjahr: 2008
Publikationsdatum: 01.07.2008
Indexliste