Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.19100 · SciPost Physics

Nonequilibrium steady-state dynamics of Markov processes on graphs

Stefano Crotti, Thomas Barthel, Alfredo Braunstein

Published Aug 18, 2025• 2 citations
arXivHTMLPDF

Abstract

We propose an analytic approach for the steady-state dynamics of Markov processes on locally tree-like graphs. It is based on time-translation invariant probability distributions for edge trajectories, which we encode in terms of infinite matrix products. For homogeneous ensembles on regular graphs, the distribution is parametrized by a single d× d× r^2 d × d × r 2 tensor, where r r is the number of states per variable, and d d is the matrix-product bond dimension. While the method becomes exact in the large- d d limit, it typically provides highly accurate results even for small bond dimensions d d . The d^2r^2 d 2 r 2 parameters are determined by solving a fixed point equation, for which we provide an efficient belief-propagation procedure. We apply this approach to a variety of models, including Ising-Glauber dynamics with symmetric and asymmetric couplings, as well as the SIS model. Even for small d d , the results are compatible with Monte Carlo estimates and accurately reproduce known exact solutions. The method provides access to precise temporal correlations, which, in some regimes, would be virtually impossible to estimate by sampling.

DOI
10.21468/scipostphys.19.2.045

Related papers

Matrix product algorithm for stochastic dynamics on networks applied to nonequilibrium Glauber dynamics

Thomas Barthel, Caterina De Bacco, Silvio Franz

We introduce and apply an efficient method for the precise simulation of stochastic dynamical processes on locally treelike graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, our approach is based on a matrix product approximation of the so-called edge messages-conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both single instances as well as the thermodynamic limit. We employ it to examine prototypical nonequilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.

arXiv:1508.03295•Physical review. E•Jan 29, 2018•20 citations

A matrix product algorithm for stochastic dynamics on locally tree-like graphs

Thomas Barthel, Caterina De Bacco, Silvio Franz

We describe and demonstrate an algorithm for the efficient simulation of generic stochastic dynamics of classical degrees of freedom defined on the vertices of a locally tree-like graph. Networks with cycles are treated in the framework of the cavity method. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, the algorithm is based on a matrix product approximation of the so-called edge messages -- conditional probabilities of vertex variable trajectories. The matrix product edge messages (MPEM) are constructed recursively. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. In contrast to Monte Carlo simulations, the approach has a better error scaling and works for both, single instances as well as the thermodynamic limit. As we demonstrate at the example of Glauber dynamics, due to the absence of cancellation effects, observables with small expectation values can be evaluated reliably, allowing for the study of decay processes and temporal correlations.

Bulletin of the American Physical Society•Aug 13, 2015•5 citations

The matrix product approximation for the dynamic cavity method

Thomas Barthel

Abstract Stochastic dynamics of classical degrees of freedom, defined on vertices of locally tree-like graphs, can be studied in the framework of the dynamic cavity method which is exact for tree graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, and other technical, biological, and social networks. The central objects in the cavity method are edge messages—conditional probabilities of two vertex variable trajectories. In this paper, we discuss a rather pedagogical derivation for the dynamic cavity method, give a detailed account of the novel matrix product edge message (MPEM) algorithm for the solution of the dynamic cavity equation as introduced in Barthel et al (2018 Phys. Rev . E 97 010104 (R)), and present optimizations and extensions. Matrix product approximations of the edge messages are constructed recursively in an iteration over time. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. Without truncations, the dynamics is exact. Data for Glauber–Ising dynamics shows a linear growth of computation costs in time. In contrast to Monte Carlo simulations, the approach has a much better error scaling. Hence, it gives for example access to low probability events and decaying observables like temporal correlations. We discuss optimized truncation schemes and an extension that allows to capture models which have a continuum time limit.

arXiv:1904.03312•Journal of Statistical Mechanics Theory and Experiment•Jan 1, 2020•12 citations

Exact results for an asymmetric annihilation process with open boundaries

Arvind Ayyer, Kirone Mallick

We consider a nonequilibrium reaction–diffusion model on a finite one-dimensional lattice with bulk and boundary dynamics inspired by the Glauber dynamics of the Ising model. We show that the model has a rich algebraic structure that we use to calculate its properties. In particular, we show that the Markov dynamics for a system of a given size can be embedded into the dynamics of systems of higher sizes. This remark leads us to devise a technique which we call the transfer matrix Ansatz that allows us to determine the steady-state distribution and correlation functions. Furthermore, we show that the disorder variables satisfy very simple properties and we give a conjecture for the characteristic polynomial of Markov matrices. Finally, we compare the transfer matrix Ansatz used here with the matrix product representation of the steady state of one-dimensional stochastic models.

arXiv:0910.0693•Journal of Physics A Mathematical and Theoretical•Jan 4, 2010•22 citations

Tensor-network algorithm for nonequilibrium relaxation in the thermodynamic limit

Yoshihito Hotta

We propose a tensor-network algorithm for discrete-time stochastic dynamics of a homogeneous system in the thermodynamic limit. We map a d-dimensional nonequilibrium Markov process to a (d+1)-dimensional infinite tensor network by using a higher-order singular-value decomposition. As an application of the algorithm, we compute the nonequilibrium relaxation from a fully magnetized state to equilibrium of the one- and two-dimensional Ising models with periodic boundary conditions. Utilizing the translational invariance of the systems, we analyze the behavior in the thermodynamic limit directly. We estimated the dynamical critical exponent z=2.16(5) for the two-dimensional Ising model. Our approach fits well with the framework of the nonequilibrium-relaxation method. Our algorithm can compute time evolution of the magnetization of a large system precisely for a relatively short period. In the nonequilibrium-relaxation method, one needs to simulate dynamics of a large system for a short time. The combination of the two provides a different approach to the study of critical phenomena.

arXiv:1512.06517•Physical review. E•Jun 22, 2016•6 citations

Matrix-Product Belief Propagation for continuous-state-space variables

Federico Florio, Alfredo Braunstein

Computation of observables in discrete stochastic, possibly conditioned, dynamics over large sparse networks is fundamental for a myriad of applications. The Matrix-Product Belief Propagation method allows a semi-analytical estimation of such observables in tree-like networks with a controlled error that depends on the bond dimension, that is the dimension of the employed square matrices. Its computational cost is linear in the time horizon and the network size for a large family of models with discrete degrees of freedom. Here, a generalization of this method to models with continuous or mixed continuous/discrete degrees of freedom is presented, using a tunable expansion in a Hilbert function basis. For a wide class of models, the computational cost of the method is linear in the network size with a prefactor that depends on the basis size and the bond dimension. The method's efficacy is demonstrated by employing a Fourier basis for a mixed continuous/discrete representation of the Kinetic Ising dynamics with real-valued random couplings, where intermediate "local fields" are treated as continuous. The accuracy of the method is verified via comparison with Monte Carlo simulations. For this model, we calculate time auto-correlations, time evolution of energy and magnetization, and finally we estimate the large deviation function of the magnetization at a given future time.

arXiv:2605.14522•May 14, 2026•0 citations
We propose an analytic approach for the steady-state dynamics of Markov processes on locally tree-like graphs. It is based on time-translation invariant probability distributions for edge trajectories, which we encode in terms of infinite matrix products. For homogeneous ensembles on regular graphs, the distribution is parametrized by a single d× d× r^2 d × d × r 2 tensor, where r r is the number of states per variable, and d d is the matrix-product bond dimension. While the method becomes exact in the large- d d limit, it typically provides highly accurate results even for small bond dimensions d d . The d^2r^2 d 2 r 2 parameters are determined by solving a fixed point equation, for which we provide an efficient belief-propagation procedure. We apply this approach to a variety of models, including Ising-Glauber dynamics with symmetric and asymmetric couplings, as well as the SIS model. Even for small d d , the results are compatible with Monte Carlo estimates and accurately reproduce known exact solutions. The method provides access to precise temporal correlations, which, in some regimes, would be virtually impossible to estimate by sampling.
We introduce and apply an efficient method for the precise simulation of stochastic dynamical processes on locally treelike graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, our approach is based on a matrix product approximation of the so-called edge messages-conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both single instances as well as the thermodynamic limit. We employ it to examine prototypical nonequilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.
We describe and demonstrate an algorithm for the efficient simulation of generic stochastic dynamics of classical degrees of freedom defined on the vertices of a locally tree-like graph. Networks with cycles are treated in the framework of the cavity method. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, the algorithm is based on a matrix product approximation of the so-called edge messages -- conditional probabilities of vertex variable trajectories. The matrix product edge messages (MPEM) are constructed recursively. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. In contrast to Monte Carlo simulations, the approach has a better error scaling and works for both, single instances as well as the thermodynamic limit. As we demonstrate at the example of Glauber dynamics, due to the absence of cancellation effects, observables with small expectation values can be evaluated reliably, allowing for the study of decay processes and temporal correlations.
Abstract Stochastic dynamics of classical degrees of freedom, defined on vertices of locally tree-like graphs, can be studied in the framework of the dynamic cavity method which is exact for tree graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, and other technical, biological, and social networks. The central objects in the cavity method are edge messages—conditional probabilities of two vertex variable trajectories. In this paper, we discuss a rather pedagogical derivation for the dynamic cavity method, give a detailed account of the novel matrix product edge message (MPEM) algorithm for the solution of the dynamic cavity equation as introduced in Barthel et al (2018 Phys. Rev . E 97 010104 (R)), and present optimizations and extensions. Matrix product approximations of the edge messages are constructed recursively in an iteration over time. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. Without truncations, the dynamics is exact. Data for Glauber–Ising dynamics shows a linear growth of computation costs in time. In contrast to Monte Carlo simulations, the approach has a much better error scaling. Hence, it gives for example access to low probability events and decaying observables like temporal correlations. We discuss optimized truncation schemes and an extension that allows to capture models which have a continuum time limit.
We consider a nonequilibrium reaction–diffusion model on a finite one-dimensional lattice with bulk and boundary dynamics inspired by the Glauber dynamics of the Ising model. We show that the model has a rich algebraic structure that we use to calculate its properties. In particular, we show that the Markov dynamics for a system of a given size can be embedded into the dynamics of systems of higher sizes. This remark leads us to devise a technique which we call the transfer matrix Ansatz that allows us to determine the steady-state distribution and correlation functions. Furthermore, we show that the disorder variables satisfy very simple properties and we give a conjecture for the characteristic polynomial of Markov matrices. Finally, we compare the transfer matrix Ansatz used here with the matrix product representation of the steady state of one-dimensional stochastic models.
We propose a tensor-network algorithm for discrete-time stochastic dynamics of a homogeneous system in the thermodynamic limit. We map a d-dimensional nonequilibrium Markov process to a (d+1)-dimensional infinite tensor network by using a higher-order singular-value decomposition. As an application of the algorithm, we compute the nonequilibrium relaxation from a fully magnetized state to equilibrium of the one- and two-dimensional Ising models with periodic boundary conditions. Utilizing the translational invariance of the systems, we analyze the behavior in the thermodynamic limit directly. We estimated the dynamical critical exponent z=2.16(5) for the two-dimensional Ising model. Our approach fits well with the framework of the nonequilibrium-relaxation method. Our algorithm can compute time evolution of the magnetization of a large system precisely for a relatively short period. In the nonequilibrium-relaxation method, one needs to simulate dynamics of a large system for a short time. The combination of the two provides a different approach to the study of critical phenomena.
Computation of observables in discrete stochastic, possibly conditioned, dynamics over large sparse networks is fundamental for a myriad of applications. The Matrix-Product Belief Propagation method allows a semi-analytical estimation of such observables in tree-like networks with a controlled error that depends on the bond dimension, that is the dimension of the employed square matrices. Its computational cost is linear in the time horizon and the network size for a large family of models with discrete degrees of freedom. Here, a generalization of this method to models with continuous or mixed continuous/discrete degrees of freedom is presented, using a tunable expansion in a Hilbert function basis. For a wide class of models, the computational cost of the method is linear in the network size with a prefactor that depends on the basis size and the bond dimension. The method's efficacy is demonstrated by employing a Fourier basis for a mixed continuous/discrete representation of the Kinetic Ising dynamics with real-valued random couplings, where intermediate "local fields" are treated as continuous. The accuracy of the method is verified via comparison with Monte Carlo simulations. For this model, we calculate time auto-correlations, time evolution of energy and magnetization, and finally we estimate the large deviation function of the magnetization at a given future time.