Perfect simulation of processes with long memory: A "coupling into and from the past" algorithm 1. Issue 2 (18th March 2014)

• Record Type: Journal Article
• Authors: Garivier, Aurélien
• Is Part Of: Random structures & algorithms. Volume 46:Issue 2(2015)
• Page Start: 300
• Page End: 319
• Publication Date: 2014-03-18
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20527
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>We describe a new algorithm for the perfect simulation of variable length Markov chains and random systems with perfect connections. This algorithm, which generalizes Propp and Wilson's simulation scheme, is based on the idea of coupling into and from the past. It improves on existing algorithms by relaxing the conditions on the kernel and by accelerating convergence, even in the simple case of finite order Markov chains. Although chains of variable or infinite order have been widely investigated for decades, their use in applied probability, from information theory to bio‐informatics and linguistics, has recently led to considerable renewed interest. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46, 300–319, 2015</p> </abstract>