Peskun-Tierney ordering for Markov chain and process Monte Carlo: beyond the reversible scenario

Christophe Andrieu, Samuel LivingstonearXiv 2019 · DOI · arXiv

Abstract

Historically, the time-reversibility of transitions or processes underpinning Markov chain Monte Carlo (MCMC) methods has played a key role in their development. The self-adjointness of associated operators, combined with classical functional analysis techniques on Hilbert spaces, has provided powerful tools to characterize and compare their performance. However, similar results for algorithms relying on non-reversible Markov processes have remained scarce. This paper demonstrates that for a specific class of non-reversible MCMC methods—currently of high interest in physics and statistics—it is possible to develop comparison results that closely mirror those available in the reversible scenario. These findings shed light on earlier literature, proving several conjectures and strengthening previous results regarding the efficiency of non-reversible processes.

Introduction

In the field of Markov chain Monte Carlo (MCMC), the Peskun-Tierney ordering has long served as the "gold standard" for comparing the efficiency of reversible Markov chains. If one reversible transition is "larger" than another in a specific operator sense, it is guaranteed to produce estimators with lower asymptotic variance. While this theoretical framework is robust, it relies heavily on the property of reversibility (detailed balance), which allows mathematicians to treat Markov operators as self-adjoint.

In practice, however, non-reversible chains—those that do not satisfy detailed balance—often outperform their reversible counterparts. By avoiding the "backtracking" inherent in random walks, these processes explore the target distribution more efficiently. Despite their empirical success, the mathematical tools required to compare non-reversible algorithms have been historically limited, often forcing researchers to rely on case-by-case simulations rather than unified theory. This paper bridges that gap by extending Peskun-Tierney ordering to a broad class of non-reversible processes.

The Framework: $(\mu, Q)$-Self-Adjointness

The authors identify a unifying property called $(\mu, Q)$-self-adjointness, also known as skewed detailed balance, which allows non-reversible chains to be analyzed with the same rigor as reversible ones.

The $Q$ Operator and Skewed Balance

The core of this framework is the $Q$ operator, an involution (or "flip"). In many physics-inspired algorithms, such as Hamiltonian Monte Carlo (HMC), this corresponds to a velocity reversal. While the chain itself is not reversible, it becomes "reversible-like" when the state is transformed by $Q$ at each step. Formally, these operators satisfy a skewed adjoint relationship: $P^* = QPQ$. This structure is present in a wide variety of modern algorithms, including the Zig-Zag process and Lifted MCMC.

Dirichlet Forms and Variance Ordering

By focusing on the "reversible parts" of these non-reversible operators, the authors utilize Dirichlet forms—a measure of the "energy" or movement of the chain. They prove that if the Dirichlet forms of two $(\mu, Q)$-self-adjoint operators can be ordered, then their asymptotic variances are also ordered. This provides a rigorous mathematical foundation for the intuition that suppressing random-walk behavior leads to superior estimation.

Key Theoretical Results

The paper establishes several landmark results for both discrete and continuous-time processes:

  1. General Ordering Theorems: The authors prove Theorem 2.9 (for discrete time) and Theorem 4.6 (for continuous time), establishing that the Peskun-Tierney ordering holds for $(\mu, Q)$-self-adjoint processes. This allows for the direct comparison of asymptotic variances without needing to compute them explicitly.
  2. Resolution of Conjectures: The framework is used to provide formal proofs for several long-standing conjectures. For instance, it rigorously confirms the optimality of specific "switching rates" in Lifted MCMC and validates Neal’s scheme for avoiding backtracking.
  3. Optimization of the Zig-Zag Process: For the Zig-Zag process—a popular Piecewise Deterministic Markov Process (PDMP)—the authors prove that partial momentum refreshment (infrequent velocity changes) is theoretically superior to full refreshment for reducing estimator variance.

Discussion and Future Directions

While this work provides a powerful tool for comparing the accuracy of MCMC estimators (asymptotic variance), it distinguishes this from the speed of convergence. In the reversible world, the "spectral gap" typically governs both. In the non-reversible world, the spectrum is complex, making the relationship between variance ordering and the rate of convergence to the target distribution more nuanced.

Furthermore, while $(\mu, Q)$-self-adjointness covers a significant portion of modern non-reversible MCMC, it is not universal. Future research may look toward even more general structures that do not rely on an involution $Q$. Nonetheless, this paper provides a vital unifying language for the MCMC literature, moving the field beyond the "security blanket" of reversibility and toward a more complete theoretical understanding of non-equilibrium sampling.

Summary updated

Abstract

Historically time-reversibility of the transitions or processes underpinning Markov chain Monte Carlo methods (MCMC) has played a key rôle in their development, while the self-adjointness of associated operators together with the use of classical functional analysis techniques on Hilbert spaces have led to powerful and practically successful tools to characterize and compare their performance. Similar results for algorithms relying on nonreversible Markov processes are scarce. We show that for a type of nonreversible Monte Carlo Markov chains and processes, of current or renewed interest in the Physics and Statistical literatures, it is possible to develop comparison results which closely mirror those available in the reversible scenario. We show that these results shed light on earlier literature, proving some conjectures and strengthening some earlier results.
BibTeX
@misc{andrieu2019peskun,
  author = {Christophe Andrieu and Samuel Livingstone},
  title = {{Peskun-Tierney ordering for Markov chain and process Monte Carlo: beyond the reversible scenario}},
  year = {2019},
  eprint = {1906.06197},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.06197},
}
Figure