Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling

Introduction

Gibbs sampling is one of the most common Markov chain Monte Carlo methods used with graphical models . In this setting, Gibbs sampling (Algorithm 1) operates iteratively by choosing at random a variable from the model at each timestep, and updating it by sampling from its conditional distribution given the other variables in the model. Often, it is applied to inference problems, in which we are trying to estimate the marginal probabilities of some query events in a given distribution.

For sparse graphical models, to which Gibbs sampling is often applied, each of these updates needs to read the values of only a small subset of the variables; therefore each update can be computed very quickly on modern hardware. Because of this and other useful properties of Gibbs sampling, many systems use Gibbs sampling to perform inference on big data .

Since Gibbs sampling is such a ubiquitous algorithm, it is important to try to optimize its execution speed on modern hardware. Unfortunately, while modern computer hardware has been trending towards more parallel architectures , traditional Gibbs sampling is an inherently sequential algorithm; that is, the loop in Algorithm 1 is not directly parallelizable. Furthermore, for sparse models, very little work happens within each iteration, meaning it is difficult to extract much parallelism from the body of this loop. Since traditional Gibbs sampling parallelizes so poorly, it is interesting to study variants of Gibbs sampling that can be parallelized. Several such variants have been proposed, including applications to latent Dirichlet allocation and distributed constraint optimization problems .

In one popular variant, multiple threads run the Gibbs sampling update rule in parallel without locks, a strategy called asynchronous or Hogwild! execution—in this paper, we use these two terms interchangeably. This idea was proposed, but not analyzed theoretically, in Smola & Narayanamurthy , and has been shown to give empirically better results on many models . But when can we be sure that Hogwild! Gibbs sampling will produce accurate results? Except for the case of Gaussian random variables , there is no existing analysis by which we can ensure that asynchronous Gibbs sampling will be appropriate for a particular application. Even the problems posed by Hogwild!-Gibbs are poorly understood, and their solutions more so.

As we will show in the following sections, there are two main issues when analyzing asynchronous Gibbs sampling. Firstly, we will show by example that, surprisingly, Hogwild!-Gibbs can be biased—unlike sequential Gibbs, it does not always produce samples that are arbitrarily close to the target distribution. Secondly, we will show that the mixing time (the time for the chain to become close to its stationary distribution) of asynchronous Gibbs sampling can be up to exponentially greater than that of the corresponding sequential chain.

To address the issue of bias, we need some way to describe the distance between the target distribution $\pi$ and the distribution of the samples produced by Hogwild!-Gibbs. The standard notion to use here is the total variation distance, but for the task of computing marginal probabilities, it gives an overestimate on the error caused by bias. To better describe the bias, we introduce a new notion of statistical distance, the sparse variation distance. While this relaxed notion of statistical distance is interesting in its own right, its main benefit here is that it uses a more local view of the chain to more tightly measure the effect of bias.

Our main goal is to identify conditions under which the bias and mixing time of asynchronous Gibbs can be bounded. One parameter that has been used to great effect in the analysis of Gibbs sampling is the total influence $\alpha$ of a model. The total influence measures the degree to which the marginal distribution of a variable can depend on the values of the other variables in the model—this parameter has appeared as part of a celebrated line of work on Dobrushin’s condition ($\alpha<1$), which ensures the rapid mixing of spin statistics systems . It turns out that we can use this parameter to bound both the bias and mixing time of Hogwild!-Gibbs, and so we make the following contributions:

We describe a way to statistically model the asynchronicity in Hogwild!-Gibbs sampling.

To bound the bias, we prove that for classes of models with bounded total influence $\alpha=O(1)$, if sequential Gibbs sampling achieves small sparse variation distance to $\pi$ in $O(n)$ steps, where $n$ is the number of variables, then Hogwild!-Gibbs samples achieve the same distance in at most $O(1)$ more steps.

For models that satisfy Dobrushin’s condition (that is, $\alpha<1$), we show that the mixing time bounds of sequential and Hogwild!-Gibbs sampling differ only by a factor of $1+O(n^{-1})$.

We validate our results experimentally and show that, by using asynchronous execution, we can achieve wall-clock speedups of up to $2.8\times$ on real problems.

Related Work

Much work has been done on the analysis of parallel Gibbs samplers. One simple way to parallelize Gibbs sampling is to run multiple chains independently in parallel: this heuristic uses parallelism to produce more samples overall, but does not produce accurate samples more quickly. Additionally, this strategy is sometimes worse than other strategies on a systems level , typically because it requires additional memory to maintain multiple models of the chain. Another strategy for parallelizing Gibbs sampling involves taking advantage of the structure of the underlying factor graph to run in parallel while still maintaining an execution pattern to which the standard sequential Gibbs sampling analysis can be applied . Much further work has focused on parallelizing sampling for specific problems, such as LDA and others .

Our approach follows on the paper of Johnson et al. , which named the Hogwild!-Gibbs sampling algorithm and analyzed it for Gaussian models. Their main contribution is an analysis framework that includes a sufficient condition under which Hogwild! Gaussian Gibbs samples are guaranteed to have the correct asymptotic mean. Recent work has analyzed a similar algorithm under even stronger regularity conditions. Here, we seek to give more general results for the analysis of Hogwild!-Gibbs sampling on discrete-valued factor graphs.

The Hogwild!-Gibbs sampling algorithm was inspired by a line of work on parallelizing stochastic gradient descent (SGD) by running it asynchronously. Hogwild! SGD was first proposed by Niu et al. , who proved that while running without locks causes race conditions, they do not significantly impede the convergence of the algorithm. The asynchronous execution strategy has been applied to many problems—such as PageRank approximations , deep learning and recommender systems —so it is not surprising that it has been proposed for use with Gibbs sampling. Our goal in this paper is to combine analysis ideas that have been applied to Gibbs sampling and Hogwild!, in order to characterize the behavior of asynchronous Gibbs. In particular, we are motivated by some recent work on the analysis of Hogwild! for SGD . Several of these results suggest modeling the race conditions inherent in Hogwild! SGD as noise in a stochastic process; this lets them bring a trove of statistical techniques to bear on the analysis of Hogwild! SGD. Therefore, in this paper, we will apply a similar stochastic process model to Gibbs sampling.

Several recent papers have focused on the mixing time of Gibbs sampling based on the structural properties of the model. Gotovos et al. and De Sa et al. each show that Gibbs sampling mixes in polynomial time for a class of distributions bounded by some parameter. Unfortunately, these results both depend on spectral methods (that try to bound the spectral gap of the Markov transition matrix), which are difficult to apply to Hogwild! Gibbs sampling for two reasons. First, spectral methods don’t let us represent the sampler as a stochastic process, which limits the range of techniques we can use to model the noise. Secondly, while most spectral methods only apply to reversible Markov chains—and sequential Gibbs sampling is always a reversible chain—for Hogwild!-Gibbs sampling the asynchronicity and parallelism make the chain non-reversible. Because of this, we were unable to use these spectral results in our asynchronous setting. We are forced to rely on the other method for analyzing Markov processes, coupling—the type of analysis used with the Dobrushin condition—which we will describe in the following sections.

Modeling Asynchronicity

In this section, we describe a statistical model for asynchronous Gibbs sampling by adapting the hardware model outlined in De Sa et al. . Because we are motivated by the factor graph inference problem, we will focus on the case where the distribution $\pi$ that we want to sample comes from a sparse, discrete graphical model.

Any Hogwild!-Gibbs implementation involves some number of threads each repeatedly executing the Gibbs update rule on a single copy of the model (typically stored in RAM). We assume that this model serializes all writes, such that we can speak of the state of the system after $t$ writes have occurred. We call this time $t$, and we will model the Hogwild! system as a stochastic process adapted to the natural filtration $\mathcal{F}_{t}$. Here, $\mathcal{F}_{t}$ contains all events that have occurred up to time $t$, and we say an event is $\mathcal{F}_{t}$ measurable if it is known deterministically by time $t$.

this represents the fact that we have an equal probability of sampling each variable.

Using this, we can relate the values of the variables across time with

This parameter is typically very close to the expected value bound $\tau$; in particular, as $n$ approaches infinity, $\tau^{*}$ approaches $\tau$.

The First Challenge: Bias

Perhaps the most basic result about sequential Gibbs sampling is the fact that, in the limit of large numbers of samples, it is unbiased. In order to measure convergence of Markov chains to their stationary distribution, it is standard to use the total variation distance.

The total variation distance [12, p. 48] between two probability measures $\mu$ and $\nu$ on probability space $\Omega$ is defined as

that is, the maximum difference between the probabilities that $\mu$ and $\nu$ assign to a single event $A$.

It is a well-known result that, for Gibbs sampling on a strictly-positive target distribution $\pi$, it will hold that

where $P^{(t)}\mu_{0}$ denotes the distribution of the $t$-th sample.

One of the difficulties that arises when applying Hogwild! to Gibbs sampling is that the race conditions from the asynchronous execution add bias to the samples — Equation 1 no longer holds. To understand why, we can consider a simple example.

Consider a simple model with two variables $X_{1}$ and $X_{2}$ each taking on values in $\{0,1\}$, and having distribution

Sequential Gibbs sampling on this model will produce unbiased samples from the target distribution. Unfortunately, this is not the case if we run Hogwild!-Gibbs sampling on this model. Assume that the state is currently $(1,1)$ and two threads, $T_{1}$ and $T_{2}$, simultaneously update $X_{1}$ and $X_{2}$ respectively. Since $T_{1}$ reads state $(1,1)$ it will update $X_{1}$ to or $1$ each with probability $0.5$; the same will be true for $T_{2}$ and $X_{2}$. Therefore, after this happens, every state will have probability $0.25$; this includes the state $(0,0)$ which should never occur! Over time, this race condition will produce samples with value $(0,0)$ with some non-zero frequency; this is an example of bias introduced by the Hogwild! sampling. Worse, this bias is not just theoretical: Figure 2 illustrates how the measured distribution for this model is affected by two-thread asynchronous execution. In particular, we observe that almost $5\%$ of the mass is erroneously measured to be in the state $(0,0)$, which has no mass at all in the true distribution. The total variation distance to the target distribution is quite large at $9.8\%$, and, unlike in the sequential case, this bias doesn’t disappear as the number of samples goes to infinity.

2 Bounding the Bias

The previous example has shown that asynchronous Gibbs sampling will not necessarily produce a sequence of samples arbitrarily close to the target distribution. Instead, the samples may approach some other distribution, which we hope is sufficiently similar for some practical purpose. Often, the purpose of Gibbs sampling is to estimate the marginal distributions of individual variables or of events that each depend on only a small number of variables in the model. To characterize the accuracy of these estimates, the total variation distance is too conservative: it depends on the difference over all the events in the space, when most of these are events that we do not care about. To address this, we introduce the following definition.

For any event $A$ in a probability space $\Omega$ over a set of variables $V$, let $\left|A\right|$ denote the number of variables upon which $A$ depends. Then, for any two distributions $\mu$ and $\nu$ over $\Omega$, we define the $\omega$-sparse variation distance to be

For the wide variety of applications that use sampling for marginal estimation, the sparse variation distance measures the quantity we actually care about: the maximum possible bias in the marginal distribution of the samples. As we will show, asynchronous execution seems to have less effect on the sparse variation distance than the total variation distance, because sparse variation distance uses a more localized view of the chain. For example, in Figure 2, the total variation distance between the sequential and Hogwild! distributions is $9.8\%$, while the $1$-sparse variation distance is only $0.4\%$. That is, while Hogwild! execution does introduce great bias into the distribution, it still estimates marginals of the individual variables accurately.

This definition suggests the question: how long do we have to run before our samples have low sparse variation distance from the target distribution? To answer this question, we introduce the following definition.

The $\omega$-sparse estimation time of a stochastic sampler with distribution $P^{(t)}\mu_{0}$ at time $t$ and target distribution $\pi$ is the first time $t$ at which, for any initial distribution $\mu_{0}$, the estimated distribution is within sparse variation distance $\epsilon$ of $\pi$,

In many practical systems , Gibbs sampling is used without a proof that it works; instead, it is naively run for some fixed number of passes through the dataset. This naive strategy works for models for which accurate marginal estimates can be achieved after $O(n)$ samples. This $O(n)$ runtime is necessary for Gibbs sampling to be feasible on big data, meaning roughly that these are the models which it is interesting to try to speed up using asynchronous execution. Therefore, for the rest of this section, we will focus on the bias of the Hogwild! chain for this class of models. When analyzing Gibbs sampling, we can bound the bias within the context of a coupling argument using a parameter called the total influence. While we arrived at this condition independently, it has been studied before, especially in the context of Dobrushin’s condition, which ensures rapid mixing of Gibbs sampling.

Let $\pi$ be a probability distribution over some set of variables $I$. Let $B_{j}$ be the set of state pairs $(X,Y)$ which differ only at variable $j$. Let $\pi_{i}(\cdot|X_{I\setminus\{i\}})$ denote the conditional distribution in $\pi$ of variable $i$ given all the other variables in state $X$. Then, define $\alpha$, the total influence of $\pi$, as

We say the model satisfies Dobrushin’s condition if $\alpha<1$.

One way to think of total influence for factor graphs is as a generalization of maximum degree; indeed, if a factor graph has maximum degree $\Delta$, it can easily be shown that $\alpha\leq\Delta$. It turns out that if we can bound both this parameter and the sparse estimation time of sequential Gibbs sampling, we can give a simple bound on the sparse estimation time for asynchronous Gibbs sampling.

where $n$ is the number of variables in the model. Then, for any $\epsilon$, the sparse estimation time of Hogwild!-Gibbs across all models is bounded by

Roughly, this means that Hogwild!-Gibbs sampling “works” on all problems for which we know marginal estimation is “fast” and the total influence is bounded. Since the sparse estimation times here are measured in iterations, and the asynchronous sampler is able, due to parallelism, to run many more iterations in the same amount of wall clock time, this result implies that Hogwild!-Gibbs can be much faster than sequential Gibbs for producing estimates of similar quality. To prove Claim 1, and more explicitly bound the bias, we use the following lemma.

where $(x)_{+}$ denotes $x$ if $x>0$ and otherwise.

This lemma bounds the distance between the distributions of asynchronous and sequential Gibbs; if we let $t$ be the sparse estimation time of sequential Gibbs, we can interpret this distance as an upper bound on the bias. When $t=O(n)$, this bias is $O(n^{-1})$, which has an intuitive explanation: for Hogwild! execution, race conditions occur about once every $\Theta(n)$ iterations, so the bias is roughly proportional to the frequency of race conditions. This gives us a relationship between the statistical error of the algorithm and a more traditional notion of computational error.

Up until now, we have been assuming that we have a class for which the sparse estimation time is $O(n)$. Using the total influence $\alpha$, we can identify a class of models known to meet this criterion.

For any distribution that satisfies Dobrushin’s condition, $\alpha<1$, the $\omega$-sparse estimation time of the sequential Gibbs sampling process will be bounded by

This surprising result says that, in order to produce good marginal estimates for any model that satisfies Dobrushin’s condition, we need only $O(n)$ samples! While we could now use Lemma 1 to bound the sparse estimation time for Hogwild!-Gibbs, a more direct analysis produces a slightly better result, which we present here.

For any distribution that satisfies Dobrushin’s condition, $\alpha<1$, and for any $\epsilon$ that satisfies

the $\omega$-sparse estimation time of the Hogwild! Gibbs sampling process will be bounded by

This result gives us a definite class of models for which Hogwild!-Gibbs sampling is guaranteed to produce accurate marginal estimates quickly.

The Second Challenge: Mixing Times

Even though the Hogwild!-Gibbs sampler produces biased estimates, it is still interesting to analyze how long we need to run it before the samples it produces are independent of its initial conditions. To measure the efficiency of a Markov chain, it is standard to use the mixing time.

The mixing time [12, p. 55] of a stochastic process with transition matrix $P^{(t)}$ at time $t$ and target distribution $\pi$ is the first time $t$ at which, for any initial distribution $\mu_{0}$, the estimated distribution is within TV-distance $\epsilon$ of $P^{(t)}\pi$. That is,

As we did with bias, here we construct an example model for which asynchronous execution disastrously increases the mixing time. The model we will construct is rather extreme; we choose this model because simpler, practical models do not seem to exhibit this type of catastrophic increase in the mixing time. We start, for some odd constant $N$, with $N$ variables $X_{1},\ldots,X_{N}$ all in $\{-1,1\}$, and one factor with energy

for some very large energy parameter $M_{1}$. The resulting distribution will be almost uniform over all states with $\mathbf{1}^{T}X\in\{-1,1\}$. To this model, we add another bank of variables $Y_{1},\ldots,Y_{N}$ all in $\{-1,1\}$. These variables also have a single associated factor with energy

for parameters $\beta$ and $M_{2}$. Combining these two factors gives us the overall distribution for our model,

where $Z$ is the constant necessary for this to be a distribution. Roughly, the $X$ dynamics are constructed to regularly “generate” race conditions, while the $Y$ dynamics are chosen to “detect” these race conditions and mix very slowly as a result. This model is illustrated in Figure 3.

We simulated two-thread Hogwild!-Gibbs on this model, measuring the marginal probability that $\mathbf{1}^{T}Y>0$; by symmetry, this event has probability $0.5$ in the stationary distribution for both the sequential and asynchronous samplers. Our results, for a model with $N=2001$, $\beta=0.3$, $M_{1}=10^{10}$, and $M_{2}=100$, and initial state $X=Y=\mathbf{1}$, are plotted in Figure 4. Notice that, while the sequential sampler achieves the correct marginal probability relatively quickly, the asynchronous samplers take a much longer time to achieve the correct result, even for a relatively small expected delay ($\tau=0.5$). These results suggest that something catastrophic is happening to the mixing time when we switch from sequential to asynchronous execution — and in fact we can prove this is the case.

For the example model described above, there exist parameters $M_{1}$, $M_{2}$, and $\beta$ (as a function of $N$) such that the mixing time of sequential Gibbs sampling is $O(N\log N)$ but the mixing time of Hogwild!-Gibbs sampling, even with $\tau=O(1)$, can be $\exp(\Omega(N))$.

The intuition behind this statement is that for sequential Gibbs, the dynamics of the $X$ part of the chain quickly causes it to have $\left|\mathbf{1}^{T}X\right|=1$, and then remain there for the remainder of the simulation with high probability. This in turn causes the energy of the $\phi_{Y}$ factor to be essentially $\frac{\beta}{N}(\mathbf{1}^{T}Y)^{2}$, a model which is known to be fast-mixing because it satisfies Dobrushin’s condition. On the other hand, for Hogwild! Gibbs, due to race conditions we will see $\left|\mathbf{1}^{T}X\right|\neq 1$ with constant probability; this will cause the effective energy of the $\phi_{Y}$ factor to be dominated by the $M_{2}(\mathbf{1}^{T}Y)^{2}$ term, a model that is known to take exponential time to mix.

2 Bounding the Mixing Time

This example shows that fast mixing of the sequential sampler alone is not sufficient to guarantee fast mixing of the Hogwild! chain. Consequently, we look for classes of models for which we can say something about the mixing time of both sequential and Hogwild!-Gibbs. Dobrushin’s condition is well known to imply rapid mixing of sequential Gibbs, and it turns out that we can leverage it again here to bound the mixing time of Hogwild!-Gibbs.

Assume that we run Gibbs sampling on a distribution that satisfies Dobrushin’s condition, $\alpha<1$. Then the mixing time of sequential Gibbs will be bounded by

Under the same conditions, the mixing time of Hogwild!-Gibbs will be bounded by

The above example does not contradict this result since it does not satisfy Dobrushin’s condition; in fact its total influence is very large and scales with $n$. We can compare these two mixing time results as

the bounds on the mixing times differ by a negligible factor of $1+O(n^{-1})$. This result shows that, for problems that satisfy Dobrusin’s condition, Hogwild!-Gibbs sampling mixes in about the same time as sequential Gibbs sampling, and is therefore a practical choice for generating samples.

3 A Positive Example: Ising Model

To gain intuition here, we consider a simple example. The Ising model on a graph $G=(V,E)$ is a model over probability space $\{-1,1\}^{V}$, and has distribution

where $\beta$ is a parameter that is called the inverse temperature, the $B_{x}$ are parameters that encode a prior on the variables, and $Z$ is the normalization constant necessary for this to be a distribution. For graphs of maximum degree $\Delta$ and sufficiently small $\beta$, a bound on the mixing time of Gibbs sampling is known when $\Delta\tanh\beta\leq 1$. It turns out that the total influence of the Ising model can be bounded by $\alpha\leq\Delta\tanh\beta$, and so this condition is simply another way of writing Dobrushin’s condition. We can therefore apply Theorem 3 to bound the mixing time of Hogwild!-Gibbs with

This illustrates that the class of graphs we are considering includes some common, well-studied models.

4 Proof Outline

In order to bound the probability that the chains are not equal at a particular time $t$, we focus on the quantity

Experiments

Now that we have derived a theoretical characterization of the behavior of Hogwild!-Gibbs sampling, we examine whether this characterization holds up under experimental evaluation. First, we examine the mixing time claims we made in Section 5. Specifically, we want to check whether increasing the expected delay parameter $\tau^{*}$ actually increases the mixing time as predicted by Equation 2.

To do this, we simulated Hogwild!-Gibbs sampling running on a random synthetic Ising model graph of order $n=1000$, degree $\Delta=3$, inverse temperature $\beta=0.2$, and prior weights $E_{x}=0$. This model has total influence $\alpha\leq 0.6$, and Theorem 3 guarantees that it will mix rapidly. Unfortunately, the mixing time of a chain is difficult to calculate experimentally. While techniques such as coupling from the past exist for estimating the mixing time, using these techniques in order to expose the (relatively small) dependence of the mixing time on $\tau$ proved to be computationally intractable.

Of course, in order for Hogwild!-Gibbs to be useful, it must also speed up the execution of Gibbs sampling on some practical models. It is already known that this is the case, as these types of algorithms been widely implemented in practice . To further test this, we ran Hogwild!-Gibbs sampling on a real-world $11$ GB Knowledge Base Population dataset (derived from the TAC-KBP challenge) using a machine with a single-socket, 18-core Xeon E7-8890 CPU and $1$ TB RAM. As a comparison, we also ran a “multi-model” Gibbs sampler: this consists of multiple threads with a single execution of Gibbs sampling running independently in each thread. This sampler will produce the same number of samples as Hogwild!-Gibbs, but will require more memory to store multiple copies of the model.

Figure 6 reports the speedup, in terms of wall-clock time, achieved by Hogwild!-Gibbs on this dataset. On this machine, we get speedups of up to $2.8\times$, although the program becomes memory-bandwidth bound at around $8$ threads, and we see no significant speedup beyond this. With any number of workers, the run time of Hogwild!-Gibbs is close to that of multi-model Gibbs, which illustrates that the additional cache contention caused by the Hogwild! updates has little effect on the algorithm’s performance.

Conclusion

We analyzed Hogwild!-Gibbs sampling, a heuristic for parallelized MCMC sampling, on discrete-valued graphical models. First, we constructed a statistical model for Hogwild!-Gibbs by adapting a model already used for the analysis of asynchronous SGD. Next, we illustrated a major issue with Hogwild!-Gibbs sampling: that it produces biased samples. To address this, we proved that if for some class of models with bounded total influence, only $O(n)$ sequential Gibbs samples are necessary to produce good marginal estimates, then Hogwild!-Gibbs sampling produces equally good estimates after only $O(1)$ additional steps. Additionally, for models that satisfy Dobrushin’s condition ($\alpha<1$), we proved mixing time bounds for sequential and asynchronous Gibbs sampling that differ by only a factor of $1+O(n^{-1})$. Finally, we showed that our theory matches experimental results, and that Hogwild!-Gibbs produces speedups up to $2.8\times$ on a real dataset.

The authors acknowledge the support of: DARPA FA8750-12-2-0335; NSF IIS-1247701; NSF CCF-1111943; DOE 108845; NSF CCF-1337375; DARPA FA8750-13-2-0039; NSF IIS-1353606; ONR N000141210041 and N000141310129; NIH U54EB020405; Oracle; NVIDIA; Huawei; SAP Labs; Sloan Research Fellowship; Moore Foundation; American Family Insurance; Google; and Toshiba.

“The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA, AFRL, NSF, ONR, NIH, or the U.S. Government.”

References

Appendix A Additional Bias Results

In this section, we present the following additional result that bounds the sparse estimation time of general Gibbs samplers. In particular, this theorem provides an explicit form of the result given in Claim 1.

Then, as long as $\epsilon$ is large enough that

where we use the notation $(x)_{+}=\max(0,x)$, the $\omega$-sparse estimation time of the Hogwild! chain can be bounded with

Appendix B Proofs

Here, we provide proofs for the results in the paper. In the first subsection, we will state lemmas and known results that we will use in the subsequent proofs. Next, we will prove the Claims and Theorems stated in the body of the paper. Finally, we will prove the lemmas previously stated.

First, we state a proposition from \citetseclevin2009markov. This proposition relates the concept of a coupling with the total variation distance between the distributions of two random variables.

Let $X$ and $Y$ be two random variables that take on values in the same set, and let their distributions be $\mu$ and $\nu$, respectively. Then for any coupling, $(\bar{X},\bar{Y})$ it will hold that

Furthermore, there exists a coupling for which equality is achieved; this is called an optimal coupling.

We can prove a related result for sparse variation distance.

Let $X$ and $Y$ be two random variables that each assign values to a set of variables $\{1,\ldots,n\}$, and let their distributions be $\mu$ and $\nu$, respectively. Then for any coupling, $(\bar{X},\bar{Y})$ it will hold that

We state a lemma that bounds the expected total variation distance between the marginal distributions of two states using the total influence $\alpha$. Note that a similar statement to that proved in this lemma may be used as an alternate definition for the total influence $\alpha$; the definition given in the body of the paper is used because it is more intuitive and does not require introducing the concept of a coupling. This lemma will be useful later when proving the subsequent lemmas stated in this subsection.

If $\pi$ is a distribution with total influence $\alpha$, and $X$ and $Y$ are two random variables that take on values in the state space of $\pi$, then for any variable $i$

where, for simplicity of notation, we let $\pi_{i}(\cdot|X)$ denote the conditional distribution of variable $i$ in $\pi$ given the values of all the other variables in state $X$.

Next, we state three lemmas, each of which give bounds on the quantity

for some coupling of two (potentially asynchronous) Gibbs sampling chains. First, we state the result for comparing two synchronous chains.

Consider sequential Gibbs sampling on a distribution $\pi$ with total influence $\alpha$. Then, for any initial states $(X_{0},Y_{0})$ there exists a coupling of the chains $(X_{t},Y_{t})$ such that for any variable $i$ and any time $t$,

Second, we state the result comparing two Hogwild! chains.

Consider any model of Hogwild!-Gibbs sampling on a distribution $\pi$ with total influence $\alpha$. Then, for any initial states $(X_{0},Y_{0})$ there exists a coupling $(X_{t},Y_{t})$ of the Hogwild!-Gibbs sampling chains starting at $X_{0}$ and $Y_{0}$ respectively such that for any variable $i$ and any time $t$,

Third, we state the result comparing a sequential and an asynchronous chain.

Consider any model of Hogwild!-Gibbs sampling on a distribution $\pi$ with total influence $\alpha$. Then if for any initial states $(X_{0},Y_{0})$ we can construct a coupling $(X_{t},Y_{t})$ such that the process $X_{t}$ is distributed according to the dynamics of Hogwild!-Gibbs, the process $Y_{t}$ is distributed according to the dynamics of sequential Gibbs, and for any time $t$,

As a secondary result, if the chain satisfies Dobrushin’s condition ($\alpha<1$), then for any variable $i$ and any time $t$,

Let $x_{0},x_{1},\ldots$ be a sequence such that, for all $t$,

where $f_{t}$ is a function that is monotonically increasing in all of its arguments. Then, for any sequence $y_{0},y_{1},\ldots$, if $x_{0}=y_{0}$ and for all $t$,

Consider the model on $N$ variables $X_{i}$, for $N$ odd, where each $X_{i}$ takes on values in $\{-1,1\}$ and has probability

Then Gibbs sampling on this model (assuming that we allow the chain to start only at a state $X$ where $\pi(X)>0$) has mixing time

B.2 Proofs of Bias Results

First, we restate and prove Claim 1. This proof will use the result of Theorem 4, which we will prove subsequently. We note here that the use of a convex upper bound for the sparse estimation time of the sequential chain (as opposed to using the sequential chain’s sparse estimation time directly) is an unfortunate consequence of the proof—we hope that a more careful analysis could remove it or replace it with a more natural condition.

First, note that, since $\alpha=O(1)$, we know by the definition of big-$O$ notation that for some $\alpha^{*}$, for all models in the class, the total influence of that model will be $\alpha\leq\alpha^{*}$. Similarly, since we assumed that, for any $\epsilon$ and across all models $\pi$,

then for each $\epsilon$, there must exist a $c(\epsilon)$ such that for any distribution $\pi$ with $n$ variables in the class,

For some error $\epsilon$ and model $\pi$, we would like to apply Theorem 4 to bound its mixing time. In order to apply the theorem, we must satisfy the conditions on $\epsilon$: it suffices for

Under this condition, applying the theorem allows us to bound the $\omega$-sparse estimation time of the Hogwild! chain with

then it follows that, for any $\epsilon$ and for all models with $n\geq N(\epsilon)$,

This is equivalent to saying that, for any $\epsilon$ and across all models,

Next, we restate and prove the bias lemma, Lemma 1.

We start by using the primary result from Lemma 6. This result states that we can construct a coupling $(X_{t},Y_{t})$ of the Hogwild! and sequential chains starting at any initial distributions $X_{0}$ and $Y_{0}$ such that at any time $t$,

Now, for any initial distribution $\mu_{0}$, assume that we start with $X_{0}=Y_{0}$, where both are distributed according to $\mu_{0}$. Then, trivially,

It follows from recursive application of the sub-result of Lemma 6 that, for this coupling,

where $(x)_{+}$ denotes $\max(0,x)$. It follows by the union bound that, for any set of variables $I$ with $\left|I\right|\leq\omega$, the probability that the coupling is unequal in at least one of those variables is

Since this inequality holds for any set of variable $I$ with $\left|I\right|\leq\omega$, it follows that

We can proceed to apply Lemma 2, which lets us conclude that

Next, we restate and prove the full bias result, Theorem 4.

We start with the result of Lemma 1, which lets us conclude that

Therefore, by the triangle inequality, for any $t$,

Therefore, for any $t_{0}\leq t\leq t_{1}$,

and so, if we want this to be less than $\epsilon$, it suffices to choose $t$ such that

Recall that as a condition for the theorem, we assumed that

It follows from this and our expression for $R$ that

Therefore this assignment of $t$ will satisfy the previous constraint that $t_{0}\leq t\leq t_{1}$, and so for this assignment of $t$, and for any initial distribution $\mu_{0}$, it holds that

Therefore, by the definition of sparse estimation time, the sparse estimation time of the Hogwild! chain will be

for this assignment of $t$. Now, recall that above we assigned

Under this condition, we can bound this whole error term as

Combining this with the definitions of $t_{0}$ and $c$ lets us state that

Since we above defined $\mu_{t}$ to be the distribution of Hogwild! Gibbs after $t$ timesteps, $\mu_{t}=P^{(t)}\mu_{0}$, where $P^{(t)}$ is the transition matrix of Hogwild! Gibbs after $t$ timesteps. We can thus equivalently write this as

Therefore, by the definition of sparse estimation time,

Next, we restate and prove the theorem that bounds the sparse estimation time of sequential Gibbs for distributions that satisfy Dobrushin’s condition.

We start by using the result of Lemma 4. This result states that, for any initial distributions $(X_{0},Y_{0})$, there exists a coupling $(X_{t},Y_{t})$ of the sequential Gibbs sampling chains starting at distributions $X_{0}$ and $Y_{0}$, respectively, such that for any variable $i$ and any time $t$,

It follows by the union bound that, for any set of variables $I$ with $\left|I\right|\leq\omega$, the probability that the coupling is unequal in at least one of those variables is

Since this inequality holds for any set of variable $I$ with $\left|I\right|\leq\omega$, it follows that

We can proceed to apply Lemma 2, which lets us conclude that, if we let $\mu_{t}$ and $\nu_{t}$ denote the distributions of $X_{t}$ and $Y_{t}$, respectively, then

Since this was true for any initial distributions for $X_{0}$ and $Y_{0}$, it will hold in particular for $Y_{0}$ distributed according to $\pi$, the stationary distribution of the chain. In this case, $\nu_{t}=\pi$, and so for any initial distribution $\mu_{0}$ for $X_{0}$,

Now, in order for this to be bounded by $\epsilon$, it suffices to choose $t$ such that

(here we used the fact that $\alpha<1$ to do the division). Taking the ceiling, we can conclude that when

Since we defined $\mu_{t}$ to be the distribution of $X_{t}$, it must hold that $\mu_{t}=P^{(t)}\mu_{0}$, where $\mu_{0}$ is the initial distribution of $X_{0}$, and $P^{(t)}$ is the transition matrix associated with running $t$ steps of sequential Gibbs sampling. Thus, we can rewrite this as

Since this result held for any initial assignment of $X_{0}$ and therefore for any $\mu_{0}$, by the definition of sparse estimation time it follows that

Next, we restate and prove the theorem that bounds the sparse estimation time of Hogwild! Gibbs for distributions that satisfy Dobrushin’s condition.

We start by using the secondary result from Lemma 6—we can safely use this result because we assumed the chain satisfied Dobrushin’s condition ($\alpha<1$). This result states that we can construct a coupling $(X_{t},Y_{t})$ of the Hogwild! and sequential chains starting at any initial distributions $X_{0}$ and $Y_{0}$ such that at any time $t$,

It follows by the union bound that, for any set of variables $I$ with $\left|I\right|\leq\omega$, the probability that the coupling is unequal in at least one of those variables is

Since this inequality holds for any set of variable $I$ with $\left|I\right|\leq\omega$, it follows that

We can proceed to apply Lemma 2, which lets us conclude that, if we let $\mu_{t}$ and $\nu_{t}$ denote the distributions of $X_{t}$ and $Y_{t}$ respectively,

To bound the sparse estimation time, notice that for any fixed $\epsilon$ (independent of $n$), in order to achieve

therefore $\epsilon$ is large enough that

It is easy to prove that, for all $x\leq\frac{1}{2}$,

Therefore, under this condition in $\epsilon$, it suffices to choose $t$ such that

Since we defined $\mu_{t}$ above to be the distribution of $X_{t}$, it follows that $\mu_{t}=P^{(t)}\mu_{0}$, where $\mu_{0}$ is the initial distribution of $X_{0}$ and $P^{(t)}$ is the transition matrix associated with running $t$ steps of Hogwild! Gibbs. Therefore, we can rewrite this as

Since this is true for any initial distribution of $X_{0}$ and therefore for any $\mu_{0}$, it follows from the definition of sparse estimation time that

B.3 Proofs of Mixing Time Results

We start out by proving that the model mixes rapidly in the sequential case.

First, we assume that we select $M_{1}$ large enough that, even for potentially exponential run times, the dynamics of the chain are indistinguishable from the chain with $M_{1}=\infty$. In particular, this alternate chain will have the following properties:

The dynamics of the $X$ part of the chain do not depend in any way on the value of $Y$.

If at any point, $\left|\mathbf{1}^{T}X\right|>1$, whenever we sample an $X$ variable, we will re-sample it if possible to decrease the value of $\left|\mathbf{1}^{T}X\right|$ with probability $1$.

As long as $\left|\mathbf{1}^{T}X\right|=1$ at some point in time, this will remain true, and the dynamics of the $X$ part of the chain will be those of the chain described in Lemma 8.

We assume that we choose $M_{1}$ large enough that these properties hold over all time windows discussed in this proof with high probability.

Now, by the coupon collector’s problem, after $O(N\log N)$ timesteps, we have sampled all the variables with high probability. If we have sampled all the variables with high probability, then we will certainly have $\left|\mathbf{1}^{T}X\right|=1$ with high probability.

Once we have $\left|\mathbf{1}^{T}X\right|=1$, Lemma 8 ensures that, after $O(N\log N)$ additional timesteps, the $X$ part of the chain will be close to its stationary distribution.

Meanwhile, while $\left|\mathbf{1}^{T}X\right|=1$, the dynamics of the $Y$ part of the chain are exactly Gibbs sampling over the model with energy

For any $\beta<1$, this is known to mix in $O(N\log N)$ time, since it satisfies Dobrushin’s condition. Therefore, after $O(N\log N)$ steps after we have $\left|\mathbf{1}^{T}X\right|=1$, the $Y$ part of the chain will also be close to its stationary distribution.

Summing up the times for the above events gives us a total mixing time for this chain of

Next we prove that the model takes a potentially exponential time to mix in the asynchronous case. Assume here that our model of execution has two threads, which always either sample two $X$ variables independently and asynchronously, or sample a single $Y$ variable synchronously (i.e. there is never any delay when reading the value of a $Y$ variable). For this execution pattern, we have uniformly that $\tau_{i,t}\leq 1$. In particular, this has $\tau=O(1)$.

Now, consider the case where the two threads each choose to sample a variable in $X$ that can be switched. Since at least $\frac{1}{4}$ of the variables are variables in $X$ that can be switched, this will occur with probability at least $\frac{1}{16}$. Given this, they will each independently switch their variable with probability $\frac{1}{2}$. This means that both variables are switched with probability $\frac{1}{4}$ — but this would place the system in a state where

At any time when $\left|\mathbf{1}^{T}X\right|=1$, this will occur with probability $\frac{1}{64}$, which implies that whenever we sample $Y$, the probability that $\left|\mathbf{1}^{T}X\right|>1$ is at least $\frac{1}{64}$.

Now, assume without loss of generality that we initialize $Y$ such that $\mathbf{1}^{T}Y=N$. Let $\rho_{t}$ denote the value of $\mathbf{1}^{T}Y$ at time $t$. Assuming that we sample a variable $Y_{i}$ with value $1$, while $\left|\mathbf{1}^{T}X\right|=1$, the probability that it will be switched will be

Note that since $\rho_{t}\leq N$ at all times, if $\beta<1$,

We also can verify that, for any $0\leq x\leq 2$, as a basic property of the exponential function,

Therefore, as long as $\rho_{t}>0$, and $\left|\mathbf{1}^{T}X\right|=1$,

On the other hand, if $\left|\mathbf{1}^{T}X\right|>1$, then we can pick $M_{2}$ large enough such that with high probability, as long as $\rho_{t}>0$, all variables $Y_{i}$ are always sampled to be $1$. In this case,

In general, since $\left|\mathbf{1}^{T}X\right|>1$ with probability at least $\frac{1}{64}$,

Since $\rho$ is written as a sum of independent samples, as long as $\rho>0$, the distribution of $\rho$ is going to be exponentially concentrated around its expected value, which we have just shown is at least $\frac{N}{64}$. It follows that it is exponentially unlikely to ever achieve a value of $\rho$ that is not positive. By the union bound, there is some $t=\exp(\Omega(N))$ such that, after $t$ timesteps, $\rho_{t}>0$ with high probability.

But, the actual probability that $\rho>0$ in the stationary distribution is exactly $\frac{1}{2}$, by symmetry. It follows that the mixing time for the Hogwild! chain must be greater than $t$; that is,

This finishes our proof of the statement. ∎

If we use the coupling from Lemma 4, then by the result of that lemma,

Now, assume that we initialize $X_{0}$ with distribution $\mu_{0}$, and $Y_{0}$ with the stationary distribution $\pi$. By Proposition 1, since $X_{t}$ has distribution $P^{(t)}\mu_{0}$ and $Y_{t}$ has distribution $P^{(t)}\pi$, this is equivalent to saying

If we use the coupling from Lemma 5, then by the result of that lemma,

Next, recall that we assumed that our Hogwild!-Gibbs sampler has target distribution $\pi$. Now, assume that we initialize $X_{0}$ with distribution $\mu_{0}$, and $Y_{0}$ with the target distribution $\pi$. By Proposition 1, since $X_{t}$ has distribution $P^{(t)}\mu_{0}$ and $Y_{t}$ has distribution $P^{(t)}\pi$, this is equivalent to saying

Next, we restate and prove Statement 2, which says that our experimental strategy provides a valid upper bound on the mixing time.

Consider the partial ordering of states in this Ising model defined by

This sampling procedure is equivalent to the one that we use in the experiment, and it will produce a chain that is consistent with the Ising model’s dynamics.

then the marginal probability of assigning $1$ to any particular variable in $X$ is always no less than the marginal probability of assigning $1$ to the same variable in $Y$.

Therefore, if we initialize all $X^{(0)}_{i}=1$ and all $Y^{(0)}_{i}=-1$, and run the coupling until time $T_{\text{coupling}}$, the time at which

then by the previous analysis, since for any chain $U$ initialized at any state $U^{(0)}$,

Since this was true for any initial value of $U$, it follows that $T_{\text{coupling}}$ is a coupling time for any two initial values of the chain. Therefore, by Corollary 5.3 from \citetseclevin2009markov,

If we use our definition of $\hat{t}(\epsilon)$ where

This in turn implies that $\hat{t}$ is a upper bound on the mixing time, which is the desired result. ∎

B.4 Proofs of Lemmas

In this section, we will restate and prove the lemmas used earlier in the appendix.

For any set of variables $I\subset\{1,\ldots,n\}$, let $M_{I}(\mu)$ denote the marginal distribution of the variables in $I$ in the distribution $\mu$. In particular, $M_{I}$ includes all events $A$ that depend only on variables in set $I$. Next, let $\bar{X}_{I}$ and $\bar{Y}_{I}$ denote the values of $\bar{X}$ and $\bar{Y}$ on those variables in $I$; this will be a coupling of the distributions $M_{I}(\mu)$ and $M_{I}(\nu)$. Therefore, by Proposition 1,

Let $\Omega_{I}$ denote all events in the original probability space $\Omega$ that depend only on the variables in $I$. By the definition of total variation distance,

Now, since this was true for any $I$, it is certainly true if we maximize both sides over all $I$ with $\left|I\right|\leq\omega$. Therefore,

and applying the definition of sparse variation distance proves the lemma. ∎

Let $n$ be the number of variables in the model. For all $k\in\{0,1,\ldots,n\}$, let $Z_{k}$ be a random variable that takes on values in the state space of $\pi$ such that, for all $j\in\{1,\ldots,n\}$,

In particular, $Z_{0}=X$ and $Z_{n}=Y$. Now, by the triangle inequality on the total variation distance,

Next, we note that $Z_{k-1}=Z_{k}$ if and only if $X_{k}=Y_{k}$. Therefore,

Since $Z_{k-1}$ and $Z_{k}$ differ only at most at index $k$, it follows that $(Z_{k-1},Z_{k})\in B_{k}$, and so,

Taking the expected value of both sides produces

Finally, applying the definition of total influence gives us

Define the coupling as follows. Start in state $(X_{0},Y_{0})$, and at each timestep, choose a single variable $i$ uniformly at random for both chains to sample. Then, sample the selected variable in both chains using the optimal coupling, of the conditional distributions of the variable to be sampled in both chains, guaranteed by Proposition 1. Iterated over time, this defines a full coupling of the two chains.

Next, consider the event that $X_{i,t+1}\neq Y_{i,t+1}$. This event will occur if one of two things happens: either we didn’t sample variable $i$ at time $t$ and $X_{i,t}\neq Y_{i,t}$; or we did sample variable $i$ at time $t$, and the sampled variables were not equal. Since the probability of sampling variable $i$ is $\frac{1}{n}$, and we know the probability that the sampled variables were not equal from Proposition 1, it follows that, by the law of total probability,

where $\pi_{i}(\cdot|X_{t})$ denotes the conditional distribution of variable $i$ in $\pi$ given the values of the other variables in $X_{t}$.

Next, we apply the Lemma 3, which gives us

Applying this inequality recursively, and noting that $\max_{i}\underset{}{\mathbf{P}}\left(X_{i,0}\neq Y_{i,0}\right)\leq 1$, we get

As in the sequential case, we sample the selected variable in both chains using the optimal coupling (of the conditional distributions of the variable to be sampled in both chains) guaranteed by Proposition 1. Iterated over time, this defines a full coupling of the two chains.

We follow the same argument as in the sequential case. First, consider the event that $X_{i,t+1}\neq Y_{i,t+1}$. This event will occur if one of two things happens: either we didn’t sample variable $i$ at time $t$ and $X_{i,t}\neq Y_{i,t}$; or we did sample variable $i$ at time $t$, and the sampled variables were not equal. Since the probability of sampling variable $i$ is $\frac{1}{n}$, and we know the probability that the sampled variables were not equal from Proposition 1, it follows that, by the law of total probability,

where $\pi_{i}(\cdot|X_{t})$ denotes the conditional distribution of variable $i$ in $\pi$ given the values of the other variables in $X_{t}$.

Next, we apply the Lemma 3, which gives us

then maximizing the previous expression over $i$ implies that

Now, for some constant $r\leq n^{-1}$, let $y_{t}$ be defined to be the sequence

Now, by the convexity of the exponential function,

Now, we choose $r$ such that the argument to this exponential is zero; that is, we choose

Notice that this choice satisfies the earlier assumption that $0<r\leq n^{-1}$. Using this choice, we can conclude that

We follow a similar argument as in the above lemmas used to bound the mixing time. First, consider the event that $X_{i,t+1}\neq Y_{i,t+1}$. This event will occur if one of two things happens: either we didn’t sample variable $i$ at time $t$ and $X_{i,t}\neq Y_{i,t}$; or we did sample variable $i$ at time $t$, and the sampled variables were not equal. Since the probability of sampling variable $i$ is $\frac{1}{n}$, and we know the probability that the sampled variables were not equal from Proposition 1, it follows that, by the law of total probability,

where $\pi_{i}(\cdot|X_{t})$ denotes the conditional distribution of variable $i$ in $\pi$ given the values of the other variables in $X_{t}$.

Next, we apply the Lemma 3, which gives us

Since the probability of sampling variable $j$ at any time is always just $\frac{1}{n}$, we can reduce this to

Substituting this into our previous expression produces

then maximizing the previous expression over $i$ implies that

Subtracting from both sides to identify the fixed point gives us

Applying this inequality recursively lets us conclude that

We will approach this by induction. The base case holds by assumption, since $x_{0}=y_{0}$. For the inductive case, if $x_{t}\leq y_{t}$ for all $t\leq T$, then

By monotonicity and the inductive hypothesis,

Applying induction to this proves the lemma. ∎

(This lemma contains much of the technical work needed to prove Statement 1. A higher-level motivation for why we are proving this lemma is furnished in the proof of that result.)

Assume that, as we run the chain described in this lemma, we also assign a “color” to each of the variables. All variables with an initial value of $1$ start out as black, and all other variables start out as white. Let $B_{t}$ denote the set of variables that are colored black at any time $t$, and let $S_{t}$ denote the sum of all variables that are colored black at that time. We re-color variables according to the following procedure:

Whenever we change a variable’s value from $-1$ to $1$, if it is colored white, color it black.

Whenever we change a variable’s value from $-1$ to $1$, if it is already colored black, choose a random variable that had value $-1$ at time $t$, and if it is white, color it black.

Note that as a consequence of this result, a variable that is colored white always has value $-1$.

We will prove the following sub-result by induction on $t$: given a time $t$, set $B_{t}$, and sum $S_{t}$, the values of the variables in $B_{t}$ are uniformly distributed over the set of possible assignments that are consistent with $S_{t}$.

(Base Case.) The base case is straightforward. Since $B_{0}$ is just the set of variables that have value $1$, there is only one possible assignment that is consistent with $S_{0}$: the assignment in which all variables take on the value $1$. Since this assignment actually occurs with probability $1$, the statement holds.

(Inductive Case.) Assume that the sub-result is true at time $t$. The sampler chooses a new variable $i$ to sample. One of the following things will happen:

We don’t re-color any variables, or change the values of any variables in $B_{t}$. In this case, $B_{t+1}=B_{t}$ and $S_{t+1}=S_{t}$. Since there is no change to $B$ or $S$, all consistent assignments of the black variables are still equiprobable.

We don’t re-color any variables, but we do change the value of some variable in $B_{t}$ (by changing its value from $1$ to $-1$). Since we sampled the variable $i$ at random, all consistent assignments of the black variables will remain equiprobable.

We re-color some variable $j$ black. There are two events that can cause this:

We could have sampled variable $j$ (that is $i=j$), and changed its value from $-1$ to $1$. This will happen with probability

We could have sampled a variable $i\neq j$ that is already colored black, changed its value from $-1$ to $1$, and then chosen variable $j$ at random to color black. Since, at time $t$, the number of variables with value $-1$ must be

(since we are about to change a value from $-1$ to $1$), this will happen with probability

where $u$ is the number of black-colored variables that have value $-1$ at time $t$.

From this analysis, it follows that, given that we re-colored some variable $j$ black, it will have value $-1$ with probability

In particular, at time $t$, the number of variables that are in $B_{t}$ is

since all variables with value $1$ are in $B_{t}$, and $B_{t}$ is stipulated to contain $u$ additional variables with value $-1$. It follows that at time $t+1$, the number of variables that are in $B_{t}$ is

and there will still be $u$ variables in $B_{t+1}$ with value $-1$. Therefore, the fraction of variables in $B_{t+1}$ that have value $-1$ will be

Note that this is exactly equal to the probability that variable $j$ will have value $-1$. Combining this with the inductive hypothesis shows that the consistent states will all remain equiprobable in this case.

Since the consistent states remain equiprobable in all of the possible cases, it follows from the law of total probability that the consistent states are equiprobable in all cases. This shows that the sub-result holds in the inductive case.

We have now showed that given a time $t$, set $B_{t}$, and sum $S_{t}$, the values of the variables in $B_{t}$ are uniformly distributed over the set of possible assignments that are consistent with $S_{t}$. This implies that if $T_{1}$ is the first time at which the set $B_{t}$ contains all variables, the value of $X_{T}$ is are uniformly distributed over all possible states with $\mathbf{1}^{T}X=1$.

Now, we performed this construction for a particular polarity of swaps (i.e. focusing on switches from $-1$ to $1$), but by symmetry we could just as easily have used the same construction with the signs of all the variables reversed. If we let $T_{-1}$ be the first time at which the set $B_{t}$ contains all variables using this reverse-polarity construction, then the value of $X_{T}$ is uniformly distributed over all possible states with $\mathbf{1}^{T}X=-1$.

Let $T^{*}$ be a random variable that is $T_{1}$ with probability $\frac{1}{2}$ and $T_{-1}$ with probability $\frac{1}{2}$. It follows that at time $T^{*}$, the distribution of $X_{T^{*}}$ will be $\pi$. Therefore, $T^{*}$ is a strong stationary time for this chain. By the properties of strong stationary times,

To bound the mixing time, we start by noticing that

If we let $\bar{T}$ be the first time at which each variable has been set to $1$ at least once, then

Now, if we sample a variable, the probability that we will set it to $1$ is (roughly) $\frac{1}{4}$. It follows from the coupon collector’s problem bound that the expected amount of time required to set all variables to $1$ at least once is

Combining this with the previous inequalities lets us conclude that