Probability metrics and recursive algorithms
- 1 September 1995
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 27 (3) , 770-799
- https://doi.org/10.2307/1428133
Abstract
It is shown by means of several examples that probability metrics are a useful tool to study the asymptotic behaviour of (stochastic) recursive algorithms. The basic idea of this approach is to find a ‘suitable' probability metric which yields contraction properties of the transformations describing the limits of the algorithm. In order to demonstrate the wide range of applicability of this contraction method we investigate examples from various fields, some of which have already been analysed in the literature.Keywords
This publication has 27 references indexed in Scilit:
- Rate of Convergence for Sums and Maxima and Doubly Ideal MetricsTheory of Probability and Its Applications, 1993
- The Continuum random tree II: an overviewPublished by Cambridge University Press (CUP) ,1991
- Stochastik für InformatikerPublished by Springer Nature ,1990
- Rates for the CLT Via New Ideal MetricsThe Annals of Probability, 1989
- Estimates of the Rate of Convergence for Max-Stable ProcessesThe Annals of Probability, 1989
- New results on the size of triesIEEE Transactions on Information Theory, 1989
- On a relationship between Uspensky's theorem and poisson approximationsAnnals of the Institute of Statistical Mathematics, 1988
- Stochastische Modelle in der InformatikPublished by Springer Nature ,1986
- Fundamentals of the Average Case Analysis of Particular AlgorithmsPublished by Springer Nature ,1984
- Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional SpacesTheory of Probability and Its Applications, 1977