论文标题
马尔可夫链的亚电势混合：有效抽样低温指数随机图
Metastable Mixing of Markov Chains: Efficiently Sampling Low Temperature Exponential Random Graphs
论文作者
论文摘要
在本文中，我们考虑了从低温指数随机图模型（ERGM）进行采样的问题。通常的方法是通过马尔可夫链蒙特卡洛（Monte Carlo），但Bhamidi等人。表明，由于亚稳态状态，任何当地的马尔可夫链都遭受了指数较大的混合时间。相反，我们考虑了亚稳态混合，这是相对于固定分布的近似混合的概念，事实证明这足以仅在亚稳态的集合中混合。我们表明，当在$ g（n，p）$初始化$ p $的$ g（n，p）$初始化$ p $时，ERGM在任何温度下的Glauber动力学（除了较低维的临界参数集外），具有$ O（n^2 \ log n）$的亚稳态混合时间在总变量距离内$ \ \ \ \ \ \ \ fex（exp（n））$。
In this paper we consider the problem of sampling from the low-temperature exponential random graph model (ERGM). The usual approach is via Markov chain Monte Carlo, but Bhamidi et al. showed that any local Markov chain suffers from an exponentially large mixing time due to metastable states. We instead consider metastable mixing, a notion of approximate mixing relative to the stationary distribution, for which it turns out to suffice to mix only within a collection of metastable states. We show that the Glauber dynamics for the ERGM at any temperature -- except at a lower-dimensional critical set of parameters -- when initialized at $G(n,p)$ for the right choice of $p$ has a metastable mixing time of $O(n^2\log n)$ to within total variation distance $\exp(-Ω(n))$.
