Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees

This paper studies the mixing time of the Glauber dynamics for the hard-core model assuming that the underlying graph is an arbitrary tree. In the hard-core model, we are given a graph $G=(V,E)$ and an activity $\lambda>0$. The model is defined on the collection of all independent sets of $G$ (regardless of size), which we denote as $\Omega$. Each independent set $\sigma\in\Omega$ is assigned a weight $w(\sigma)=\lambda^{|\sigma|}$ where $|\sigma|$ is the number of vertices contained in the independent set $\sigma$. The Gibbs distribution $\mu$ is defined on $\Omega$: for $\sigma\in\Omega$, let $\mu(\sigma)=w(\sigma)/Z$ where $Z=\sum_{\tau\in\Omega}w(\tau)$ is known as the partition function. When $\lambda=1$ then every independent set has weight one and hence the Gibbs distribution $\mu$ is the uniform distribution over (unweighted) independent sets.

Our goal is to sample from $\mu$ (or estimate $Z$) in time polynomial in $n=|V|$. Our focus is on trees. These sampling and counting problems are computationally easy on trees using dynamic programming algorithms. Nevertheless, our interest is to understand the convergence properties of a simple Markov Chain Monte Carlo (MCMC) algorithm known as the Glauber dynamics for sampling from the Gibbs distribution.

The Glauber dynamics (also known as the Gibbs sampler) is the simple single-site update Markov chain for sampling from the Gibbs distribution of a graphical model. For the hard-core model with activity $\lambda$, the transitions $X_{t}\rightarrow X_{t+1}$ of the Glauber dynamics are defined as follows: first, choose a random vertex $v$. Then, with probability $\frac{\lambda}{1+\lambda}$ set $X^{\prime}=X_{t}\cup\{v\}$ and with the complementary probability set $X^{\prime}=X_{t}\setminus\{v\}$. If $X^{\prime}$ is an independent set, then set $X_{t+1}=X^{\prime}$ and otherwise set $X_{t+1}=X_{t}$.

We consider two standard notions of convergence to stationarity. The relaxation time is the inverse spectral gap, i.e., $(1-\lambda^{*})^{-1}$ where $\lambda^{*}=\max\{\lambda_{2},|\lambda_{N}|\}$ and $1=\lambda_{1}>\lambda_{2}\geq\dots\geq\lambda_{N}>-1$ are the eigenvalues of the transition matrix $P$ for the Glauber dynamics. The relaxation time is a key quantity in the running time for approximate counting algorithms (see, e.g., Štefankovič, Vempala, and Vigoda [ŠVV09]). The mixing time is the number of steps, from the worst initial state, to reach within total variation distance $\leq 1/2e$ of the stationary distribution, which in our case is the Gibbs distribution $\mu$.

We say that $O(n)$ is the optimal relaxation time and that $O(n\log{n})$ is the optimal mixing time (see Hayes and Sinclair [HS07] for a matching lower bound for any constant degree graph). Here, $n$ denotes the size of the underlying graph. More generally, we say the Glauber dynamics is rapidly mixing when the mixing time is $\mathrm{poly}(n)$.

We establish bounds on the mixing time of the Glauber dynamics by means of approximate tensorization inequalities for the variance of the hard-core model. Interestingly, our analysis utilizes nothing further than the inductive nature of the tree, e.g., we do not make any assumptions about spatial mixing properties of the Gibbs distribution. As a consequence, the bounds we obtain have no dependence on the maximum degree of the graph.

To be more specific we derive the following two group of results: We establish approximate tensorization of variance of the hard-core model on the tree for all $\lambda<1.1$. This implies optimal $O(n)$ relaxation time for the Glauber dynamics. Notably this also includes the uniform distribution over independent sets, i.e., $\lambda=1$.

We can now state our main results.

We believe the optimal mixing results of Theorem 1.1 are related to the reconstruction threshold, which we describe now. Consider the complete $\Delta$-regular tree of height $h$; this is the rooted tree where all nodes at distance $\ell<h$ from the root have $\Delta-1$ children and all nodes at distance $h$ from the root are leaves. We are interested in how the configuration at the leaves affects the configuration at the root.

Consider fixing an assignment/configuration $\sigma$ to the leaves (i.e., specifying which leaves are fixed to occupied and which are unoccupied), we refer to this fixed assignment to the leaves as a boundary condition $\sigma$. Let $\mu_{\sigma}$ denote the Gibbs distribution conditional on this fixed boundary condition $\sigma$, and let $p_{\sigma}$ denote the marginal probability that the root is occupied in $\mu_{\sigma}$.

The uniqueness threshold $\lambda_{c}(\Delta)$ measures the affect of the worst-case boundary condition on the root. For all $\lambda<\lambda_{c}(\Delta)$, all $\sigma\neq\sigma^{\prime}$, in the limit $h\rightarrow\infty$, we have $p_{\sigma}=p_{\sigma}^{\prime}$; this is known as the (tree) uniqueness region. In contrast, for $\lambda>\lambda_{c}(\Delta)$ there are pairs $\sigma\neq\sigma^{\prime}$ (namely, all even occupied vs. odd occupied) for which the limits are different; this is the non-uniqueness region. The uniqueness threshold is at $\lambda_{c}(\Delta)=(\Delta-1)^{\Delta-1}/(\Delta-2)^{\Delta}=O(1/\Delta)$.

In contrast, the reconstruction threshold $\lambda_{r}(\Delta)$ measures the affect on the root of a random/typical boundary condition. In particular, we fix an assignment $c$ at the root and then generate the Gibbs distribution via an appropriately defined broadcasting process. Finally, we fix the boundary configuration $\sigma$ and ask whether, in the conditional Gibbs distribution $\mu_{\sigma}$, the root has a bias towards the initial assignment $c$. The non-reconstruction region $\lambda<\lambda_{r}(\Delta)$ corresponds to when we cannot infer the root’s initial value, in expectation over the choice of the boundary configuration $\sigma$ and in the limit $h\rightarrow\infty$, see Mossel [Mos04] for a more complete introduction to reconstruction.

The reconstruction threshold is not known exactly but close bounds were established by Bhatnagar, Sly, and Tetali [BST16] and Brightwell and Winkler [BW04]; they showed that for constants $C_{1},C_{2}>0$ and sufficiently large $\Delta$: $C_{1}\log^{2}{\Delta}/\log\log{\Delta}\leq\lambda_{r}(\Delta)\leq C_{2}\log^{2}{\Delta}$, and hence $\lambda_{r}(\Delta)$ is “increasing asymptotically” with $\Delta$ whereas the uniqueness threshold is a decreasing function of $\Delta$. Martin [Mar03] showed that $\lambda_{r}(\Delta)>e-1$ for all $\Delta$. As a consequence, we conjecture that Theorem 1.1 holds for all trees for all $\lambda<e-1$, which is close to the bound we obtain. A slowdown in the reconstruction region is known: Restrepo, Štefankovič, Vera, Vigoda, and Yang [RŠV⁺14] showed that there are trees for which there is a polynomial slow down for $\lambda>C$ for a constant $C>0$; an explicit constant $C$ is not stated in [RŠV⁺14] but using the Kesten-Stigum bound one can show $C\approx 28$ (by considering binary trees).

For general graphs the appropriate threshold is the uniqueness threshold, which is $\lambda_{c}(\Delta)=O(1/\Delta)$. In particular, for bipartite random $\Delta$-regular graphs the Glauber dynamics has optimal mixing in the uniqueness region by Chen, Liu and Vigoda [CLV21], and is exponentially slow in the non-uniqueness region by Mossel, Weitz, and Wormald [MWW07] (see also [GŠV16]). Moreover, for general graphs there is a computational phase transition at the uniqueness threshold: optimal mixing on all graphs of maximum degree $\Delta$ in the uniqueness region [CLV21, CFYZ22, CE22], and NP-hardness to approximately count/sample in the non-uniqueness region by Sly [Sly10] (see also, [GŠV16, SS14]).

There are a variety of mixing results for the special case on trees, which is the focus of this paper. In terms of establishing optimal mixing time bounds for the Glauber dynamics, previous results only applied to complete, $\Delta$-regular trees. Seminal work of Martinelli, Sinclair, and Weitz [MSW03, MSW04] proved optimal mixing on complete $\Delta$-regular trees for all $\lambda$. The intuitive reason this holds for all $\lambda$ is that the complete tree corresponds to one of the two extremal phases (all even boundary or all odd boundary) and hence it does not exhibit the phase co-existence which causes mixing. As mentioned earlier, [RŠV⁺14] shows that there is a fixed assignment $\tau$ for the leaves of the complete, $\Delta$-regular tree so that the mixing time slows down in the reconstruction region; intuitively, this boundary condition $\tau$ corresponds to the assignment obtained by the broadcasting process.

For more general trees the following results were known. A classical result of Berger, Kenyon, Mossel and Peres [BKMP05] proves polynomial mixing time for trees with constant maximum degree [BKMP05]. A very recent result of Eppstein and Frishberg [EF23] proved polynomial mixing time $n^{C(\lambda)}$ of the Glauber dynamics for graphs with bounded tree-width which includes arbitrary trees, however the polynomial exponent is $C(\lambda)=O(1+|\log(\lambda)|)$ for trees; see more recent work of Chen [Che24] for further improvements. For other combinatorial models, rapid mixing for the Glauber dynamics on trees with bounded maximum degree was established for $k$-colorings in [LMP09] and edge-colorings in [DHP20].

Spectral independence is a powerful notion in the analysis of the convergence rate of Markov Chain Monte Carlo (MCMC) algorithms. For independent sets on an $n$-vertex graph $G=(V,E)$, spectral independence considers the $n\times n$ pairwise influence matrix ${\mathcal{I}}_{G}$ where ${\mathcal{I}}_{G}(v,w)=\mathrm{Prob}_{\sigma\sim\mu}(v\in\sigma\ |\ w\in\sigma)-\mathrm{Prob}_{\sigma\sim\mu}(v\in\sigma\ |\ w\notin\sigma)$; this matrix is closely related to the vertex covariance matrix. We say that spectral independence holds if the maximum eigenvalue of ${\mathcal{I}}_{G^{\prime}}$ for all vertex-induced subgraphs $G^{\prime}$ of $G$ are bounded by a constant. Spectral independence was introduced by Anari, Liu, and Oveis Gharan [ALO21]. Chen, Liu, and Vigoda [CLV21] proved that spectral independence, together with a simple condition known as marginal boundedness which is a lower bound on the marginal probability of a valid vertex-spin pair, implies optimal mixing time of the Glauber dynamics for constant-degree graphs. This has led to a flurry of optimal mixing results, e.g., [CLV22, BCC⁺22, Liu21, CLMM23, CG24].

The limitation of the above spectral independence results is that they only hold for graphs with constant maximum degree $\Delta$. There are several noteworthy results that achieve a stronger form of spectral independence which establishes optimal mixing for unbounded degree graphs [CFYZ22, CE22]; however all of these results for general graphs only achieve rapid mixing in the tree uniqueness region which corresponds to $\lambda=O(1/\Delta)$ whereas we are aiming for $\lambda=\Theta(1)$.

The inductive approach we use to establish approximate tensorization inequalities can also be utilized to establish spectral independence. In fact, we show that spectral independence holds for any tree when $\lambda<1.3$, including the case where $\lambda=1$, see Section 4. Applying the results of Anari, Liu, and Oveis Gharan [ALO21] we obtain a $\mathrm{poly}(n)$ bound on the mixing time, but with a large constant in the exponent of $n$. For constant degree trees we obtain the following optimal mixing result by applying the results of Chen, Liu, and Vigoda [CLV21] (see also [BCC⁺22, CFYZ22, CE22]).

Interestingly, combining the spectral independence results from the proof Theorem 1.2 with results of Chen, Feng, Yin, and Zhang [CFYZ24, Theorem 1.9], we are able to strengthen Theorem 1.1 by allowing larger fugacities, i.e., $\lambda\leq 1.3$.

In the next section we recall the key functional definitions and basic properties of variance that will be useful later in the proofs. In Section 3 we prove approximate tensorization of variance which establishes Theorem 1.1. We establish spectral independence and prove Theorem 1.2 in Section 4.

A recent paper of Chen, Yang, Yin, and Zhang [CYYZ24] improves Corollary 1.3 to obtain optimal relaxation time on trees for $\lambda<e^{2}$.

In this section we prove Theorem 1.1, establishing an optimal bound on the relaxation time for the Glauber dynamics on any tree for $\lambda\leq 1.1$. We will prove this by establishing variance tensorization, see Definition 2.1.

Consider a graph $G=(V,E)$ and a collection of fugacities $\lambda_{i}$ for each $i\in V$. Throughout this section we will assume that all the fugacities are bounded by $1.1$. Consider the following more general definition of the Gibbs distribution $\mu$ for the hard-core model, where for an independent set $S$,

Let $T^{\prime}=(V^{\prime},E^{\prime})$ be a tree, let $\{\lambda^{\prime}_{w}\}_{w\in V^{\prime}}$ be a collection of fugacities and let $\mu^{\prime}$ be the corresponding Gibbs distribution. We will establish the following variance tensorization inequality: for all $f^{\prime}:2^{V^{\prime}}\rightarrow{\mathbb{R}}$

where $F:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ is a function to be determined later (in Lemma 3.1). We refer to $\mathrm{Var}(f^{\prime})$ as the “global” variance and we refer to $\mu^{\prime}(\mathrm{Var}_{x}(f^{\prime}))$ as the “local” variance (of $f^{\prime}$ at $x$).

We will establish (12) using induction. Let $v$ be a vertex of degree $1$ in $T^{\prime}$ and let $u$ be the unique neighbor of $v$. Let $T=(V,E)$ be the tree by removing $v$ from $T^{\prime}$, i.e., $T$ is the induced subgraph of $T^{\prime}$ on $V=V^{\prime}\setminus\{v\}$. Let $\{\lambda_{w}\}_{w\in V}$ be a collection of fugacities where $\lambda_{w}=\lambda^{\prime}_{w}$ for $w\neq u$ and $\lambda_{u}=\lambda^{\prime}_{u}/(1+\lambda^{\prime}_{v})$. Let $\mu$ be the hard-core measure on $T$ with fugacities $\{\lambda_{w}\}_{w\in V}$.

Note that for $S\subseteq V$ we have

Fix a function $f^{\prime}:2^{V^{\prime}}\rightarrow\mathbb{R}$. Let $f:2^{V}\rightarrow\mathbb{R}$ be defined by

Note that $f^{\prime}$ is defined on independent sets of the tree $T^{\prime}$ and $f$ is the natural projection of $f^{\prime}$ to the tree $T$. Since $f=\mu^{\prime}_{v}(f^{\prime})$, then by Lemma 2.2 we have that:

For measure $\mu^{\prime}$, when we condition on the configuration at $u$, the configuration at $V\setminus\{u\}$ is independent of that at $\{v\}$. Hence, from eq. 10 for any $x\not\in\{u,v\}$ (by setting $U=\{x\}$ and $W=\{v\}$) we have:

Since by (13) we have $\mu(\mathrm{Var}_{x}(f))=\mu^{\prime}(\mathrm{Var}_{x}(f))$, the above implies that

The following lemma is the main technical ingredient. It bounds the local variance at $u$ for the smaller graph $T$ in terms of the local variance at $u$ and $v$ in the original graph $T^{\prime}$.

We now utilize the above lemma to prove the main theorem for the relaxation time. We then go back to prove Lemma 3.1.

Our task now is to prove Lemma 3.1. The following technical inequality will be useful.

We can now prove the main lemma.