Riegler, L. (2010). Analytische Behandlung von Urnenmodellen [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/159783
E104 - Institut für Diskrete Mathematik und Geometrie
-
Date (published):
2010
-
Number of Pages:
93
-
Keywords:
Urnenmodell; Polya-Eggenberger; Isomorphismus; Methode der Charakteristiken
de
Urn model; Polya-Eggenberger; Isomorphism; Method of characteristics
en
Abstract:
In der Diplomarbeit werden kombinatorisch-analytische Methoden zur Behandlung von Urnenmodellen untersucht. Grundlage ist eine Urne mit einer vorgegebenen Anzahl weißer und schwarzer Kugeln. Nach Ziehung einer zufälligen Kugel wird, abhängig von der Farbe, der Kugelstand der weißen und schwarzen Kugeln um einen festen Wert verändert. Die anfänglichen Anzahlen der Kugeln und die in einer 2x2-Übergangsmatrix zusammengefassten Übergangsregeln beschreiben ein Urnenmodell. Von Interesse ist dann die Verteilung der weißen und schwarzen Kugeln nach n Ziehungen bzw. wenn eine modellabhängige Abbruchbedingung erfüllt ist. Es werden hierzu in der Diplomarbeit zwei verschiedene Methoden untersucht: Für balancierte Übergangsmatrizen, bei denen die Gesamtanzahl der Kugeln zu jedem Zeitpunkt einen deterministischen Wert annimmt, wird die Isomorphismus-Methode angewandt. Dabei wird die Übergangsmatrix in ein isomorphes System von Differentialgleichungen übersetzt, aus deren Lösung man die erzeugende Funktion für die Anzahl weißer und schwarzer Kugeln gewinnen kann. Bei der zweiten Methode wird eine Rekursion für die Wahrscheinlichkeit, von einer Initialkonfiguration (n,m) ausgehend, schließlich in einen Absorptionspunkt (j,k) zu gelangen, aufgestellt. Für die daraus gebildete erzeugende Funktion, wird eine partielle Differentialgleichung hergeleitet, die über die Methode der Charakteristiken gelöst werden kann. Die vorgestellten Methoden finden Anwendung in der Biologie (zur Beschreibung von Populationsentwicklungen oder Seuchenausbreitungen), in der Physik (bei der Untersuchung des Ehrenfest-Modells für Gasdiffusion), bei der Behandlung kombinatorischer Probleme (Coupon-Collector Problem), sowie bei der Analyse von Algorithmen und Datenstrukturen.
In this diploma thesis, two different combinatorial-analytic methods for treating urn models are applied. At the beginning, a given number of white and black balls are in the urn. After drawing a random ball and examining its colour, a constant number of white and black balls is added or removed. In order to determine the distribution after n drawings or when reaching an absorbing state, the following two methods are applied: In balanced urn models, i.e. the total number of balls after n drawings is deterministic, it turns out, that the solution of an isomorphic system of differential equations is related to the generating function for the number of white and black balls. The second method is based on a recursion for the probability to eventually reach an absorbing state (j,k) given an initial configuration of n white and m black balls. The recursion yields a partial differential equation for the probability generating function, which can be solved using the method of characteristics. Urn models are, inter alia, applied in Biology (population dynamics, contagion models), Physics (Ehrenfest-Model for gas diffusion), Mathematics (Coupon-Collector problem) and the analysis of algorithms and data structures.
en
Additional information:
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers