Iterated Random Functions
SIAM ReviewPublished 1 January 1999
Persi Diaconis, David A. Freedman
Citations472
SJR quartileQ1
SJR score3.02
SNIP5.22
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Survey of iterated random functions offers a method for studying the steady state distribution of a Markov chain, and presents useful bounds on rates of convergence in a variety of examples.
Abstract
Iterated random functions are used to draw pictures or simulate large Ising models, among other applications. They offer a method for studying the steady state distribution of a Markov chain, and give useful bounds on rates of convergence in a variety of examples. The present paper surveys the field and presents some new examples. There is a simple unifying idea: the iterates of random Lipschitz functions converge if the functions are contracting on the average.
Keywords
Computer ScienceMathematics
Markov Chains and Stochastic Stability
5,130 Citations1993Sean Meyn, Richard L. Tweedie
This second edition reflects the same discipline and style that marked out the original and helped it to become a classic: proofs are rigorous and concise, the range of applications is broad and knowledgeable, and key ideas are accessible to practitioners with limited mathematical background.
The Annals of StatisticsA Bayesian Analysis of Some Nonparametric Problems
4,812 Citations1973Thomas S. Ferguson
The Annals of Mathematical StatisticsThe Existence of Probability Measures with Given Marginals
1,335 Citations1965Volker Strassen
Transactions of the American Mathematical SocietyNoncommuting random products
946 Citations1963Harry Furstenberg
Springer series in statisticsMonte Carlo Methods in Bayesian Computation
919 Citations2000Ming‐Hui Chen, Qi-Man Shao +1 more
The Annals of Applied ProbabilityImplicit Renewal Theory and Tails of Solutions of Random Equations
556 Citations1991Charles M. Goldie
Advances in Applied ProbabilityOn a stochastic difference equation and a representation of non–negative infinitely divisible random variables
482 Citations1979Wim Vervaat
The Annals of ProbabilityStrict Stationarity of Generalized Autoregressive Processes
412 Citations1992Philippe Bougerol, Nico Picard
American Journal of MathematicsOn a Family of Symmetric Bernoulli Convolutions
396 Citations1939P. Erdös
The Annals of Mathematical StatisticsOn Asymptotic Distributions of Estimates of Parameters of Stochastic Difference Equations
378 Citations1959T. W. Anderson
Advances in Applied ProbabilityThe stochastic equation <i>Y<sub>n</sub></i><sub>+1</sub>=<i>A<sub>n</sub>Y<sub>n</sub> + B<sub>n</sub></i> with stationary coefficients
305 Citations1986Andreas Brandt
The Annals of Mathematical StatisticsOn the Asymptotic Behavior of Bayes' Estimates in the Discrete Case
245 Citations1963David A. Freedman
Transactions of the American Mathematical SocietyArithmetic properties of Bernoulli convolutions
234 Citations1962Adriano M. Garsia
Journal of the Royal Statistical Society Series B (Statistical Methodology)Bayesian Nonparametric Inference for Random Distributions and Related Functions
233 Citations1999Stephen G. Walker, Paul Damien +2 more
Journal of AlgorithmsHow to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
211 Citations1998James Propp, David B. Wilson
Algorithms for generating a random sample from the state space of a Markov chain in accordance with the steady-state probability law of the chain are given, improving on earlier results and exploiting the duality between the two problems.
Mathematical Research LettersAbsolute Continuity of Bernoulli Convolutions, A Simple Proof
180 Citations1996Yuval Peres, Boris Solomyak
The Annals of Applied ProbabilityAn interruptible algorithm for perfect sampling via Markov chains
176 Citations1998James Allen Fill
The Annals of ProbabilityRandom walks and hyperplane arrangements
157 Citations1998Kenneth S. Brown, Persi Diaconis
Transactions of the American Mathematical SocietySelf-similar measures and intersections of Cantor sets
141 Citations1998Yuval Peres, Boris Solomyak
The Annals of StatisticsDistribution Functions of Means of a Dirichlet Process
135 Citations1990Donato Michele Cifarelli, Eugenio Regazzini
Pacific Journal of MathematicsMeasurable sets of measures
132 Citations1964Lester E. Dubins, David A. Freedman
Advances in Applied ProbabilityA new class of markov processes for image encoding
129 Citations1988Michael F. Barnsley, John H. Elton
BernoulliCharacterization Results and Markov Chain Monte Carlo Algorithms Including Exact Simulation for Some Spatial Point Processes
100 Citations1999Olle Häggström, M. N. M. van Lieshout +3 more
A two-component Gibbs sampler is devised, which can be used for fast and exact simulation by extending the recent ideas of Propp and Wilson, and a Swendsen-Wang type algorithm is introduced.
The Annals of Mathematical StatisticsAsymptotic Behavior of Bayes' Estimates
95 Citations1964Jasper H. Fabius
Stochastic Processes and their ApplicationsA multiplicative ergodic theorem for lipschitz maps
91 Citations1990John H. Elton
Journal of Theoretical ProbabilityExplicit stationary distributions for compositions of random functions and products of random matrices
87 Citations1991Jean-Fran�ois Chamayou, G�rard Letac
The Annals of ProbabilityThe random difference equation $X\sb n=A\sb nX\sb {n-1}+B\sb n$ in the critical case
81 Citations1997Martine Babillot, Philippe Bougerol +1 more
The Annals of ProbabilityErgodic Theory of Stochastic Petri Networks
77 Citations1992François Baccelli
This paper determines the conditions under which the existence of this regime is guaranteed and makes use of an associated stochastic recursive equation in order to construct its stationary and ergodic regime.
Counterexamples in Probability and Real Analysis
60 Citations1993G.L. Wise, Eric B Hall
Mathematical Proceedings of the Cambridge Philosophical SocietyLinear functionals and Markov chains associated with Dirichlet processes
45 Citations1989Paul D. Feigin, Richard L. Tweedie
Scandinavian Journal of StatisticsOn Exact Simulation of Markov Random Fields Using Coupling from the Past
44 Citations1999Olle Häggström, Karin Nelander
A general framework for exact simulation of Markov random fields using the Propp–Wilson coupling from the past approach is proposed, with emphasis is on situations lacking the monotonicity properties that have been exploited in previous studies.
Advances in Applied ProbabilityLimit laws for a stochastic process and random recursion arising in probabilistic modelling
44 Citations1995Svetlozar T. Rachev, Gennady Samorodnitsky
The Annals of ProbabilityCharacteristic Functions of Means of Distributions Chosen from a Dirichlet Process
42 Citations1984Hajime Yamato
Journal of Applied ProbabilityA Central Limit Theorem for Contractive Stochastic Dynamical Systems
37 Citations1998Martin Benda
The Annals of ProbabilityLocally Contractive Iterated Function Systems
28 Citations1999David Steinsaltz
FractalsA MULTIFRACTAL ANALYSIS OF IFSP INVARIANT MEASURES WITH APPLICATION TO FRACTAL IMAGE GENERATION
26 Citations1996José Manuel Gutiérrez, Andrés Iglesias +1 more
This paper shows the equivalence between an IFSP and a linear dynamical system driven by a white noise, and uses a multifractal analysis to obtain scaling properties of the resulting invariant measures, working within the framework of dynamical systems.
Bulletin of the London Mathematical SocietyOn Representations of Markov Chains by Random Smooth Maps
18 Citations1991Anthony Quas
IBM Systems JournalElements of queuing theory for system design
18 Citations1975Arnold O. Allen
The author provides a working familiarity with extended principles of queuing and application to system performance estimation through the use of worked out examples.
Annales de l’institut FourierOn continuous collections of measures
13 Citations1970Robert Blumenthal, Harry H. Corson
Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale, toute copie ou impressions de ce fichier doit contenir la présente mention de copyright.
Probability Theory and Related FieldsZeno's walk: A random walk with refinements
6 Citations1997David Steinsaltz