Zeiner, M. (2007). Funktionale Grenzwertsätze in der Kombinatorik [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-16994
functional limit theorems; generating functions; poisson process approximation; random structures; stochastic processes; combinatorics; saddle point method; singularity analysis
en
Abstract:
Wir betrachten kombinatorische Objekte der Größe n und zählen Unterstrukturen der Größe j (j=1..n). Für ein Objekt o sei X(j,o) diese Anzahl. Versehen wir die Menge der Objekte der Größe n mit einem Wahrscheinlichkeitsmaß, so werden die X(j,o) zu Zufallsvariablen X(j).<br />Für nichtganzzahlige j können wir beispielsweise linear interpolieren.<br />Skaliert man diesen Prozess noch geeignet, so kann man das Verhalten für n gegen unendlich untersuchen.<br />In dieser Arbeit studieren wir derartige Grenzwertsätze (sogenannte funktionale Grenzwertsätze), sowie Methoden, mit denen diese gezeigt werden können, und ihre Anwendungen in der Kombinatorik.<br />In Kapitel 1 geben wir die Definition stochastischer Prozesse und wichtige Eingenschaften an und stellen die behandelten Prozesse, insbesondere die Brown'sche Bewegung und davon abgeleitete Prozesse vor.<br />Da die betrachteten Prozesse ein Wahrscheinlichkeitsmaß auf den Räumen C[0,1], C[0,unendlich) oder D[0,1] induzieren, untersuchen wir die Konvergenz von Maßen speziell in diesen Räumen.<br />In Kapitel 2 werden Methoden vorgestellt, mit denen funktionale Grenzwertsätze gezeigt werden können: erzeugende Funktionen diskreter Zufallsvariablen und kombinatorischer Structuren, Sattelpunktmethode und Singularitätsanalyse zur Bestimmung der Koeffizienten und Poissonapproximation, um auftretende Abhängigkeiten zwischen Zufallsvariablen zu umgehen.<br />In Kapitel 3 zeigen wir, wo funktionale Grenzwertsätze in der Kombinatorik auftreten und wie diese mithilfe obiger Methoden bewiesen werden können. Zu den Beispielen zählen zufällige Bäume, Matrizen, Abbildungen, Permutationen, Mengenpartitionen und Urnenmodelle.<br />
de
Consider combinatorial objects of size n. Let X(j,o) the number of substructures of size j (j=1..n) of an object o. If we choose o randomly, then X(j,o) become random variables X(j). For non-integer we can define by linear interpolation a stochastic process. After suitable scaling we are able to study the behaviour of this process for n to infinity.<br />In chapter 1 we give an introduction to stochastic processes (especially we consider Gaussian processes, Brownian Motion, Brownian Bridge and Brownian Excursion) and study the convergence of probablitiy measures especially in C[0,1], C[0,infinity) and D[0,1].<br />In chapter 2 we present methodes which are useful to proof functional limit theorems in combinatorics: probability generating functions, generating functions of cmbinatorial structures, saddle point method and singularity analysis to determine their coefficients and poisson process approximation, which ca be used to avoid depedences of random variables which arise because of the combinatorial setup.<br />In chapter 3 we show how these methods can be used to proof functional limit theorems in combinatorics. Our examples are random trees, random matrices, random mappings, random permutations, random set partitions and urn models.