Filtern
Dokumenttyp
- diplomthesis (1)
- Dissertation (1)
Volltext vorhanden
- ja (2)
Gehört zur Bibliographie
- nein (2)
Schlagworte
- Verzweigungsprozess (2) (entfernen)
Institut
- Mathematik (2)
Mit den Small World Graphen stehen seit Ende der Neunzigerjahre Modelle für soziale und ähnliche Netzwerke, die im Vergleich zu Erdös-Rényi-Graphen stärker Cluster ausbilden, zur Verfügung. Wir betrachten die Konstruktion dieser Graphen und untersuchen zwei der Modelle genauer im Zusammenhang mit stochastischen Prozessen. Das stetige Modell betrachten wir hinsichtlich dem Abstand zweier Knoten. Der interessanteste Aspekt hierbei ist, dass man bei der Konstruktion des Graphen die entfernten Nachbarn mithilfe der Poissonverteilung wählt und in der Folge einen Yule-Prozess auf dem Graphen erhält. Auf der Bollobás-Chung Small World lassen wir den Kontaktprozess ablaufen und untersuchen diesen bezüglich seiner Überlebenswahrscheinlichkeit. Wir sehen, dass er auf diesem Graphen zwei Phasenübergänge aufweist. Oberhalb des ersten überlebt er für immer mit positiver Wahrscheinlichkeit, oberhalb des zweiten ist zudem der Knoten, auf dem der Kontaktprozess gestartet ist, stets mit positiver Wahrscheinlichkeit infiziert. Schließlich betrachten wir die Zeitdauer, die ein leicht modifizierter, superkritischer Kontaktprozess auf der Small World unter bestimmten Voraussetzungen überlebt. Die wesentliche Dynamik, die wir hierbei ausmachen können, ist, dass auf ein Absinken der Infektionen mit hoher Wahrscheinlichkeit wieder eine Verdopplung der Infektionen folgt.
Concentration of multivariate random recursive sequences arising in the analysis of algorithms
(2006)
Stochastic analysis of algorithms can be motivated by the analysis of randomized algorithms or by postulating on the sets of inputs of the same length some probability distributions. In both cases implied random quantities are analyzed. Here, the running time is of great concern. Characteristics like expectation, variance, limit law, rates of convergence and tail bounds are studied. For the running time, beside the expectation, upper bounds on the right tail are particularly important, since one wants to know large values of the running time not taking place with possibly high probability. In the first chapter game trees are analyzed. The worst case runnig time of Snir's randomized algorithm is specified and its expectation, asymptotic behavior of the variance, a limit law with uniquely characterized limit and tail bounds are identified. Furthermore, a limit law for the value of the game tree under Pearl's probabilistic modell is proved. In the second chapter upper and lower bounds for the Wiener Index of random binary search trees are identified. In the third chapter tail bounds for the generation size of multitype Galton-Watson processes (with immigration) are derived, depending on their offspring distribution. Therefore, the method used to prove the tail bounds in the first chapter is generalized.