Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs

DOI10.1214/23-aap1971arXiv2208.13153MaRDI QIDQ6126113

Dheeraj Nagaraj, Guy Bresler, Eshaan Nichani

Publication date: 9 April 2024

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.13153

zbMATH Keywords

Markov chainGlauber dynamicsexponential random graphsefficient sampling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Phase transitions in exponential random graphs
• Equi-energy sampler with applications in statistical inference and statistical mechanics
• Mixing time of exponential random graphs
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Exponential random graphs behave like mixtures of stochastic block models
• Fast initial conditions for Glauber dynamics
• Statistics of the two star ERGM
• Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
• Asymptotics for sparse exponential random graph models
• Stein's method for concentration inequalities
• Estimating and understanding exponential random graph models
• Graph limits and parameter testing
• Polynomial-Time Approximation Algorithms for the Ising Model
• Markov Graphs
• An Exponential Family of Probability Distributions for Directed Graphs
• Random cluster dynamics for the Ising model is rapidly mixing
• Swendsen--Wang Is Faster than Single-Bond Dynamics
• Ensemble Markov Chain Monte Carlo with Teleporting Walkers
• Simulating normalizing constants: From importance sampling to bridge sampling to path sampling