Profile of asymmetric tries in the saddle point range

Abstract

The thesis is about the probability distribution of the profile of tries, whose entries are given by an asymmetric Bernoulli distribution. We therefore need tools from analytic combina-torics. Firstly we discuss properties of the Mellin transform. Secondly we will repeatedly poissonize and depoissonanize, necessitating the saddle point method. We analyze this method in detail and one focal point of the thesis is to be clear in how we apply it and to be comprehensive in checking its assumptions. We follow Park et al. to determine expected value and variance of the outer profile by a nested application of the saddle point method, where in one case we have infinitely many saddle points along a complex line. To meet this and other problem we use complex estimates, often concerning the Gamma function.Inboth cases this results in an asymptotic expression, which differs only by the occurrence of a different oszillating function. A similar approach helps to make progress toward a centrallimit theorem, by determining the characteristic functions. But to prove it, the oszillating functions need to be positive. We follow a method by Javanian and apply a Fourier transform, helping us to compare the different components. In this way, we show that the variance is positive for some set of parameters, proving a central theorem by filling a gap in the literature.

Die Arbeit beschreibt die Wahrscheinlichkeitsverteilung des Profils eines Tries, dessen Einträge durch eine asymmetrische Bernoulli Verteilung erzeugt wurden. Dafür sind Methoden der analytischen Kombinatorik notwendig. Einerseits besprechen wir Eigenschaften der Mellin-Transformation, andererseits führen wir wiederholt eine Poisson-Transformation und Rücktransformation durch, wofür wir die Sattelpunktmethode benötigen. Diese analysieren wir im Detail und ein Fokus der Arbeit ist es, deren Anwendung klar darzustellen und Vorraussetzungen zu überprüfen. Wir folgen Park et al. und bestimmen Erwartungswert und Varianz des äußeren Profils durch eine geschachtelte Anwendung der Sattelpunktmetho-de, wobei wir in einem Fall entlang einer komplexen Geraden unendlich viele Sattelpunkte antreffen. Diese und andere Probleme werden mit komplexen Abschätzungen, oft die Gamma-Funktion betreffend, behandelt. Es resultiert in beiden Fällen ein asymptotischer Ausdruck, der sich nur durch das Auftreten verschiedener oszillierender Terme unterscheidet. Eine ähnliche Herangehensweise hilft, durch das Bestimmen der charakteristischen Funktionen, erste Schritte zu einem zentralen Grenzwertsatz zu machen.Um diesen zu zeigen ist zusätzlich notwendig, dass die oben genannten oszillierenden Funktionen positiv sind. Wir folgen der Methodik von Javanian und wenden eine Fouriertransformation an, um die auftretenden Terme besser gegeneinander abschätzen zu können. Somit zeigen wir für manche Parameterwerte, dass die Varianz positiv ist und zeigen durch das Schließen dieser Lücke in der Literatur den zentralen Grenzwertsatz.