• Zielgruppen
  • Suche
 

Wahrscheinlichkeitstheorie

Ein Forschungsschwerpunkt am Institut für Mathematische Stochastik im Bereich der Wahrscheinlichkeitstheorie ist das Gebiet der zufälligen diskreten Strukturen.

Analyse von Algorithmen

Schon bevor es brauchbare Computer gab, hat man sich neben der worst case-Analyse von Algorithmen auch mit der average case-Analyse beschäftigt, also Überlegungen dazu, was schlimmstenfalls passieren kann, durch Untersuchungen zum Verhalten „im Mittel“ bei zufälligem Input ergänzt. In den letzten Jahren hat es hier enorme Fortschritte gegeben, insbesondere bei Untersuchungen, bei denen es über Mittelwertbetrachtungen hinaus um die gesamte Verteilung der Laufzeit des Verfahrens oder seines Speicherbedarfs geht.

Probabilistische Kombinatorik

Will man Objekte eines bestimmten Typs zählen, beispielsweise die Permutationen einer bestimmten Grundmenge, deren Zyklenstruktur bestimmten Bedingungen genügt, oder die Anzahl der additiven Zerlegungen einer natürlichen Zahl, deren Summandenmenge keine Lücke hat, so kann dies häufig auf dem Umweg über eine gleichverteilte Zufallsvariable geschehen. Insbesondere bei der Asymptotik erweisen sich dann moderne wahrscheinlichkeitstheoretische Konzepte, beispielsweise Martingale, als sehr nützlich.

Zufall als Hilfsmittel

Bei randomisierten Algorithmen wird Zufall gezielt eingesetzt, um beispielsweise ein gutes Verhalten im Mittel zu erzwingen, oder um mit vorgegebener Wahrscheinlichkeit eine brauchbare Näherung bei `unlösbaren' Problemen zu erhalten. Klassisch sind Quicksort und Quickselect (Find), aber auch das Auffinden des Maximums einer Funktion kann von einer solchen Strategie profitieren.

Ausgewählte Publikationen:

  • On the silhouette of binary search trees
    (Grübel, R.)
    Annals of Applied Probability, 19, 1781-1802, 2009
  • Renewals for exponentially increasing lifetimes, with an application to digital search trees
    (Dennert, F. und Grübel, R.)
    Annals of Applied Probability, 19, 676-687, 2007
  • Monte Carlo algorithms for finding the maximum of a random walk with negative drift
    (Baringhaus, L. und Grübel, R.)
    Journal of Applied Probability, 43, 74-86, 2006
  • Zufällige binäre Bäume: Von der average-case Analyse zur Verteilungsasymptotik
    (Grübel, R.)
    Math. Semesterberichte, 53, 210-230, 2006
  • On the number of iterations required by von Neumann addition
    (Grübel, R. und Reimers, A.).
    Theor. Inform. Appl., 35, 187-206, 2001

Weitere Arbeiten zu diesen und anderen Themen, die am Institut für Mathematische Stochastik entstanden sind, teilweise in Kooperation mit anderen Wissenschaftlern aus dem In- und Ausland, sind auf der Homepage von R. Grübel zu finden. Dort können auch die pdf-Dateien zu den genannten Artikeln heruntergeladen werden.