From the archives
Perfect Simulation Of Processes With Long Memory: A 'Coupling Into And From The Past' Algorithm
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: Random Structures and Algorithms
Date: March, 2015
PageStart: 300
PageEnd: 319
Arxiv Number: 1106.5971
Hal Number: 00798388
Authors: Aurélien Garivier
Abstract: We describe a new algorithm for the perfect simulation of
variable length Markov chains and random systems with perfect connections. This algorithm
generalizes Propp and Wilson's simulation scheme, and is based on the idea of coupling into
and from the past. It improves on existing algorithms by relaxing the conditions required on
the kernel and by accelerating convergence, even in the simple case of finite order Markov
chains. Chains of variable or infinite order are an old object of consideration that raised
considerable interest recently because of its applications in applied probability, from
information theory to bio-informatics and linguistics.
Direct link: DOI: 10.1002/rsa.20527
Issue: 2
Volume: 46
Keywords:
