Perfect simulation of processes with long memory: A "coupling into and from the past" algorithm

Aurélien Garivier

TL;DR

This paper introduces a novel algorithm for "perfect simulation" of complex stochastic processes with long memory, generalizing existing methods. The new "coupling into and from the past" (CIAFTP) algorithm offers improved efficiency and relaxes restrictive conditions, making it applicable to a broader range of processes relevant in fields like information theory and bioinformatics.

What Problem Does This Paper Address?

Simulating the behavior of complex systems governed by probability is crucial in many scientific disciplines. For stationary Markov chains, "perfect simulation" techniques aim to generate exact samples from the stationary distribution, avoiding approximations. However, extending these techniques to processes with "long memory" (where the future state depends on a potentially infinite past) has been challenging. Existing methods for these long-memory processes often rely on strong assumptions about the process's properties (like continuity or regeneration) or require significant computational resources. This paper addresses the need for a more general and efficient perfect simulation algorithm for these complex, long-memory processes.

Methods

The core of this paper is the "coupling into and from the past" (CIAFTP) algorithm. This algorithm builds upon the idea of "coupling from the past" (CFTP) but introduces a novel approach by "coupling into" the past. Instead of solely relying on the process eventually coalescing from all possible initial states, CIAFTP exploits local coalescence and a recursive construction of "trie representations" of functions.

Key methodological contributions include:

  • Generalization of Propp-Wilson: The algorithm extends the seminal Propp-Wilson CFTP scheme to handle infinite-order Markov chains and general continuous transition kernels.
  • "Coupling Into and From the Past": This hybrid approach combines ideas of coupling from the past with a new strategy of incorporating information from the past dynamically.
  • Trie Representation: The algorithm leverages a compact representation of piecewise constant functions using tries. This allows for efficient manipulation of potentially infinite-dimensional state spaces using finite memory.
  • Update Rule Construction: A crucial part of the method is the construction of a specific "update rule" that ensures the algorithm's convergence and correctness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Local Coalescence is Powerful: The paper demonstrates that focusing on local coalescence, rather than global convergence, can significantly relax the conditions required for perfect simulation.
  • Tries as Finite Memory for Infinite Processes: The use of trie representations for piecewise constant functions is a key insight that allows the algorithm to manage infinite-dimensional state spaces efficiently. This is crucial for simulating long-memory processes.
  • CIAFTP Bridges Gaps: The CIAFTP algorithm effectively bridges the gap between methods for short-memory (like standard CFTP) and long-memory processes, offering a unified framework.
  • Relaxed Conditions for Convergence: The algorithm can simulate processes that are not necessarily regenerating or do not satisfy the strict continuity conditions of previous methods. This opens up simulation possibilities for a wider class of models.

Key Results

  • The paper presents a new perfect simulation algorithm (CIAFTP) that generalizes existing methods for long-memory processes.
  • The algorithm is shown to converge under less restrictive hypotheses than previously required.
  • For finite-order Markov chains, the algorithm's computational complexity is comparable to or better than existing methods.
  • The paper provides theoretical guarantees for the algorithm's convergence and correctness, including probabilistic bounds on stopping times.
  • An example of a non-regenerating kernel with slow convergence is used to illustrate the algorithm's applicability where other methods fail.

Limitations and Future Work

  • Computational Complexity Analysis: While the paper provides some analytical elements for computational complexity, a full bounding of the number of iterations and tree sizes for general kernels is noted as a challenging task.
  • Practical Implementation: The paper presents the algorithm as pseudo-code, acknowledging that a real implementation would require careful data structure design. A MATLAB implementation is mentioned as available online.
  • Future Work: The authors suggest that further work could explore more complicated variants of the example process and investigate how continuity is not strictly necessary for convergence in some cases. They also hint at the possibility of adapting the algorithm for processes where regeneration or rapid coupling coefficient decrease are not present.

Summary updated

Abstract

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.
BibTeX
@article{garivier2015perfect,
  author = {Aurélien Garivier},
  title = {{Perfect simulation of processes with long memory: A "coupling into and from the past" algorithm}},
  journal = {Random Struct. Algorithms},
  year = {2015},
  doi = {10.1002/rsa.20527},
}
Figure