Analyse von Algorithmen und minimalen Metriken

Prof. Dr. L. Rüschendorf, Institut für Mathematische Stochastik

Dr. M. Cramer, Stuttgart

Dipl.Math. Raph Neininger, Institut für Mathematische Stochastik

Bisherige Arbeiten:

Zur Analyse von Algorithmen, die in der Informatik und Stochastik angewendet werden, ist in einer kürzlichen Arbeit von Rachev und Rüschendorf (1992) eine neue Methode entwickelt worden. Es handelt sich um eine Kontraktionsmethode basierend, auf der Verwendung geeigneter minimaler Metriken. Mit Hilfe dieser Methode ist es gelungen, für eine Reihe von Algorithmen das asymptotische Verhalten gut zu beschreiben. Es wurden bisher verschiedene Such- und Sortierverfahren behandelt, sowie Algorithmen zur Auflösung von Kollisionen in Netzwerken (CRI), Algorithmen im Zusammenhang mit Garch-Modellen und andere. Insbesondere ergaben sich auch einfache Analysen für Bootstrapverfahren und ein einfacher Beweis für die Konvergenz von Algorithmen für iterative Funktionensysteme, die für das Image encoding von Interesse sind.

Aktuelle und zukünftige Arbeiten:

Aktuelle Themengebiete sind Anwendungen der Methode minimaler Metriken auf die Konstruktion multifraktaler Maße sowie auf die Untersuchung von Produkten zufälliger Matrizen. Es gibt thematische Zusammenhänge mit der fraktalen Kodierung von Bildern und mit der Untersuchung von GARCH-Modellen für Finanzdaten.

Veröffentlichungen:

(1)

S.T. Rachev, L. Rüschendorf:
Probability metrics and recursive algorithms, Advances Applied Probability 27, 770-799, 1995

(2)

P. Feldmann, S.T. Rachev, L. Rüschendorf:
Limiting distribution of the collision resolution interval, erscheint in: Statistica Neerlandica

(3)

P. Feldmann, S.T. Rachev, L. Rüschendorf:
Limit theorems for recursive algorithms, J. Computational and Appl. Mathematics 56, 169-182, 1995

(4)

L. Rüschendorf:
Convergence of the iterative proportional fitting procedure, Ann. Statistics 23, 1160-1174, 1995

(5)

M. Cramer, L. Rüschendorf:

Convergence of a branching type recursion, Ann. Inst. Henri Poincare 32, 725 - 741, 1996

(6)

M. Cramer:

Stochastische Analyse rekursiver Algorithmen mit idealen Metriken. Dissertation, Universität Freiburg

(7)

M. Cramer, L. Rüschendorf:

Analysis of recursive algorithms by the constraction method. In: Lectures Notes in Statistics 114, Athens Conference Proceedings, 18 - 33, 1996

(8)

M. Cramer:

A note concerning the limit distribution of the quicksort algorithmen. Informatique Theor. Appl. 30, 195 - 207, 1996

(9)

J.R. Hutchinson, L. Rüschendorf:

Random fractal measures via the contraction method Erscheint in: Indiana Univ. Math. J., 1998

(9)

J.R. Hutchinson, L. Rüschendorf:

Random fractals and probability metrics Preprint, 1998