Analysis of algorithms and minimal metrics

In papers by Rösler (1991, 1992) and Rachev and Rüschendorf (1990, 1995) a new method was developed for the analysis of algorithms used in computer science and stochastics. It is a contraction method based on the use of suitable minimal metrics. Using this method it was possible to describe the asymptotic behaviour for a number of algorithms. To date we have handled different search and sort methods as well as algorithms for the resolutions of collisions in networks (CRI), algorithms in the context of GARCH models, tree algorithms, quad-trees and others. In particular, we deduced simple analyses for bootstrap methods and an easy proof for the convergence of algorithms for iterative function systems used for image encoding. <BR> Current topics are the application of the method of minimal metrics to the construction of multifractal measures as well as the study of products of random metrics. Connections exist with the fractal encoding of images and with the exploration of GARCH models on financial data. The method is suited in particular for the analysis of tree algorithms. <BR> Staff member: Michael Cramer, Johannes Fehrenbach, Ralph Neininger

Phone: 0761/203-5665
Email: ruschen@stochastik.uni-freiburg.de

Start of project: 1992
End of project: 2001

Albert-Ludwigs-University Freiburg
Prof. Dr. Ludger Rüschendorf
Abteilung für Mathematische Stochastik
Prof. Dr. Ludger Rüschendorf
Ernst-Zermelo-Straße 1
79104 Freiburg
Germany

Phone: 0761/203-5664
Fax: 0761/203-5661
Email: sekretariat@stochastik.uni-freiburg.de
http://www.stochastik.uni-freiburg.de/rueschendorf
Actual Research Report

Analyse von Algorithmen, Konstruktion multifraktaler Maße, P

• Hutchinson J.R, Rüschendorf L: Random fractals and probability metrics. Advances of Appl. Prob., 2000; 32: 925-947.
• Hutchinson J.R, Rüschendorf L: Random fractal measures via the contraction method. Indiana Univ. Math. J., 1998; 47: 471-488.
• Cramer M: Convergence of a branching type recursion with non-stationary immigration. Metrika, 1997; 46 (3): 187-211.
• Cramer M: Stochastic analysis of the Merge-Sort algorithm. J. Random Struct. Algorithms, 1997; 1/11: 81-96.
• Feldman P, Rachev S.T, Rüschendorf L: Limiting distribution of the collision resolution interval. Statistica Neerlandica, 1997; 51: 1-22.
• Cramer M: A note concerning the limit distribution of the quicksort algorithm. RAIRO, Inform. Theor. Appl., 1996; 30: 195-207.
• Cramer M, Rüschendorf L: Analysis of recursive algorithms by the contraction method. In: Heyde, C.C. et al. (Hrsg.): Athens Conference on Applied Probability and Time Series Analysis. Athens, Greece, March 22-26, 1995. In Honor of J.M. Gani. Lecture Notes of Statistics, 114, Springer, 1996; 18-33.
• Cramer M, Rüschendorf L: Convergence of a branching type recursion. Ann. Inst. Henri Poincaré, 1996; 32: 725-741.
• Cramer M: Stochastische Analyse rekursiver Algorithmen mit idealen Metriken. Dissertation Universität Freiburg, 1995: p.283.
• Feldman P, Rachev S.T, Rüschendorf L.: Limit theorems for recursive algorithms. J. Comp. Appl. Mathematics, 1995; 56: 169-182.
• Rachev S.T, Rüschendorf L: Probability metrics and recursive algorithms. Adv. Appl. Prob., 1995; 27: 770-779.
• Rüschendorf L: Convergence of the iterative proportional fitting procedure. Ann. Statistics, 1995; 23: 1160-1174.