Theory and applications of the multivariate contraction method

• Antragsteller: Professor Dr. Ralph Neininger
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2012 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 230688343

Die Kontraktionsmethode wurde in den vergangenen 20 Jahren entwickelt, um schwache Konvergenz von Folgen von Zufallsvariablen zu zeigen, deren Verteilungen eine rekursive Beschreibung erlaubt. Motivation und Hauptanwendungsgebiet sind die probabilistische Analyse der Komplexität grundlegender rekursiver Algorithmen sowie das Studium asymptotischer Eigenschaften zufälliger Baummodelle. Die meisten dieser Anwendungen betreffen univariate (reelle) Folgen von Zufallsvariablen, wenn etwa die Komplexität durch einen reellen Parameter beschrieben wird. Die Theorie der Kontraktionsmethode wurde bereits teilweise für höhere Dimensionen und jüngst auch für funktionale Grenzwertsätze entwickelt. Im multivariaten Fall hauptsächlich, um Korrelationen zwischen eindimensionalen Größen zu studieren. Allerdings lassen sich selbst eindimensionale Parameter oft nicht rekursiv durch eine eindimensionale Rekursion beschreiben, sondern erfordern weitere Parameter, deren Beschreibung ebenfalls rekursiv erfolgt. Dies führt auf Systeme von Rekursionen, also multivariate Rekursionen.Ein systematisches Studium derartiger Systeme rekursiver Verteilungsgleichungen mit besonderem Blick auf Anwendungen ist Gegenstand dieses Projekts. Es soll insbesondere geklärt werden, unter welchen Wahrscheinlichkeits-Metriken sich die in den Anwendungen auftretende Klassen von Rekursionen behandeln lassen und welche Art von Rekusionen universell untersucht werden können.Beabsichtigte Anwendungen betreffen zum einen die Analyse von digitalen Baummodellen (digitaler Suchbaum, Trie, PATRICA-Trie) unter Markov-Quellen. Diese sind in der Praxis verwendete Datenstrukturen, deren Analyse häufig unter idealisierteren Modellannahmen als denen einer Markov-Quelle betrieben wurde. Es ist beabsichtigt, verschiedene grundlegende Parameter dieser Baummodelle mit einer multivariaten Version der Kontraktionsmethode im Markov-Fall auf asymptotische Normalität hin zu untersuchen. Dies verallgemeinert den viel untersuchten Fall von unabhängigen, identisch verteilten Symbolen zu einem in vielen Anwendungen (z.B. Text) realistischeren Modell.Ein weiteres Anwendungsgebiet stellen Polya-Urnenmodelle dar. Hier soll ein Zugang über die Kontraktionsmethode etabliert werden. Da sich die Dynamik der Anzahl von Kugeln einer Farbe in der Urne nicht univariat ausdrücken lässt, sondern von den Kugeln anderer Farben mit abhängt, kann eine rekursive Beschreibung hier nur multivariat erfolgen. Der Fall von zwei Farben ist hinsichtlich von Grenzverteilungen bereits (mit anderen Methoden) klassifiziert, jedoch sind nur wenige asymptotische Resultate für Urnen mit mehr als zwei Farben bekannt. Ein Zugang über eine multivariate Kontraktionsmethode erscheint flexibel genug, um auch den Fall von mehr Farben zu fassen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: USA
• Beteiligte Person: Professor Dr. Wojciech Szpankowski