Mixing Time of Conditional Two Star Exponential Random Graphs
Abstract
Two star exponential random graph models (ERGMs) are an interesting special case of both general ERGMs and mean-field Ising models. In this paper, we study two star ERGMs conditioning on the edge density p. We begin with an analytic characterization of the replica symmetric region, where the conditional model is close in cut distance to the Erdős--Rényi random graph G(n,p). We prove that this region is twice as large as the corresponding region for the unconditional model. To study refined properties of the conditional model, we then analyze the global Kawasaki algorithm for sampling from it. Within the replica symmetric region, and under the additional condition that 4βp(1−p)<0.5 when |p−1/2|≲ 0.4632, where β is the model parameter, we prove metastable fast mixing of the Kawasaki algorithm. As corollaries, we obtain a weak Poincaré inequality and use it to deduce concentration inequalities of optimal order for conditional subgraph counts. The additional condition 4βp(1−p)<1/2 if |p−1/2|≲ 0.4632 comes from our proof technique of contractive coupling. This bottleneck did not appear in previous studies applying the contractive coupling technique to unconditional ERGMs.
Related
- Exponential mixing time for the Davies dynamics of the quantum random energy model
- Fluctuations of subgraph counts in exponential random graphs
- Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
- Quantitative non-Gaussian and Gaussian approximation for exponential random graphs in the single-phase critical regime
- Near linear mixing of random-cluster Glauber dynamics on random regular graphs
BibTeX
@misc{fang2026mixing,
title = {{Mixing Time of Conditional Two Star Exponential Random Graphs}},
author = {Xiao Fang and Song-Hao Liu and Xiaolin Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14335},
eprint = {2609.14335},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14335},
}
RIS
TY - UNPB
TI - Mixing Time of Conditional Two Star Exponential Random Graphs
AU - Xiao Fang
AU - Song-Hao Liu
AU - Xiaolin Wang
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14335
UR - https://arxiv.org/abs/2609.14335
AB - Two star exponential random graph models (ERGMs) are an interesting special case of both general ERGMs and mean-field Ising models. In this paper, we study two star ERGMs conditioning on the edge density p. We begin with an analytic characterization of the replica symmetric region, where the conditional model is close in cut distance to the Erdős--Rényi random graph G(n,p). We prove that this region is twice as large as the corresponding region for the unconditional model. To study refined properties of the conditional model, we then analyze the global Kawasaki algorithm for sampling from it. Within the replica symmetric region, and under the additional condition that 4βp(1−p)<0.5 when |p−1/2|≲ 0.4632, where β is the model parameter, we prove metastable fast mixing of the Kawasaki algorithm. As corollaries, we obtain a weak Poincaré inequality and use it to deduce concentration inequalities of optimal order for conditional subgraph counts. The additional condition 4βp(1−p)<1/2 if |p−1/2|≲ 0.4632 comes from our proof technique of contractive coupling. This bottleneck did not appear in previous studies applying the contractive coupling technique to unconditional ERGMs.
ER -