{'fraction_non_alphanumeric': 0.031543454969433414, 'fraction_numerical': 0.012510241381483583, 'mean_word_length': 4.673042545584555, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improving Gibbs Sampler Scan Quality with DoGS

The pairwise influence matrix of Dobrushin has long been used as an analytical tool to bound the rate of convergence of Gibbs sampling. In this work, we use Dobrushin influence as the basis of a practical tool to certify and efficiently improve the quality of a discrete Gibbs sampler. Our Dobrushin-optimized Gibbs samplers (DoGS) offer customized variable selection orders for a given sampling budget and variable subset of interest, explicit bounds on total variation distance to stationarity, and certifiable improvements over the standard systematic and uniform random scan Gibbs samplers. In our experiments with joint image segmentation and object recognition, Markov chain Monte Carlo maximum likelihood estimation, and Ising model inference, DoGS consistently deliver higher-quality inferences with significantly smaller sampling budgets than standard Gibbs samplers.


Introduction
The Gibbs sampler of Geman and Geman [GG84], also known as the Glauber dynamics or the heatbath algorithm, is a leading Markov chain Monte Carlo (MCMC) method for approximating expectations unavailable in closed form. First detailed as a technique for restoring degraded images [GG84], Gibbs sampling has since found diverse applications in statistical physics [Jan08], stochastic optimization and parameter estimation [Gey91], and Bayesian inference [Lun+00].
The hallmark of any Gibbs sampler is conditional simulation: individual variables are successively simulated from the univariate conditionals of a multivariate target distribution. The principal degree of freedom is the scan, the order in which variables are sampled [He+16]. While it is common to employ a systematic scan, sweeping through each variable in turn, or a uniform random scan, sampling each variable with equal frequency, it is known that non-uniform scans can lead to more accurate inferences both in theory and in practice [LWK95; LC06]. This effect is particularly pronounced when certain variables are of greater inferential interest. Past approaches to optimizing Gibbs sampler scans were based on asymptotic quality measures approximated with the output of a Markov chain [Lev+05;LC06].
In this work, we propose a computable non-asymptotic scan quality measure for discrete target distributions based on Dobrushin's notion of variable influence [DS85]. We show that for a given subset of variables, this Dobrushin variation (DV) bounds the marginal total variation between a target distribution and T steps of Gibbs sampling with a specified scan. More generally, Dobrushin variation bounds a weighted total variation based on user-inputted importance weights for each variable. We couple this quality measure with an efficient procedure for optimizing scan quality by minimizing Dobrushin variation. Our Dobrushin-optimized Gibbs samplers (DoGS) come equipped with a guaranteed bound on scan quality, are never worse than the standard uniform random and systematic scans, and can be tailored to a target number of sampling steps and a subset of target variables. Moreover, Dobrushin variation can be used to evaluate and compare the quality of any user-specified set of scans prior to running any expensive simulations.
The improvements achieved by DoGS are driven by an inputted matrix,C, of pairwise variable influence bounds discussed in more detail in Section 3. While DoGS can be used with any discrete distribution, it was designed for targets with total influence C < 1, measured in any matrix norm. This criterion is known to hold for a variety of distributions, including Ising models with sufficiently high temperatures, hard-core lattice gas models, random graph colorings [Hay06], and classes of weighted constraint satisfaction problems [FSY17]. Moreover, as we will see in Section 4.1, suitable variable influence bounds are readily available for pairwise and binary Markov random fields. These user-friendly bounds give rise to total influence C < 1 in all of our experiments and thereby enable improvements in both inferential speed and accuracy over standard scans.
The remainder of the paper is organized as follows. Section 2 reviews Gibbs sampling and standard but computationally intractable measures of Gibbs sampler quality. In Section 3, we introduce our scan quality measure and its relationship to (weighted) total variation. We describe our procedures for selecting high-quality Gibbs sampler scans in Section 4. In Section 5, we apply our techniques to three popular applications of the Gibbs sampler: joint image segmentation and object recognition, MCMC maximum likelihood estimation with intractable gradients, and inference in the Ising model. In each case, we observe substantial improvements in full or marginal total variation over standard scans. Section 6 presents our conclusions and discussion of future work.
Notation For any vector v and index i, we let v −i represent the subvector of v with entry v i removed. We use diag(v) for a square diagonal matrix with v on the diagonal and for element-wise multiplication. The i-th standard basis vector is denoted by e i , I represents an identity matrix, 1 signifies a vector of ones, and C is the spectral norm of matrix C. We use the shorthand [p] {1, . . . , p}.

Gibbs sampling and total variation
Consider a target distribution π on a finite p-dimensional state space, X p . Our inferential goal is to approximate expectations -means, moments, marginals, and more complex function averages, E π [f (X)] = x∈X p π(x)f (x) -under π, but we assume that both exact computation and direct sampling from π are prohibitive due to the large number of states, |X | p . Markov chain Monte Carlo (MCMC) algorithms attempt to skirt this intractability by simulating a sequence of random vectors X 0 , X 1 , . . . , X T ∈ X p from tractable distributions such that expectations over X T are close to expectations under π.

Gibbs sampling
Algorithm 1 summarizes the specific recipe employed by the Gibbs sampler [GG84], a leading MCMC algorithm which successively simulates single variables from their tractable conditional distributions. The principal degree of freedom in a Gibbs sampler is the scan, the sequence of p-dimensional probability vectors q 1 , . . . , q T determining the probability of resampling each variable on each round of Gibbs sampling. Typically one selects between the uniform random scan, q t = (1/p, . . . , 1/p) for all t, where variable indices are selected uniformly at random on each round and the systematic scan, q t = e (t mod p)+1 for each t, which repeatedly cycles through each variable in turn. However, non-uniform scans are known to lead to better approximations [LWK95; LC06], motivating the need for practical procedures for evaluating and improving Gibbs sampler scans.

Total variation
Let π t represent the distribution of the t-th step, X t , of a Gibbs sampler. The quality of a T -step Gibbs sampler and its scan is typically measured in terms of total variation (TV) distance between π T and the target distribution π: Definition 1. The total variation distance between probability measures µ and ν is the maximum difference in expectations over all [0, 1]-valued functions, We view TV as providing a bound on the bias of a large class of Gibbs sampler expectations; note, however, that TV does not control the variance of these expectations.

Marginal and weighted total variation
While we typically sample all p variables in the process of Gibbs sampling, it is common for some variables to be of greater interest than others. For example, when modeling a large particle system, we may be interested principally in the behavior in local region of the system; likewise, when segmenting an image into its component parts, a particular region, like the area surrounding a face, is often of primary interest. In these cases, it is more natural to consider a marginal total variation that measures the discrepancy in expectation over only those variables of interest.
Definition 2 (Marginal total variation). The marginal total variation between probability measures µ and ν on a subset of variables S ∈ [p] is the maximum difference in expectations over all [0, 1]-valued functions of X S , the restriction of X to the coordinates in S: More generally, we will seek to control an arbitrary user-defined weighted total variation that assigns an independent non-negative weight to each variable and hence controls the approximation error for functions with varying sensitivities in each variable.
Definition 3 (d-bounded differences). We say f : For example, every function with range [0, 1] is a 1-Lipschitz feature, and the value of the first variable, x → x 1 , is an e 1 -Lipschitz feature. This definition leads to a measure of sample quality tailored to d-bounded difference functions.
Definition 4 (d-weighted total variation). The d-weighted total variation between probability measures µ and ν is the maximum difference in expectations across d-bounded difference functions: 3 Measuring scan quality with Dobrushin variation Since the direct computation of total variation measures is typically prohibitive, we will define an efficiently computable upper bound on the weighted total variation of Definition 4. Our construction is inspired by the Gibbs sampler convergence analysis of Dobrushin and Shlosman [DS85]. The first step in Dobrushin's approach is to control total variation in terms of coupled random vectors, where X t has the distribution, π t , of the t-th step of the Gibbs sampler and Y t follows the target distribution π. For any such coupling, we can define the marginal coupling probability p t,i P(X t i = Y t i ). The following lemma, a generalization of results in [DS85;Hay06], shows that weighted total variation is controlled by these marginal coupling probabilities. The proof is given in Appendix A.1, and similar arguments can be found in Rebeschini and Handel [RH14].
Lemma 5 (Marginal coupling controls weighted TV). For any joint distribution (X, Y ) such that X ∼ µ and Y ∼ ν for probability measures µ and ν on X p and any nonnegative weight vector d ∈ R p , Dobrushin's second step is to control the marginal coupling probabilities p t in terms of influence, a measure of how much a change in variable j affects the conditional distribution of variable i.
Definition 6 (Dobrushin influence matrix). The Dobrushin influence of variable j on variable i is given by This influence matrix is at the heart of our efficiently computable measure of scan quality, Dobrushin variation.
Theorem 8 shows that Dobrushin variation dominates weighted TV and thereby provides target-and scan-specific guarantees on the weighted TV quality of a Gibbs sampler. The proof in Appendix A.2 rests on the fact that, for each t, b t B(q t ) · · · B(q 1 )1 provides an elementwise upper bound on the vector of marginal coupling probabilities, p t .
Theorem 8 (Dobrushin variation controls weighted TV). Suppose that π T is the distribution of the T -th step of a Gibbs sampler with scan (q t ) T t=1 . Then, for any nonnegative weight vector d ∈ R p and entrywise upper boundC on the Dobrushin influence (1), 4 Improving scan quality with DoGS We next present an efficient algorithm for improving the quality of any Gibbs sampler scan by minimizing Dobrushin variation. We will refer to the resulting customized Gibbs samplers as Dobrushin-optimized Gibbs samplers or DoGS for short. Algorithm 2 optimizes Dobrushin variation using coordinate descent, with the selection distribution q t for each time step serving as a coordinate. Since Dobrushin variation is linear in each q t , each coordinate optimization (in the absence of ties) selects a degenerate distribution, a single coordinate, yielding a fully deterministic scan. If m ≤ p is a bound on the size of the Markov blanket of each variable, then our forward-backward algorithm runs in time O( d 0 + min(m log p + m 2 , p)T ) with O(p + T ) storage for deterministic input scans. The T (m log p + m 2 ) term arises from maintaining the derivative vector, w, in an efficient sorting structure, like a max-heap. A user can initialize DoGS with any baseline scan, including a systematic or uniform random scan, and the resulting customized scan is guaranteed to have the same or better Dobrushin variation. Moreover, DoGS scans will always be d-ergodic (i.e., π T − π d,TV → 0 as T → ∞) when initialized with a systematic or uniform random scan and C < 1. This follows from the following proposition, which shows that Dobrushin variation-and hence the d-weighted total variation by Theorem 8-goes to 0 under these conditions and standard scans. The proof relies on arguments in [Hay06] and is outlined in Appendix A.3.
Proposition 9. Suppose thatC is an entrywise upper bound on the Dobrushin influence matrix (1) and that (q t ) T t=1 is a systematic or uniform random scan. If C < 1, then, for any nonnegative weight vector d, the Dobrushin variation vanishes as the chain length T increases. That is,

Bounding influence
An essential input to our algorithms is the entrywise upper boundC on the influence matrix (1). Fortunately, Liu and Domke [LD14] showed that useful influence bounds are particularly straightforward to compute for any pairwise Markov random field (MRF) target, (2) Theorem 10 (Pairwise MRF influence [LD14, Lems. 10, 11]). Using the shorthand σ(s) 1 1+e −s , the influence (1) of the target π in (2) satisfies Pairwise MRFs with binary variables X i ∈ {−1, 1} are especially common in statistical physics and computer vision. A general parameterization for binary pairwise MRFs is given by and our next theorem, proved in Appendix A.4, leverages the strength of the singleton parameters θ i to provide a tighter bound on the influence of these targets.
// Forward: Precompute coupling bounds of Section 3, Theorem 11 in fact provides an exact computation of the Dobrushin influence C ij whenever b * = 1. The only approximation comes from the fact that the value b * = 1 may not belong to the set B = An exact computation of C ij would replace the cutoff of 1 with its closest approximation in B.
So far, we have focused on bounding influence in pairwise MRFs, as these bounds are most relevant to our experiments; indeed, in Section 5, we will use DoGS in conjunction with the bounds of Theorems 10 and 11 to improve scan quality for a variety of inferential tasks. However, user-friendly bounds are also available for non-pairwise MRFs (note that any discrete distribution can be represented as an MRF with parameters in the extended reals), and we include a simple extension of Theorem 11 that applies to binary MRFs with higher-order interactions. Its proof is in Appendix A.5 Theorem 12 (Binary higher-order influence). The target for X ∈ {−1, 1} d and S a set of non-singleton subsets of [p], has influence (1) satisfying

Related Work
In related work, Latuszynski, Roberts, and Rosenthal [LRR13] recently analyzed an abstract class of adaptive Gibbs samplers parameterized by an arbitrary scan selection rule. However, as noted in their Rem. 5.13, no explicit scan selection rules were provided in that paper. The only prior concrete scan selection rules of which we are aware are the Minimax Adaptive Scans with asymptotic variance or convergence rate objective functions [LC06]. Unless some substantial approximation is made, it is unclear how to implement these procedures when the target distribution of interest is not Gaussian. Levine and Casella [LC06] approximate these Minimax Adaptive Scans for specific mixture models by considering single ad hoc features of interest; the approach has many hyperparameters to tune including the order of the Taylor expansion approximation, which sample points are used to approximate asymptotic quantities online, and the frequency of adaptive updating. Our proposed quality measure, Dobrushin variation, requires no approximation or tuning and can be viewed as a practical non-asymptotic objective function for the abstract scan selection framework of Levine and Casella. In the spirit of [LJHG11], DoGS can also be viewed as an approximate inference scheme calibrated for downstream inferential tasks depending only on subsets of variables.
Levine et al. [Lev+05] employ the Minimax Adaptive Scans of Levine and Casella by finding the mode of their target distribution using EM and then approximating the distribution by a Gaussian. They report that this approach to scan selection introduces substantial computational overhead (10 minutes of computation for an Ising model with 64 variables). As we will see in Section 5, the overhead of DoGS scan selection is manageable (15 seconds of computation for an Ising model with 1 million variables) and outweighed by the increase in scan quality and sampling speed.

Experiments
In this section, we demonstrate how our proposed scan quality measure and efficient optimization schemes can be used to both evaluate and improve Gibbs sampler scans when either the full distribution or a marginal distribution is of principal interest. For all experiments with binary MRFs, we adopt the model parameterization of (3) (with no additional temperature parameter) and use Theorem 11 to produce the Dobrushin influence boundC. On all ensuing plots, the numbers in the legend state the best guarantee achieved for each algorithm plotted. Due to space constraints, we display only one representative plot per experiment; the analogous plots from independent replicates of each experiment can be found in Appendix B.

Evaluating and optimizing Gibbs sampler scans
In our first experiment, we illustrate how Dobrushin variation can be used to select between standard scans and how DoGS can be used to efficiently improve upon standard scan quality when total variation quality is of interest. We remind the reader that both scan evaluation and scan selection are performed offline prior to any expensive simulation from the Gibbs sampler. Our target is a 10 × 10 Ising model arranged in a two-dimensional lattice, a standard model of ferromagnetism in statistical physics. In the notation of (3), we draw the unary parameters θ i uniformly at random from {0, 1}, and the interaction parameters uniformly at random: θ ij ∼ Uniform([0, 0.25]). Figure 1 compares, as a function of the number of steps T , the total variation guarantee provided by Dobrushin variation (see Theorem 8) for the standard systematic and uniform random scans. We see that the systematic scan, which traverses variables in row major order, obtains a significantly better TV guarantee than its uniform random counterpart for all sampling budgets T . Hence, the systematic scan would be our standard scan of choice for this target. DoGS (Algorithm 2) initialized with d = 1 and the systematic scan further improves the systematic scan guarantee by two orders of magnitude. Iterating Algorithm 2 on its own scan output until convergence ("Iterated DoGS" in Figure 1) provides additional improvement. However, since we consistently find that the bulk of the improvement is obtained with a single run of Algorithm 2, non-iterated DoGS remains our recommended recipe for quickly improving scan quality.
Note that since our TV guarantee is an upper bound provided by the exact computation of Dobrushin variation, the actual gains in TV may differ from the gains in Dobrushin variation. In practice and as evidenced in Section 5.4, we find that the actual gains in (marginal) TV over standard scans are typically larger than the Dobrushin variation gains.

End-to-end wall-clock time performance
In this experiment, we demonstrate that using DoGS to optimize a scan can result in dramatic inferential speed-ups. This effect is particularly pronounced for targets with a large number of variables and in settings that require repeated sampling from a low-bias Gibbs sampler. The setting is the exactly same as in the previous experiment, with the exception of model size: here we simulate a 10 3 × 10 3 Ising model, with 1 million variables in total. We target a single marginal X 1 with d = e 1 and take a systematic scan of length T = 2 × 10 6 as our input scan. After measuring the Dobrushin variation of the systematic scan, we use an efficient length-doubling scheme to select a DoGS scan: (0) initializeT = 2; (1) run Algorithm 2 with the firstT steps of the systematic scan as input; (2) if the resulting DoGS scan has Dobrushin variation less than , we keep it; otherwise we doubleT and return to step (1). The resulting DoGS scan has lengthT = 16.
We repeatedly draw independent sample points from either the length T systematic scan Gibbs sampler or the lengthT DoGS scan Gibbs sampler. Figure 2 evaluates

Accelerated MCMC maximum likelihood estimation
We next illustrate how DoGS can be used to accelerate MCMC maximum likelihood estimation, while providing guarantees on parameter estimation quality. We replicate the Ising model maximum likelihood estimation experiment of [Dom15, Sec. 6] and show how we can provide the same level of accuracy faster. Our aim is to learn the parameters of binary MRFs based on training samples with independent Rademacher entries. On each step of MCMC-MLE, Domke uses Gibbs sampling with a uniform random scan to produce an estimate of the gradient of the log likelihood. Our DoGS variant employs Algorithm 2 with d = 1, early stopping parameter = 0.01, and a Dobrushin influence bound constructed from the latest parameter estimatê θ using Theorem 11. We set the number of gradient steps, MC steps per gradient, and independent runs of Gibbs sampling to the suggested values in [Dom15]. After each gradient update, we record the distance between the optimal and estimated parameters. Figure 3 displays the estimation error of five independent replicates of this experiment using each of two scans (uniform or DoGS) for two models (a 3 × 3 and a 4 × 4 Ising model). The results show that DoGS consistently achieves the desired parameter accuracy much more quickly than standard Gibbs.

Customized scans for fast marginal mixing
In this section we demonstrate how DoGS can be used to dramatically speed up marginal inference while providing target-dependent guarantees. We use a 40 × 40 non-toroidal Ising model and set our feature to be the top left variable with d = e 1 . Figure 4 compares guarantees for a uniform random scan and a systematic scan; we also see how we can further improve the total variation guarantees by feeding a systematic scan into Algorithm 2. Again we see that a single run of Algorithm 2 yields the bulk of the improvement, and iterated applications only provide small further benefits. For the DoGS sequence, the figure also shows a histogram of the distance of sampled variables from the target variable, X 1 , at the top left corner of the grid. (left) and a 4 × 4 (right) Ising models of Domke [Dom15]. Each MCMC gradient estimate is obtained either from the uniform random scan suggested by Domke or from DoGS initialized with the uniform random scan, using Algorithm 2 to achieve a target total variation of 0.01 (see Section 5.3). Five runs are shown in each case. Figure 5 shows that optimizing our objective actually improves performance by reducing the marginal bias much more quickly than systematic scan. For completeness, we include additional experiments on a toroidal Ising model in Appendix B.3.

Targeted image segmentation and object recognition
The Markov field aspect model (MFAM) of Verbeek and Triggs [VT07] is a generative model for images designed to automatically divide an image into its constituent parts (image segmentation) and label each part with its semantic object class (object recognition). For each test image k, the MFAM extracts a discrete feature descriptor from each image patch i, assigns a latent object class label X i ∈ X to each patch, and induces the posterior distribution π(X|y; k) ∝ exp( (i,j) spatial neighbors σI{X i = X j } (4) + i log( a∈X θ k,a β a,y i I{X i = a})), over the configuration of patch levels X. When the Potts parameter σ = 0, this model reduces to probabilistic latent semantic analysis (PLSA) [Hof01], while a positive value of σ encourages nearby patches to belong to similar classes. Using the Microsoft Research Cambridge (MSRC) pixel-wise labeled image database v1 2 , we follow the weakly supervised setup of Verbeek and Triggs [VT07] to fit the PLSA parameters θ and β to a training set of images and then, for each test image k, use Gibbs sampling to generate patch label configurations X targeting the MFAM posterior (4) with σ = 0.48. We generate a segmentation by assigning each patch the most frequent label encountered during Gibbs sampling and evaluate the accuracy of this labeling using the Hamming error described in [VT07]. This experiment is repeated over 20 independently generated 90% training / 10% test partitions of the 240 image dataset. We select our DoGS scan to target a 12 × 8 marginal patch rectangle at the center of each image (the {0,1} entries of d indicate whether a patch is in the marginal rectangle highlighted in Figure 6) and compare its segmentation accuracy and efficiency with that of a standard systematic scan of length T = 620. We initialize DoGS with the systematic scan, the influence boundC of Theorem 10, and a target accuracy equal to the marginal Dobrushin variation guarantee of the systematic scan. In 11.5ms, the doubling scheme described in Section 5.2 produced a DoGS sequence of length 110 achieving the Dobrushin variation guarantee on marginal TV. Figure 7 shows that DoGS achieves a slightly better average Hamming error than systematic scan using a 5.5× shorter sequence. Systematic scan takes 1.2s to resample each variable of interest, while DoGS consumes 0.37s. Moreover, the 11.5ms DoGS scan selection was performed only once and then used to segment all test images. For each chain, X 0 was initialized to the maximum a posteriori patch labeling under the PLSA model (obtained by setting σ = 0 in the MFAM).

Using loose influence bounds in computations
In our experiments so far we used Theorem 11 to produce the Dobrushin influence boundC. In this section, we evaluate the performance of DoGS on marginal inference, when the upper bound,C, used for all computations is not tight. Figure 8 shows that DoGS' performance degrades gracefully, as the influence upper bound loosens, from left to right. The bottom row demonstrates the quality of the empirical estimates obtained. The results suggest that using a loose influence bound (up to 50% in this case) does not lead to serious accuracy penalty.

Discussion
We introduced a practical quality measure -Dobrushin variation -for evaluating and comparing existing Gibbs sampler scans and efficient procedures -DoGS -for developing customized fast-mixing scans tailored to marginals or distributional features of interest. We deployed DoGS for three common Gibbs sampler applications -joint image segmentation and object recognition, MCMC maximum likelihood estimation, and Ising model inference -and in each case achieved higher quality inferences with significantly smaller sampling budgets than standard Gibbs samplers. In the future, we aim to enlist DoGS for additional applications in computer vision and natural language processing, extend the reach of DoGS to models containing continuous variables, and integrate DoGS into large inference engines built atop Gibbs sampling.

A Proofs
A.1 Proof of Lemma 5 Let X ∼ µ and Y ∼ ν. Now define the sequence (Z i ) p i=0 , such that Z 0 X, Z p Y and Z i−1 , Z i can only differ on element i. By Definition 4 and the compactness of the space of d-Lipschitz features, there exists Then using triangle inequality,

A.2 Proof of Theorem 8
First we state a useful result due to Dobrushin and Shlosman [DS85].
Lemma 13 ( [DS85], similar arguments can be found in Theorem 6 of [Hay06] and in [DSOR16]). Consider the marginal coupling probability p t,i P(X t i = Y t i ) and influence matrix, C, we defined in Section 3 and an arbitrary scan sequence (i t ) t=T t=1 . Then, an application of the law of total probability yields the following bound on the marginal coupling probabilities.
and p 0,i ≤ 1 for all i.

Proof of Theorem 8
At each time step, i t = i with probability q t,i . Let z i (t) I{i t = i} and Z(t) denote the diagonal matrix with Z ii (t) = z i (t) so that EZ(t) = diag(q t ). Now, from Lemma 5, and using Lemma 13, Now, taking an expectation over the randomness of sampling (random variables i t ), we get where we used the fact that p 0 is a vector of probabilities, so all of its elements are at most 1.

A.3 Proof of Proposition 9
Proof Let = C . From Definition 7, we have that implies that the entries of the marginal coupling probability, p T decay with rate (1 − /n) T for uniform random scans. Similarly, Theorem 8 of [Hay06] implies that the entries of the marginal coupling decay with rate (1 − /2) T /n for systematic scans. In both cases, the statement holds by taking T to infinity.

A.4 Proof of Theorem 11: Influence bound for binary pairwise MRFs
Our proof relies on the following technical lemma.
Proof of Theorem 11 In the notation of Lemma 14, we see that, for each i and j = i, the full conditional of X i is given by Therefore, by Lemma 14, the influence of X j on X i admits the bound

B Additional experiments
We provide a few experimental results that were excluded from the main body of the paper due to space limitations.
B.1 Independent replicates of evaluating and optimizing Gibbs sampler scans experiment Figure 9 displays the results of nine independent replicates of the "Evaluating and optimizing Gibbs sampler scans" experiment of Section 5, with independently drawn unary and binary potentials.
B.2 Independent replicates of end-to-end wall clock time performance experiment Figure 10 repeats the timing experiment of Figure 2 providing three extra independent trials. Note that when the user specifies the "early stopping" parameter , Algorithm 2 terminates once its scan is within Dobrushin variation of the target. The long-term bias observed in the DoGS estimate of E π [X 1 ] is a result of this user-controlled early stopping and can be reduced arbitrarily by choosing a smaller . Figure 11 reports the estimate of a marginal expectation versus time from a sampling experiment, including the setup time for DoGS. The setting is the same as in the experiment of Section 5.2 with the exception of model size: here we simulate a 300 × 300 Ising model, with 90K variables in total. The right plot uses the average measured time for a single step the measured setup time for DoGS and the size of the two scan sequences (190K for systematic, 16 for DoGS) to give an estimate of the speedup as a function of the number of samples we draw.

B.3 Addendum to customized scans for fast marginal mixing experiment
In this section we provide alternative configurations and independent runs of the marginal experiments presented in Section 5.4. Figure 12 gives a spatial histogram of samples at different segments of the DoGS sequence produced in Section 5.4. We note that the sequence starts by sampling in the target (left) site's extended neighborhood and slowly zeroes in on the target near the end.
Here we repeat the marginal Ising model experiments from Section 5. The set up is exactly the same, with the exception of the Ising model boundary conditions. Results are shown in Figure 15 and Figure 14.
Finally, in Figure 13, we repeat the sampling experiment of Figure 5 three times.
B.4 Independent replicates of targeted image segmentation and object recognition experiment Figure 16 displays the results of two independent runs of the image segmentation experiment from Section 5.5.