Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs

Gesine Reinert, Nathan RossThe Annals of Applied Probability 2019 · DOI · arXiv

TL;DR

This paper introduces a new theoretical tool to approximate the behavior of complex systems of interacting random variables, like those found in statistical physics and network analysis. By bounding the "distance" between the true system's distribution and a simpler, independent one, they provide a way to estimate system properties with quantifiable error, especially in "high temperature" regimes.

What Problem Does This Paper Address?

Many real-world systems, from magnetic materials (Ising models) to social networks (exponential random graphs), are modeled using interacting random variables. The exact mathematical description of these systems, particularly their long-term behavior (stationary distribution), is often intractable due to complex dependencies and normalizing constants. A common heuristic is that if the system's underlying dynamics "mix" quickly (meaning it quickly forgets its initial state and approaches its typical behavior), then the variables behave almost independently. This paper aims to formalize this heuristic by providing a rigorous mathematical bound on how "close" the true, complex distribution is to an independent one, using the Wasserstein distance. This allows for more accurate approximations of system properties, like expected values of functions, with explicit error bounds.

Methods

The core of the paper is Theorem 2.1, which provides a general bound on the Wasserstein distance between two distributions of Bernoulli random variables. This bound depends on two key quantities:

  1. A measure of how fast the Glauber dynamics (a type of Markov chain used to explore the state space of the system) of one distribution mixes. This is captured by the p-norm of the influence matrix of the dynamics.
  2. A simple expectation related to the difference in probabilities of state transitions for the other distribution.

The authors leverage Stein's method, a powerful probabilistic technique for bounding errors in approximations, particularly for normal approximations. They adapt Stein's method to compare the generators of the Glauber dynamics for the two distributions being analyzed. Path coupling is also used to establish the contraction properties of the Markov chains, which are crucial for proving fast mixing.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and their application to general models like Ising models and exponential random graphs, rather than specific empirical datasets.

Key Insights and Ideas

  • Formalizing "Almost Independent": The paper provides a concrete mathematical framework to quantify the intuition that fast-mixing systems behave almost independently.
  • Glauber Dynamics as a Bridge: The mixing properties of Glauber dynamics are shown to be a direct link to the approximation quality. Faster mixing implies a better approximation.
  • Wasserstein Distance as a Metric: Using the Wasserstein distance provides a geometrically meaningful way to measure the difference between probability distributions.
  • High Temperature Regimes are Tractable: The "high temperature" assumption simplifies the analysis by ensuring certain contraction properties of the dynamics, making the approximation bounds more effective.
  • General Applicability: The main theorem is general enough to be applied to a wide range of models involving Bernoulli random variables, including those with complex dependencies.

Key Results

The paper presents a general theorem (Theorem 2.1) that bounds the Wasserstein distance between two distributions of Bernoulli random variables. This theorem is then applied to:

  • Ising Models: They derive an explicit error bound for approximating expectations of functions of random vectors in Ising models on fixed graphs, sharpening existing results. For example, in the Curie-Weiss model, they obtain an error bound of $O(|| \Delta h || \frac{\beta \sqrt{N}}{1 - \beta r/N})$ for $0 \le \beta < r/N$.
  • Exponential Random Graphs (ERGs): They provide bounds for ERGMs, showing that in the high-temperature regime, ERGMs are close to Erdős-Rényi random graphs. Specific results are given for cases involving 2-stars and triangles as subgraphs, with error bounds depending on parameters like $n$ (number of vertices) and $\beta$ (model parameters). For instance, for a triangle subgraph and $| \beta_2 | < 1/3$, the error is bounded by $O(|| \Delta h || \frac{|\beta_2|}{\sqrt{n-2}})$.

Limitations and Future Work

  • High Temperature Restriction: The current results are primarily applicable to "high temperature" regimes, where the dynamics are guaranteed to mix fast. Analyzing low-temperature regimes, where mixing can be very slow, remains a significant challenge.
  • Explicit Constants: While the bounds are quantitative, some constants are not explicitly computed, which can limit direct numerical application in certain cases.
  • Generalization to Other Models: Extending the framework to models with variables beyond Bernoulli or to different types of dynamics could be a fruitful direction.
  • Connecting Complexity and Mixing: The authors suggest exploring the connection between measures of complexity (like Gaussian width) and fast mixing more deeply.
  • Low Temperature Analysis: The paper notes that in low-temperature regimes, fast mixing might occur for the measure conditioned to be in a "good" neighborhood. Investigating the behavior of conditional Glauber dynamics at the boundary of these regions is a challenging but important area for future work.

Summary updated

Abstract

We provide a general bound on the Wasserstein distance between two arbitrary distributions of sequences of Bernoulli random variables. The bound is in terms of a mixing quantity for the Glauber dynamics of one of the sequences, and a simple expectation of the other. The result is applied to estimate, with explicit error, expectations of functions of random vectors for some Ising models and exponential random graphs in “high temperature” regimes.
BibTeX
@article{reinert2019approximating,
  author = {Gesine Reinert and Nathan Ross},
  title = {{Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs}},
  journal = {The Annals of Applied Probability},
  year = {2019},
  doi = {10.1214/19-aap1478},
}
Figure