Nonequilibrium steady-state dynamics of Markov processes on graphs

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\times d\times r^2$ tensor, where $r$ is the number of states per variable, and $d$ is the matrix-product bond dimension. While the method becomes exact in the large-$d$ limit, it typically provides highly accurate results even for small bond dimensions $d$. The $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$, 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.

7 pages main text, 7 pages appendix, 7 figures; improved presentation, additional appendix and figure on correlation times; published version

References in corpus (29)

• The density-matrix renormalization group in the age of matrix product states
• Epidemic processes in complex networks
• Efficient simulation of one-dimensional quantum many-body systems
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• Time-dependent variational principle for quantum lattices
• The Bethe lattice spin glass revisited
• Glassy dynamics of kinetically constrained models
• Voter Model on Heterogeneous Graphs
• The iTEBD algorithm beyond unitary evolution
• A message passing approach for general epidemic models
• Variational optimization algorithms for uniform matrix product states
• Infinite size density matrix renormalization group, revisited
• A message-passing approach for recurrent-state epidemic models on networks
• Calculus of continuous matrix product states
• Large deviations of cascade processes on graphs
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Tensor Networks contraction and the Belief Propagation algorithm
• Gauging tensor networks with belief propagation
• Matrix Product State Representations
• Block belief propagation algorithm for two-dimensional tensor networks
• A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
• A theory of non-equilibrium local search on random satisfaction problems
• Efficient tensor network simulation of quantum many-body physics on sparse graphs
• Matrix Product Belief Propagation for reweighted stochastic dynamics over graphs
• One-step replica symmetry breaking in the language of tensor networks
• The matrix product approximation for the dynamic cavity method
• Tensor Network Message Passing
• Loop Series Expansions for Tensor Networks
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference