Probability metrics and recursive algorithms
- 1 June 1995
- journal article
- general applied-probability
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 27 (03) , 770-799
- https://doi.org/10.1017/s0001867800027142
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 18 references indexed in Scilit:
- The asymptotic contour process of a binary tree is a Brownian excursionStochastic Processes and their Applications, 1992
- The Continuum random tree II: an overviewPublished by Cambridge University Press (CUP) ,1991
- Estimates of the Rate of Convergence for Max-Stable ProcessesThe Annals of Probability, 1989
- On a relationship between Uspensky's theorem and poisson approximationsAnnals of the Institute of Statistical Mathematics, 1988
- A new class of markov processes for image encodingAdvances in Applied Probability, 1988
- On a functional equation arising in the analysis of a protocol for a multi-access broadcast channelAdvances in Applied Probability, 1986
- Analysis of a stack algorithm for random multiple-access communicationIEEE Transactions on Information Theory, 1985
- A simple heuristic approach to simplex efficiencyEuropean Journal of Operational Research, 1982
- Some Asymptotic Theory for the BootstrapThe Annals of Statistics, 1981
- On a stochastic difference equation and a representation of non–negative infinitely divisible random variablesAdvances in Applied Probability, 1979