Theory and applications of the multivariate contraction method
Final Report Abstract
In diesem Projekt wurde eine Reihe struktureller Ergebnisse zur Analyse von Komplexitäten rekursiver Algorithmen und Datenstrukturen unter zufälliger Eingabe erarbeitet sowie die Komplexität der Algorithmen RadixSort und RadixSelect, der Datenstruktur m-närer Suchbaum sowie die Besetzungszahlen in Pólya-Urnenmodelle stochastisch asymptotisch untersucht. Methodisch wurde eine multivariate Version der Kontraktionsmethode weiterentwickelt. Die Kontraktionsmethode ist ein Zugang, um schwache Konvergenz für Folgen von Zufallsvariablen zu zeigen, deren Verteilungen rekursive Beziehungen erfüllen. Die Idee besteht darin, die gegebene Rekursion nach Skalierung in eine Fixpunktgleichung für den Grenzwert zu übersetzen, deren Fixpunkt mittels einer Kontraktion durch den Banachschen Fixpunktsatz idenitifiziert wird. Eine überraschende Wendung des Projekt bestand darin, dass solch ein Zugang für die genannten Anwendungen RadixSort und Polya-Urnenmodelle zu unnatürlichen Einschränkungen führte. Deshalb wurde zudem eine Kontraktionsmethode für Systeme univariater, rekusiver Gleichungen entwickelt. Es stellte sich heraus, dass die Verwendung der Systeme zu stärkeren Ergebnissen führt und sich damit bei RadixSort und den Polya-Urnenmodelle der gesamte Parameterbereich abdecken lässt. Allerdings lassen sich nicht alle mulitivariaten Größen mit solch einem System fassen. Für die Komplexität von RadixSort konnten Erwatungswert und Varianz asymptotisch bestimmt sowie ein zentraler Grenzwertsatz gezeigt werden im Modell unabhängiger Eingabe-Strings, die von einer Markov-Quelle generiert werden. Dies ist ein allgemeineres und realistischeres Modell (etwa zur Modellierung von Text) im Vergleich zu den viel untersuchten Modellen mit Strings mit unabhängigen Komponenten. Für RadixSelect konnte unter demselben stochastischen Modell der Markov-Quelle ebenso die Komplexität für die wesentlichen Annahmen an den zu suchenden Rang asymptotisch untersucht werden. Für Polya-Urnenmodelle wurde ein neuer Zugang zur Analyse entwickelt, der auf der zeitdiskreten Einbettung des Urnenprozesses in passende zufällige Baummodelle beruht, woraus ein System zufälliger, rekursiver Gleichungen für die Kenngrößen abgeleitet wurde. Dies führt zumindest im Falle balanzierter 2 x 2 Urnen zu Grenzwertsatzen mit einfacherer Beschreibung der Grenzwerte als dies andere Methoden zuvor erlaubten. Der Zugang scheint großes Potential für Folgeuntersuchungen zu haben. Für m-näre Suchbaume wurde im stochastischen Modell von Daten mit gleichverteilten Rängen die Anzahl der Knoten sowie die Pfadlänge bivariat asymptotisch untersucht. Die Größen beschreiben Speicherplatzbedarf des Baumes sowie die Komplexität, den Baum zu generieren. Es wurden verschiedene Phasenübergänge für die Kovarianz der Größen sowie deren asymptotischer Verteilung gefunden.
Publications
- “Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model.,” Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 877–886, 2013
Leckey, K., Neininger, R. and W. Szpankowski
- “Analysis of radix selection on Markov sources.,” Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. (Eds. M. Bousquet-Mélou, M. Soria). DMTCS-HAL Proceedings series, pp. 253–264, 2014
Leckey, K., Neininger, R. and H. Sulzbach
- “Pólya Urns Via the Contraction Method.,” Combinatorics, Probability & Computing, vol. 23, pp. 1148–1186, 2014
Knape, M. and R. Neininger
(See online at https://doi.org/10.1017/S0963548314000364) - “Dependence and phase changes in random m-ary search trees.,” Random Structures and Algorithms, vol. 50, pp. 353–379, 2017
Chern, H.-H., Fuchs, M., Hwang, H.-K. and R. Neininger
(See online at https://doi.org/10.1002/rsa.20659) - “Process convergence for the complexity of Radix Selection on Markov sources.,” Stochastic Processes and their Applications
Leckey, K., Neininger, R. and H. Sulzbach
(See online at https://doi.org/10.1016/j.spa.2018.03.009)
