Improved Mixing of Critical Hardcore Model

Denote the set of non-negative integers by ${\mathbb{Z}}_{\ge 0}$, and the set of positive integers by ${\mathbb{Z}}^{+}$. For any integers $a,b\in \mathbb{Z}$, define $a\wedge b$ by the minimum of $a$ and $b$, i.e, $a\wedge b:=\min \{a,b\}$.

Let $\mathrm{Ber}(p)$ denote the Bernoulli distribution with success probability $p\in [0,1]$. Let $\mathrm{Bin}(n,p)$ denote the binomial distribution with number of trails $n\in {\mathbb{Z}}^{+}$ and success probability $p\in [0,1]$. Let $d_{\mathrm{TV}}(\cdot ,\cdot )$ denote the total variation distance. For any random variables $X,Y$, let $X\stackrel{𝑑}{=}Y$ denote that $X$ and $Y$ are equal in distribution.

Let $G=(V,E)$ be a graph. For any $S\subseteq V$, let $\partial S$ denote the set of neighbors of $S$ in $G$, i.e., $\partial S=\{v\in V\setminus S\mid \exists u\in S,\{u,v\}\in E\}$; and let $G[S]$ denote the subgraph induced in $G$ by $S$, i.e., the graph with vertex set $S$ and edge set consisting of all edges of $G$ that have both endpoints in $S$.

Let $T=(V,E)$ be a tree rooted at $r$. For every vertex $v\in V$, let $T_v$ denote the subtree of $T$ rooted at $v$ that consists of all descendants of $v$; in particular, $T_r=T$. For any $v\in V$, let $L(v)$ denote the set of children of $v$ in $T$.

We end this subsection by defining the ($t$-fold) convolution of distributions on $\mathbb{Z}$.

The core result of this work is to establish the $O(\sqrt{n})$-spectral independence for the critical hardcore model, from which Theorem 1 readily follows by sophisticated spectral independence techniques that have been developed in a recent line of works.

The following notion of influences is needed to define the meaning of spectral independence.

In the setting of the hardcore model, the influences describe the correlation between two vertices, represented as Bernoulli random variables indicating whether the vertices are occupied. Roughly speaking, the influence of one vertex on the other represents the difference of the marginal distribution on the second vertex when flipping the first vertex from occupied to unoccupied.

Theorem 4 states that the hardcore model in the regime of interest satisfies ${\mathrm{\ell }}_{\mathrm{\infty }}$ spectral independence with constant $O(\sqrt{n})$ (see the full version of the paper [8] and also [13]). An analogous result for the Ising model was previously shown in [3].

Many methods have been introduced to establish the spectral independence property for various families of distributions. Here we adopt the coupling independence approach introduced in [6] and apply it on a related tree, known as the self-avoiding walk tree [28]. The formal definition and construction of this tree are omitted in this paper as we only need its existence, and we refer interested readers to the works [28, 10].

We are interested in coupling two hardcore models on this tree, where in one copy the root is fixed to be occupied while in the other it is fixed to be unoccupied. As we shall see soon in Proposition 5, controlling the number of discrepancies between these two copies under a simple coupling procedure enables us to deduce spectral independence. To formally describe this coupling, we first need a few definitions. Let $T=(V,E)$ be a tree rooted at $r$ of maximum degree at most $\mathrm{\Delta }$. Consider the hardcore model on $T$ with fugacity $\lambda >0$. For each vertex $v$, let $p_v$ denote the probability that $v$ is occupied in the hardcore model on the subtree $T_v$, i.e., $p_v:={Pr}_{{\mu }_{T_v,\lambda }}\left[{\sigma }_v=1\right]$, where we recall that $T_v$ is the subtree of $T$ rooted at $v$ that consists of all descendants of $v$.

We now describe a natural vertex-by-vertex greedy coupling for the hardcore model on $T$ when the spin at root $r$ is flipped.

• $\mathrm{■}$

  Initialization: $X_r=1$ and $Y_r=0$;

• $\mathrm{■}$

  While there exists $v\in V$ whose parent $u$ has already been revealed in $X$ and $Y$:

  • –

    If $X_u=Y_u$, then couple the whole subtree $T_v$ perfectly, i.e., $X_{T_v}=Y_{T_v}$;

  • –

    If $X_u=1$ and $Y_u=0$, then set $X_v=0$ and sample $Y_v\sim \mathrm{Ber}(p_v)$;

  • –

    If $X_u=0$ and $Y_u=1$, then sample $X_v\sim \mathrm{Ber}(p_v)$ and set $Y_v=0$;

• $\mathrm{■}$

  Return $(X,Y)$.

It is straightforward to check that when the greedy coupling ends, $X$ is an independent set distributed as ${Pr}_{{\mu }_{T,\lambda }}[\cdot \mid {\sigma }_r=1]$ and $Y$ as ${Pr}_{{\mu }_{T,\lambda }}[\cdot \mid {\sigma }_r=0]$.

Hence, to establish Theorem 4, it suffices to bound the expected number of disagreements in the greedy coupling for the hardcore model on trees when the spins at the root are distinct.

From the greedy coupling procedure above, we observe a natural site percolation on the tree $T$ describing the appearance of disagreements. Every vertex $v$ is open with probability $p_v$ independently, representing the occurrence of a disagreement at $v$, that is, $X_v\ne Y_v$; otherwise, the vertex $v$ is closed. The root $r$ is always open, i.e., $p_r=1$, since $X_r\ne Y_r$. Our goal is to bound the size of the open cluster containing the root, consisting of all open vertices that are connected to the root via a path of open vertices.

We now introduce some notations for the site percolation model. Let $T=(V,E)$ be a tree rooted at $r$. For any $v\in V$, let $p_v$ be the probability that $v$ is open, and we call $p_v$ the occupation probability of $v$. For simplicity, we assume $p_r=1$. Let $P={\left\{p_v\right\}}_{v\in V}$ be the list of occupation probabilities for all vertices, and call it the occupation probability list of the site percolation model. Finally, for the site percolation on $T$ with occupation probability list $P$, let $N(T,P)$ denote the random variable representing the size of the open cluster containing the root.

From the construction of the greedy coupling and the site percolation above, we see that $|X\oplus Y|\stackrel{𝑑}{=}N(T,P)$, where $p_v={Pr}_{{\mu }_{T_v,\lambda }}\left[{\sigma }_v=1\right]$ for each $v\in V\setminus \left\{r\right\}$; see the full version of the paper [8] for a formal statement. Thus, the problem is reduced to studying a site percolation model.

In order to study this site percolation model, we need to know the conditions satisfied by the occupation probabilities $\{p_v\}$. Since these probabilities correspond to the marginal probability of the roots in the respective subtrees, they satisfy a well-known recurrence called the tree recursion (see Fact 21). In this work, we present a new inequality satisfied by these marginal probabilities, which is crucial in obtaining our main spectral independence result. In particular, Equation 1 below provides a stronger and simpler contraction property of the tree recursion, which was not known in the literature as far as we are aware. For simplicity, here we consider only the exact critical fugacity $\lambda ={\lambda }_c(\mathrm{\Delta })$.

We are now ready to state our main percolation result, from which spectral independence Theorem 4 readily follows.

At this point, we transfer our original problem of bounding the mixing time and proving critical spectral independence into a problem of site percolation on trees. In [3], the same strategy was applied to the critical Ising model, another canonical example of graphical models. There, the occupation probabilities are much simpler; in fact, they can all be set to $p_v=1/d$, which is a uniform upper bound on the pairwise influence on $v$ from its parent. We remark that the main distinction of [3] and our work lies in the application of Lemma 6 (corresponding to the condition Equation 3) which substantially extends the uniform setting, $p_v=1/d$ for all $v$, appeared in the critical Ising model.

The main part of the paper aims to prove Theorem 8. We introduce a novel approach to study such a site percolation model on the infinite tree, by considering an online decision-making game.

Our strategy is to upper bound $𝔼\left[N\wedge n\right]$ by understanding the worst-case choice of occupation probabilities $\{p_v\}$. We do this by changing the perspective and thinking as an adversary who is allowed to pick the occupation probabilities. Namely, we study an online decision-making problem where a player is allowed to pick the occupation probabilities $\{p_v\}$ every time we need to reveal the status (open or closed) of a few vertices. These probabilities can be arbitrary as long as they satisfy the requirements Equation 3, and the goal of the player is to maximize $𝔼\left[N\wedge n\right]$.

To be more specific, let $A_t$ denote the number of active vertices at time $t$, where a vertex is said to be active if (i) it is open; (ii) there is an open path from it to the root; (iii) the status of its children has not been fully revealed. At the beginning, $A_0=1$ since only the root is open and we have not revealed any other vertex. Then, the player picks the occupation probabilities for both the children and the grandchildren of $r$; these probabilities are required to satisfy Equation 3. By sampling from the corresponding Bernoulli distributions independently, we reveal the number of grandchildren of $r$, denoted as $X_1$, that are active (i.e., open and connected to $r$). With $r$ being deactivated, the number of active vertices becomes $A_1=A_0-1+X_1=X_1$. The game is then repeated. Whenever there exists an active vertex $v$ at round $t$, the player picks occupation probabilities of the children and grandchildren of $v$ satisfying Equation 3, and, after the number $X_t$ of open grandchildren connected to $v$ is revealed, updates $A_t=A_{t-1}-1+X_t$. This process stops when there are no active vertices, i.e., when $A_t=0$.

We remark that we consider only active vertices at even levels because Equation 3 imposes requirements on two adjacent levels.

Suppose the game stops after $k$ rounds. Then, the number of open vertices connected to the root at even levels is precisely $k$, since every such vertex becomes active at some point and is deactivated at some other time. Therefore, controlling the number of rounds played in the game allows us to bound $𝔼\left[N_e\wedge n\right]$ where $N_e$ is the number of vertices at even levels that are in the open cluster containing the root in the site percolation. (Since $𝔼\left[N_e\wedge n\right]={\sum }_{m=1}^{n}Pr\left[N_e\ge m\right]$, in the actual proof we aim to bound $Pr\left[N_e\ge m\right]$ for every $m$ for simplicity. And we can bound $Pr\left[N_e\ge m\right]$ by the maximum probability that the game lasts for at least $m$ rounds.) Finally, combining the upper bound of $𝔼\left[N_e\wedge n\right]$ with Equation 4, it is then not hard to upper bound $𝔼\left[N\wedge n\right]$ as wanted.

Therefore, our goal is to determine the optimal strategy of the player when such an online decision-making game is played. We deal with this in Section 3 where we state and prove our main result, Theorem 19. While a natural guess of the optimal strategy is to set every occupation probability $p_v$ to be $1/d$ so that Equation 3 is satisfied, we show that the optimal strategy of the player should set $p_v{p}_w=1/d$ for one child $w\in L(v)$ of $v$ and set $p_{w^{\prime }}=0$ for all other children $w^{\prime }\in L(v)$. We remark that such choices of $\{p_v\}$ are not realizable as marginal probabilities in the hardcore model since they do not satisfy the tree recursion and are way too large (in reality, $p_v=O(\lambda )=O(1/d)$ at criticality); however, they are sufficient to provide meaningful upper bounds on $𝔼\left[N\wedge n\right]$ as we need.

We present the proof of Theorem 8 about site percolation on the infinite tree in Section 4, utilizing Theorem 19. Finally, we deduce spectral independence (Theorem 4) and rapid mixing (Theorem 1) from Theorem 8; see the full version of the paper [8] for details.

We now describe precisely an online decision-making game under a slightly more general setting.

In the online decision-making game, the player maintains some number of tokens (corresponding to active vertices). Let $A_t$ denote the number of tokens the player owns after round $t$. At the beginning, the player has $A_0=a$ tokens. There is a family $𝒫$ of distributions on non-negative integers ${\mathbb{Z}}_{\ge 0}$ (corresponding to choices of occupation probabilities). For round $t$, the player spends one token, assuming $A_{t-1}\ge 1$, and chooses a distribution ${\pi }_t\in 𝒫$. Then, a sample $X_t\sim {\pi }_t$ is generated independently, and the player receives $X_t$ tokens as a reward. The number of tokens the player owns then becomes $A_t=A_{t-1}-1+X_t$. The game ends when the player uses up all the tokens, i.e., the first time $A_t=0$. We denote this stopping time by $\tau$. Note that it is possible the game never stops, in which case $\tau =\mathrm{\infty }$. The goal of the player is to survive for $m$ rounds for some given integer $m\in {\mathbb{Z}}_{\ge 0}$. That is, the player wins if and only if $\tau \ge m$. We present the process of the online decision-making game in Algorithm 1.

Define a strategy $\mathrm{SS}$ for the player by a mapping $\mathrm{SS}:{\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}\to 𝒫$. For any $k,a\in {\mathbb{Z}}^{+}$, $\mathrm{SS}(k,a)$ is defined by the distribution the player will choose when they needs to survive for $k$ more rounds to win and currently has $a$ tokens. For example, if the winning requirement is $m$ rounds, then at the beginning of round $t$, the player will choose the distribution ${\pi }_t=\mathrm{SS}(m-t+1,A_{t-1})$ assuming $A_{t-1}\ge 1$.

For $m,a\in {\mathbb{Z}}_{\ge 0}$, define the winning probability under strategy $\mathrm{SS}$ to be

Namely, ${\phi }_m^{\mathrm{SS}}(a)$ is the probability that the game lasts for at least $m$ rounds, assuming the player has $a$ tokens at the beginning and uses strategy $\mathrm{SS}$. We further define

The following lemma establishes a simple recursive formula for the optimal winning probabilities and the existence of an optimal strategy.

Our goal is to find an optimal strategy for the online decision-making game. A first thought that one may consider is to use first-order stochastic dominance (also simply called stochastic dominance). For any two distributions $\mu ,\nu$ over ${\mathbb{Z}}_{\ge 0}$, $\mu$ is (first-order) stochastically dominated by $\nu$ if and only if ${Pr}_{\mu }\left[X\ge i\right]\le {Pr}_{\nu }\left[Y\ge i\right]$ for all $i\in {\mathbb{Z}}_{\ge 0}$. An immediate corollary is that $\mu$ is stochastically dominated by $\nu$ implies ${𝔼}_{\mu }\left[X\right]\le {𝔼}_{\nu }\left[Y\right]$. If there is a largest distribution under stochastic dominance in $𝒫$, then it can be easily proved that the player can attain the maximum winning probability when always picking the largest distribution. However, the largest distribution under stochastic dominance does not exist in our case, since any two different distributions with the same mean are not comparable under stochastic dominance. In fact, in our application, there are infinitely many distributions attaining the largest mean in $𝒫$. Therefore, there is no largest distribution under stochastic dominance and we need something else.

It turns out that second-order stochastic dominance (see, e.g., [16, 15] for more background and applications) can address the problem of the lack of a largest distribution. However, as a trade-off, it is not always true that the player can achieve the maximum winning probability when always choosing the largest distribution under second-order stochastic dominance. Nonetheless, if the largest distribution satisfies some nice properties (see Theorem 19 for details), this is indeed true.

We now define second-order stochastic dominance.

The following proposition shows some classical equivalent definitions of second-order stochastic dominance.

The following two lemmas offer easy ways to find an “upper bound” of a given distribution in the sense of “${⪯}_{(2)}$”, and are helpful to us in identifying the largest distribution in $𝒫$.

As hinted by Item 2 of Proposition 11, in order to apply second-order stochastic dominance, we hope to have some non-decreasing concave functions as the objective/utility function in our decision making. It turns out that when the largest distribution (under “${⪯}_{(2)}$”) is a Poisson binomial distribution (see, e.g., [26] for a thorough introduction) with expectation at least $1$, the maximum winning probability ${\phi }_m^{\ast }(a)$ is non-decreasing and concave with respect to $a$.

We first define the Poisson binomial distribution.

An immediate property is the following.

The crucial property that guarantees the concavity of the maximum winning probability is that a Poisson binomial random variable is unimodal with a mode near the mean of the random variable. We next define unimodality and state the property.

The following proposition of the random walk hitting time will be used in deriving the formula of the maximum winning probability and proving the concavity of the maximum winning probability.

We refer the readers to [27] for the proof of Item 1, and the full version of the paper [8] for the proof of Item 2.

In this subsection, we show our main result for the online decision-making game. The following theorem implies that if the largest distribution ${\pi }^{\ast }$ (under “${⪯}_{(2)}$”) of $𝒫$ exists and is a Poisson binomial distribution with expectation at least $1$, then an optimal strategy ${\mathrm{SS}}^{\ast }$ for the player is ${\mathrm{SS}}^{\ast }\equiv {\pi }^{\ast }$, in other words, the player can achieve the maximum winning probability when always choosing the largest distribution.

We will prove by induction on $m$. The recurrence follows from the concavity of the maximum winning probability and Proposition 11 about second-order stochastic dominance. Given the recurrence, we obtain the formula using Proposition 18 about the random walk hitting time. Finally, we derive concavity using the formula and the fact that ${\pi }^{\ast }$ is a Poisson binomial distribution and hence satisfies unimodality with mode near the mean.