Essler Krauth 2023

From Werner KRAUTH

Revision as of 15:19, 18 July 2024 Werner (Talk | contribs) ← Previous diff		Current revision Werner (Talk | contribs)
Line 1:		Line 1:
-	'''F. H. L Essler, W. Krauth''' '''''Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains ''''' ''' arXiv:2306.13059 (2023)'''	+	'''F. H. L Essler, W. Krauth''' '''''Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains ''''' ''' Phys. Rev. X 14, 041035'''
-	'''Abstract'''	+	'''Popular Summary'''
-	Markov-chain Monte Carlo (MCMC), the field of stochastic algorithms built on the concept of sampling, has countless applications in science and technology. The overwhelming majority of MCMC algorithms are time-reversible and thus satisfy the detailed-balance condition, just like physical systems in thermal equilibrium. The underlying Markov chains typically display diffusive dynamics, which leads to a slow exploration of sample space. Significant speedups can be achieved by non-reversible MCMC algorithms exhibiting non-equilibrium dynamics, whose steady states exactly reproduce the target equilibrium states of reversible Markov chains. Such algorithms have had successes in applications but are generally difficult to analyze, resulting in a scarcity of exact results. Here, we introduce the “lifted” TASEP (totally asymmetric simple exclusion process) as a paradigm for non-reversible Markov chains. Our model can be viewed as a second-generation lifting of the reversible Metropolis algorithm	+	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.
-	on a one-dimensional lattice and is exactly solvable by an unusual kind of coordinate Bethe ansatz. We establish the integrability of the model and present strong evidence that the lifting leads to relaxation on shorter timescales than in the KPZ (Kardar–Parisi–Zhang) universality class.	+
		+	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.
	[http://arxiv.org/pdf/2306.13059 Electronic version (from arXiv)]		[http://arxiv.org/pdf/2306.13059 Electronic version (from arXiv)]
		+
		+	[https://doi.org/10.1103/PhysRevX.14.041035 Published version (open source)]
		+
		+	Paper now published in Physical Review X
		+
		+	==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]].

---

Current revision

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.