A Propp-Wilson perfect simulation scheme for processes with long memory

Aurélien Garivier

Abstract

Generating exact samples from stochastic processes with infinite memory presents a significant challenge in statistics and physics. Traditional perfect simulation methods, such as the Propp-Wilson "Coupling From The Past" (CFTP) algorithm, often struggle with the "curse of dimensionality" or rely on restrictive regeneration conditions. This paper introduces the Coupling Into and From The Past (CIAFTP) algorithm. By representing the state space as a set of functions mapped onto tree-based data structures (tries), CIAFTP achieves perfect simulation through local coalescence rather than global resets. This approach works under broader mathematical conditions and demonstrates superior efficiency for processes with slow memory decay.

Introduction

In many scientific domains, from bioinformatics to information theory, we encounter processes where the future depends on an infinitely long history. Sampling from the stationary distribution of such "chains of infinite order" is notoriously difficult. Standard Markov Chain Monte Carlo (MCMC) methods suffer from unknown "burn-in" times, while existing perfect simulation techniques often require the process to occasionally "forget" its entire history—a property known as regeneration.

The CIAFTP algorithm moves beyond these limitations. It addresses the problem of infinite memory by focusing on local coalescence: identifying when specific suffixes of the past, rather than the entire history, are sufficient to determine the next state.

The CIAFTP Algorithm: Tries and Tree-Based States

The core innovation of CIAFTP is the use of tries (prefix trees) to manage the infinite state space. Instead of tracking a single value, the algorithm tracks a function that maps any possible infinite past to a current state.

Figure 1: A prefix tree (trie) structure used to represent suffixes of the past. The nodes represent specific sequences, allowing the algorithm to "look back" only as far as necessary.

These functions are represented as tree structures where each node corresponds to a specific suffix of the past. The algorithm employs a specific update rule, $\phi_P$, which is piecewise constant. This means that for any realization, the rule only needs to examine a finite portion of the past to make a deterministic update, even if the underlying process theoretically has infinite memory.

Local Coalescence and Efficiency

Previous methods relied heavily on the Harris condition, which requires a guaranteed "reset" point where the process loses all memory. CIAFTP weakens this requirement. It succeeds as long as paths eventually merge (coalesce) locally.

Figure 6: Representation of the state function f as a tree. The equality demonstrates local coalescence, where a complex tree (left) can be simplified (right) because different past sequences lead to the same outcome.

By treating the state as a "tree of possibilities," the algorithm avoids the exponential explosion of state spaces common in large-order Markov chains. It iteratively "couples into the past" to build deeper trees and "from the past" to propagate updates until the tree collapses into a single certain value.

Key Results and Theoretical Bounds

The paper validates CIAFTP using a synthetic non-regenerating kernel on a binary alphabet—a "stress test" where memory decay is so slow that traditional regeneration-based methods fail. Key findings include:

  • Broader Applicability: CIAFTP converges under much weaker assumptions than previous schemes, enabling the simulation of previously "un-simulatable" chains.
  • Computational Tractability: The author provides probabilistic upper bounds on the "stopping time" (the required look-back depth) and the size of the trees, ensuring the algorithm is practical for implementation.
  • Efficiency: By exploiting partial memory loss, the algorithm generally requires fewer iterations than standard Propp-Wilson approaches for high-order chains.

Conclusion and Future Work

While CIAFTP represents a major advancement, challenges remain. The current proof assumes a continuous transition kernel, and extending the theory to non-continuous "jump" processes is a key area for future research. Additionally, optimizing these tree structures for massive alphabets, such as those found in genomic sequence modeling, will be crucial for real-world applications.

Summary updated

BibTeX
@article{garivier2015propp,
  author = {Aurélien Garivier},
  title = {{A Propp-Wilson perfect simulation scheme for processes with long memory}},
  journal = {Random Struct. Algorithms},
  year = {2015},
  doi = {10.1002/rsa.20527},
}
Figure