Essler Krauth 2023
From Werner KRAUTH
| Revision as of 01:08, 24 January 2025 Werner (Talk | contribs) ← Previous diff |
Revision as of 00:50, 25 November 2025 Werner (Talk | contribs) (→Further context) Next diff → |
||
| Line 16: | Line 16: | ||
| ==Further context== | ==Further context== | ||
| The Lifted TASEP is discussed in my [[BegRohu_Lectures_2024|2024 Beg Rohu Lectures]] on "The second Markov chain revolution", and a sample Python program can be found [[LiftedTASEPCompact.py|here]]. | The Lifted TASEP is discussed in my [[BegRohu_Lectures_2024|2024 Beg Rohu Lectures]] on "The second Markov chain revolution", and a sample Python program can be found [[LiftedTASEPCompact.py|here]]. | ||
| + | |||
| + | My [[Massoulie_et_al_2025|2025 paper with B. Massoulié, C. Erignoux and C. Toninelli]] provides a deeper theoretical analysis. | ||
Revision as of 00:50, 25 November 2025
F. H. L Essler, W. Krauth Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains Phys. Rev. X 14, 041035
Popular Summary Markov-chain Monte Carlo (MCMC) algorithms formulate the sampling problem for complex probability distributions as a simulation of fictitious physical systems in equilibrium, where all motion is diffusive and time reversible. But nonreversible algorithms can, in principle, sample distributions much more efficiently. In recent years, a class of “lifted” Markov chains has implemented this idea in practice, but the resulting algorithms are extremely difficult to analyze. In this work, we introduce an exactly solvable paradigm for nonreversible Markov chains.
Our paradigm, which we term the lifted totally asymmetric simple exclusion process (TASEP), describes a particular type of nonreversible dynamics for particles on a one-dimensional lattice. We show that this dynamics allows for polynomial speedups in particle number compared to the famous Metropolis MCMC algorithm. The lifted-TASEP dynamics is, in fact, faster than that of any other known class of models. To arrive at our conclusions, we combine exact methods from the theory of integrable models with extensive numerical simulations. In particular, we prove that the lifted TASEP is integrable and determine the scaling of its relaxation and mixing times with system size.
Our work opens the door to obtaining mathematically rigorous results for speedups of nonreversible MCMC algorithms, and more generally, of lifted Markov chains arising in interacting many-particle systems.
Electronic version (from arXiv)
Published version (open source)
Paper now published in Physical Review X
Further context
The Lifted TASEP is discussed in my 2024 Beg Rohu Lectures on "The second Markov chain revolution", and a sample Python program can be found here.
My 2025 paper with B. Massoulié, C. Erignoux and C. Toninelli provides a deeper theoretical analysis.
