Open Access

Tämur Ali Khan

• 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.
• Eine stochastische Analyse von Algorithmen kann dadurch motiviert sein, dass man einen randomisierten Algorithmus untersuchen möchte oder dadurch, dass man als stochastisches Modell Verteilungen auf den Mengen der Eingaben gleicher Länge voraussetzt. In beiden Fällen werden sich daraus ergebende zufällige Kenngrößen des Algorithmus untersucht. Besonderes Interesse gilt der Laufzeit. Dabei werden Charakteristika wie Erwartungswert, Varianz, Grenzwertsatz, Konvergenzraten und Tailschranken studiert. Obere Schranken für den rechten Tail sind neben dem Erwartungswert für die Laufzeit besonders wichtig, da man große Werte der Laufzeit mit möglichst großer Wahrscheinlichkeit ausschließen möchte. Im ersten Kapitel werden Spielbäume untersucht. Es wird die Worst-Case-Laufzeit von Snirs randomisierten Algorithmus spezifiziert und für diese der Erwartungswert, das asymptotische Verhalten der Varianz, ein Grenzwertsatz mit eindeutig charakterisiertem Grenzwert und Tailschranken ermittelt. Außerdem wird ein Grenzwertsatz für den Wert des zufälligen Spielbaumes unter Pearls Modell gezeigt. Im zweiten Kapitel werden obere und untere Tailschranken für den Wiener-Index von zufälligen binären Suchbäumen bewiesen. Im dritten Kapitel werden Tailschranken für die Generationengröße von superkritischen Multityp-Galton-Watson-Prozessen (mit Immigration), abhängig von deren Nachkommensverteilung hergeleitet. Dazu wird die Methode, die zu den Tailschranken aus dem ersten Kapitel geführt hat, verallgemeinert.