{'fraction_non_alphanumeric': 0.06078489229861316, 'fraction_numerical': 0.02274739129268489, 'mean_word_length': 3.7899267634588205, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Mixing and Concentration by Ricci Curvature

We generalise the coarse Ricci curvature method of Ollivier by considering the coarse Ricci curvature of multiple steps in the Markov chain. This implies new spectral bounds and concentration inequalities. We also extend this approach to the bounds for MCMC empirical averages obtained by Joulin and Ollivier. We prove a recursive lower bound on the coarse Ricci curvature of multiple steps in the Markov chain, making our method broadly applicable. Applications include the split-merge random walk on partitions, Glauber dynamics with random scan and systemic scan for statistical physical spin models, and random walk on a binary cube with a forbidden region.

where P x denotes the measure P (x, dz), and W 1 denotes the Wasserstein distance of P x and P y . It is known that for reversible chains, κ gives a lower bound on the spectral gap: γ ≥ κ. It can be also used to bound the mixing time of the chain (known as the Bubley-Dyer path coupling method, see Bubley and Dyer (1997)). The name curvature comes from the fact that it is linked to the geometric definition of Ricci curvature. One of the motivating examples of Ollivier (2009) is the well known Gromov-Lévy theorem, which it recovers (up to a small constant factor).
When considering Lipschitz functions on Ω under the stationary distribution π of the chain, it is possible to prove variance and concentration bounds, with constants depending on 1/κ, the typical step size of the Markov chain, and the Lipschitz coefficient. In addition to this, one can show concentration inequalities for MCMC empirical averages of Lipschitz functions (see Joulin and Ollivier (2010)). The coarse Ricci curvature approach have been found to give the right order of concentration and spectral bounds in numerous examples. However, there were also cases where it has not succeeded to give bounds of the correct order. One of them is the split-merge walk on partitions (also called the coagulation-fragmentation chain, see Diaconis et al. (2004) for references), where κ = O(1/N 2 ), which is too small, since γ = O(1/N ) in this case. In order to extend the coarse Ricci curvature approach to this situation, we define the multi-step coarse Ricci curvature as κ k (x, y) = 1 − W 1 (P k x , P k y ) d(x, y) for x = y, and κ k = inf x,y∈Ω,x =y κ k (x, y), which is the coarse Ricci curvature of the k step Markov kernel P k . We extend the spectral and concentration bounds to this case. We show that for reversible chains, for any k ∈ AE, the spectral gap satisfies γ ≥ κ k /k, and concentration inequalities hold with constants depending on ∞ k=0 (1 − κ k ). In particular, this allows us to recover bounds of the correct order of magnitude for the split-merge walk on partitions.
We propose several approaches to bound κ k . The first approach is applicable when the mixing time of the chain can be bounded, and the state space is discrete. In this case, we are able to obtain bounds on κ k for sufficiently large k, which in turn can imply concentration bounds. We illustrate this with an example about the Curie-Weiss model in critical phase. The second approach gives a recursive lower bound on κ k . If the curvature is positive in most of the state space, and negative in a small part, then in some situations, this recursive bound can show that κ k becomes positive for sufficiently large k. An example is given about a random walk on a binary cube with a forbidden region. Now we explain the organisation of this paper. In Section 2, we introduce the main definitions. Section 3 contains our results, in particular, new spectral bounds, concentration inequalities, and moment bounds involving the multi-step coarse Ricci curvature. We also state propositions for bounding κ k . In Section 4, we present some applications. Finally, Section 5 contains the proofs of our concentration inequalities.
We end the introduction by a few additional remarks about the related literature. The coarse Ricci curvature approach originates from semigroup tools, which have been used previously in the literature to prove concentration inequalities for Lipschitz functions of random variables distributed according to the stationary distribution of a Markov process (see Ledoux (2001), Section 2.3). These can be used to prove concentration for the Gaussian measure, and more generally, for log-concave densities. For a recent extension of the coarse Ricci curvature to continuous time Markov processes, see Veysseire (2012a), and Veysseire (2012b). Veysseire (2012) obtains concentration bounds in the case when the coarse Ricci curvature is zero. The coarse Ricci curvature have been used previously, but without geometric interpretation, to bound mixing times, known as the Bubley-Dyer path coupling method. In this sense, it has been also extended to consider multiple steps in the Markov chain, in Dyer et al. (2000), see also Bhamidi, Bresler and Sly (2011). The coarse Ricci curvature approach was adapted to graphs in Bauer, Jost and Liu (2011) and Bauer et al. (2013), and to adaptive MCMC in Pillai and Smith (2013).
There is another popular curvature notion called the Sturm-Lott-Villani curvature (Lott and Villani (2009), Sturm (2006)). Ollivier (2013) gives a visual introduction to various curvature definitions, and compares them on numerous examples. In the case of Riemann manifolds, Milman (2012a) studies the relation of isoperimetric, functional and transportation cost inequalities, and Milman (2012b) generalises the Gromov-Lévy theorem to compact manifolds with negative curvature. This paper was motivated by some of the problems of the survey Ollivier (2010). Finally, we note that after we have completed this work, Luczak (2008) have been bought to our attention. It considers similar ideas as ours, and obtains concentration and spectral bounds depending on the contraction properties of the measures describing multiple steps in the Markov chain. The approach was further developed in Luczak (2012), Brightwell and Luczak (2013b) and Brightwell and Luczak (2013a). Our results in this paper are more precise, since they take into account the typical size of the jump of the Markov chain, as well as the dimension of the state space, which were not considered in the earlier work. In addition, we also show a recursive bound on the multi-step coarse Ricci curvature, which makes our method easier to apply in practice.

Preliminaries
We will work with stationary, time homogeneous Markov chains (X i ) i∈AE with transition kernel P (x, dy) taking values in a Polish metric space (Ω, d). We will denote the stationary distribution of the chain by π. The expected value of a function f : Ω → Ê under π will be denoted by E π (f ). The jump measure when starting from x will be denoted by P x , that is, P x (dy) = P (x, dy). For k ≥ 0, the k-step transition kernel will be denoted by P k (x, dy) (in particular, P 0 (x, dy) = δ x (dy), the Dirac-measure concentrated on x).

Ricci curvature
We define the L 1 transportation distance (Wasserstein distance) of two measures on (Ω, d) as where the infimum is taken over all couplings (X, Y ) of µ 1 and µ 2 (that is, (X, Y ) is a random vector taking values on Ω × Ω, whose distribution has marginals µ 1 , and µ 2 ). The following definition is a generalisation of Ollivier's coarse Ricci curvature (Definition 3 of Ollivier (2009)).
Remark 2.2. For k = 1, this is just the usual definition of coarse Ricci curvature, that is, κ = κ 1 . It is easy to show that 1 − κ i satisfies the inequality (2.3)

Mixing time and spectral gap
We define the total variational distance of two measures P, Q defined on the same state space (Ω, F ) as with the infimum taken over all the couplings (X, Y ) of P and Q. We define the mixing time of a time homogeneous Markov chain with general state space in the following way (similarly to Section 4.5 and 4.6 of Levin, Peres and Wilmer (2009)).
Let L 2 (π) denote the Hilbert space of complex valued measurable functions with domain Ω that are square integrable with respect to π, endowed with the inner product < f, g > π = f g * dπ, and norm f 2,π := f, f 1/2 π = E π f 2 1/2 (we use the same notation for the induced operator norm). P can be then viewed as a linear operator on L 2 (π), denoted by P , defined as and reversibility is equivalent to the self-adjointness of P . The operator P acts on measures to the left, creating a measure µP , that is, for every measurable subset A of Ω, µP (A) := x∈Ω P (x, A)µ(dx). For a Markov chain with transition kernel P (x, dy), and stationary distibution π, we define the time reversal of P as the Markov kernel P * (x, dy) := P (y, dx) π(dx) · π(dy). (2.6) Then the linear operator P * is the adjoint of the linear operator P on L 2 (π). For a Markov chain with stationary distribution π, we define the spectrum of the chain as S 2 := {λ ∈ \ 0 : (λI − P ) −1 does not exist as a bounded lin. oper. on L 2 (π)}.
For reversible chains, S 2 lies on the real line.
In the reversible case, γ ≥ γ * . The pseudo spectral gap of P (introduced in Paulin (2014)) is where γ((P * ) k P k ) denotes the spectral gap of the self-adjoint operator (P * ) k P k .

Results
In this section, we will present our results based on the multi-step coarse Ricci curvature. In Section 3.1, we present a recursive lower bound for κ k . Section 3.2 states spectral bounds, explain the relation of the multi-step coarse Ricci curvature and spectral properties of the Markov chain, while Section 3.3 states bounds on the diameter of the state space. In Section 3.4, where we state variance, moment, and concentration bounds for Lipschitz functions of random variables distributed according to the stationary distribution of a Markov chain. Finally, we give error estimates MCMC empirical averages in Section 3.5.

Bounding the multi-step coarse Ricci curvature
Our first proposition, the so called geodesic property is useful to get bounds on κ k (similarly as in Proposition 19 of Ollivier (2009)).
Proposition 3.1. Suppose that (Ω, d) is ǫ-geodesic in the sense that for any two points x, y ∈ Ω, there exists an integer n, and a sequence x 0 = x,x 1 , . . . , x n = y such that d(x, y) = Let k ≥ 1, then if κ k (x, y) ≥ κ k for any pair of points x, y with d(x, y) ≤ ǫ, then κ k (x, y) ≥ κ k for any pair of points x, y ∈ Ω.
Proof. Apply Proposition 19 of Ollivier (2009) to the Markov kernel P k .
The following proposition gives a recursive lower bound on the multi-step Ricci curvature κ k (x, y).
Proposition 3.2. For some x, y ∈ Ω, x = y, let (X, Y ) be a coupling of P x and P y , then If (X, Y ) satisfies that E(d(X, Y )) = W 1 (P x , P y ) (that is, the coupling "achieves" the Wasserstein distance), then Proof. We are going to construct a coupling X k+1 ∼ P k+1 x , Y k+1 ∼ P k+1 y as follows. We start from our coupling (X, Y ) of P x and P y , and for any a, b ∈ Ω, define as the optimal coupling between P k a , P k b , achieving E(d(X k+1 , Y k+1 )|X = a, Y = b) = W 1 (P k a , P k b ). Then we have and thus Finally, if (X, Y ) is the optimal coupling between P x , and P y , then E(d(X, Y )) = (1 − κ(x, y))d(x, y), and the second claim of the proposition follows.
Suppose that everywhere except in a small part of the state space Ω, κ(x, y) > 0 for neighbouring x and y. Then this result says that κ k+1 (x, y) can be lower bounded by some sort of average of κ k (x, y), and for sufficiently large k, the negative curvature may disappear. In Section 4.3, we are going to apply this result to a random walk on the binary cube with a forbidden region.

Spectral bounds
Our first result is a bound on the mixing time.
Proposition 3.3 (Relation of mixing time and coarse Ricci curvature). Let (Ω, d) be a metric space, and P (x, dy) a Markov kernel, as previously. Suppose that diam (Ω) < ∞, and there is d 0 > 0 such that for any Conversely, we have, for any ǫ > 0, k ≥ t mix (ǫ/2), which is the well known Bubley-Dyer path coupling bound. Our bound, however, does not require κ > 0, thus it is more general.
Proof of Proposition 3.3. For two disjoint x, y ∈ Ω, k ≥ 1, we have Averaging out in y gives and this is less than equal to ǫ if 1 − κ k ≤ ǫd 0 /diam (Ω). The proof of (3.2), based on Proposition 3.1, is left to the reader as exercise.
Now we give lower bounds on the spectral gap and the pseudo spectral gap.
Proposition 3.5 (Relation of spectral gap and coarse Ricci curvature). For reversible chains, for every k ≥ 1, Without assuming reversibility, for every k ≥ 1, with κ k (P * ) denoting the kth step coarse Ricci curvature of the time reversal of our Markov kernel, P * (x, dy).
Remark 3.6. In Section 4.1, we are going to use this result to obtain a lower bound for the spectral gap of the split-merge walk on partitions. Another application is given in Section 4.2.2, where we use this proposition to bound the pseudo spectral gap of the systemic scan Glauber dynamics in the high temperature regime.

Diameter bounds
Our first result in this section is an analogue of Proposition 23 of Ollivier (2009).
Proposition 3.7 (L 1 Bonnet-Myers theorem). For k ≥ 1, let the k-step jump length of the random walk at x be Suppose that for some k ≥ 1, κ k (x, y) > 0 for every x, y ∈ Ω. Then for every x, y ∈ Ω, we have and in particular, Proof. Apply Proposition 23 of Ollivier (2009) to P k .
Remark 3.8. In Section 4.1, we are going to apply this proposition to splitmerge walk on partitions, and obtain a bound on diameter of Ω of O(N ).
Proposition 3.9 (Average L 1 Bonnet-Myers theorem). Suppose that for some k ≥ 1, κ k (x, y) > 0 for all x, y ∈ Ω. Then for any x ∈ Ω, we have and thus, Proof. Apply Proposition 24 of Ollivier (2009) to P k .
Remark 3.10. In Section 3.5, we are going to use this proposition for our bounds about MCMC empirical averages for non-stationary initial distributions.

Concentration bounds
Similarly to the results of Ollivier (2009), our concentration bounds will be based on 3 types of quantities related to the multi-step coarse Ricci curvature, the average step size of the Markov chain, and the dimension of the state space.
In order to avoid unnecessary repetitions in the statement of the theorems, we introduce some notations (similarly to Definition 18 of Ollivier (2009)).
Definition 3.11. Firstly, we make a few definitions related to the multi-step coarse Ricci curvature. Let us define, for any x, y ∈ Ω, The letter c refers to complement (we add up 1 − κ k (x, y) instead of κ k (x, y)). Secondly, we state some definitions related to the step size of the Markov chain. Let the (coarse) diffusion constant of the random walk at x be , and let the average diffusion constant be Similarly, define the mean square jump length aŝ , and the average mean square jump length aŝ σ := E π σ 2 1/2 .
Let the local granularity be σ ∞ (x) := 1 2 diam Supp P x (the diameter of the support of P x ), and the granularity be σ ∞ := sup x∈Ω σ ∞ (x). Define the maximal diffusion constant as σ max = sup x∈Ω σ(x), and the maximal mean square jump length asσ max = sup x∈Ωσ (x).
Finally, we state a definition related to the dimension of the state space. Let the local dimension at x be Remark 3.12. Using (2.3), we can see that κ c Σ can be bounded as The random walk can be divided into a drift term (corresponding to the change of the expected location), and a diffusion term (corresponding to the spread in space). The diffusion constant σ 2 (x) quantifies the diffusion term, when starting from point x.
The local dimension n(x) is a quantity related to the dimension of the state space Ω. In general, when Ω is an N dimensional Euclidean space (or surface of an N dimensional manifold), n(x) is related to N . We always have n(x) ≥ 1.
Our first concentration result is a variance bound for Lipschitz functions (generalising Proposition 32 of Ollivier (2009)).
Theorem 3.13 (Variance bound). For reversible chains satisfying for any 1-Lipschitz function f on (Ω, d), we have More generally, without using reversibility, we have Our next result is a moment bound for Lipschitz functions of reversible chains.
Theorem 3.14 (Moment bound for reversible chains). For reversible chains satisfying (3.6), for any 1-Lipschitz function f on (Ω, d), for any p ≥ 1, we have Now we state a concentration bound for reversible chains.

Theorem 3.16 (Concentration without reversibility). For any function
n(x) , and denote while for t > t max , we have the exponential bound (3.14) Remark 3.18. By comparing the concentration inequalities for reversible chains, and without using reversibility, there are some important differences. Firstly, Theorem 3.15 is not using the maximal jump diameter σ ∞ , thus it may give better bounds than Theorem 3.16 in cases when σ ∞ is very large (or infinity) compared to the typical jump length. However, Theorem 3.15 ignores the local dimension n(x), while Theorem 3.16 takes it into account, and thus it can give better bounds when n(x) ≫ 1. The variance, moment, and concentration bounds above can be applied to most of our examples in Section 4.

MCMC empirical averages
Joulin and Ollivier (2010) has proven variance bounds and concentration inequalities for MCMC empirical averages under the positive Ricci curvature assumption (κ > 0). Here we generalise these results using the multi-step Ricci curvature, and then compare them with inequalities in the literature obtained by spectral methods (for the proofs, see Section 5.3). Our results will prove variance and concentration bounds for the empirical , here t 0 is the so called "burn-in" time. For some initial distribution X 1 ∼ q, our results will show concentration of Z around its mean denoted by E q (Z). The following proposition (generalising Proposition 1 of Joulin and Ollivier (2010) Proposition 3.19 (Bound on the bias of empirical averages). For any Lipschitz The bound on the bias depends on the term W 1 (q, π), the Wasserstein distance of q and π. Let δ x be the measure concentrated on the point x. Then the Wasserstein distance of δ x and π is called the eccentricity of x (see Ollivier (2009), Joulin and Ollivier (2010)), and denoted by E(x) := y∈Ω d(x, y)dπ(y). Now by convexity, we have Moreover, it follows from Ollivier (2009), and Proposition 3.9, that (3.15) Our next result is a variance bound (generalising Theorems 2 and 3 of Joulin and Ollivier (2010)).
Theorem 3.20. (Variance bound for MCMC averages) Let and let K be a positive integer such that Remark 3.21. In the stationary case, we can set t 0 = 0, so the bound becomes The following results prove concentration inequalities for the empirical averages (generalising Theorems 4 and 5 of Joulin and Ollivier (2010)).
Theorem 3.22. (Concentration bound for MCMC averages) Let X 1 , X 2 , . . . be a Markov chain with initial distribution q (X 1 ∼ q). Let Z be as in (3.16), and let K be a positive integer such that κ K > 0. Let S max := sup x∈Ω Then for 0 ≤ t ≤ t max , we have the Gaussian bound while for t > t max , we have the exponential bound Theorem 3.23. Alternatively, suppose that σ 2 (x)/n(x) ≤ S(x) for some function S : Ω → Ê (for every x ∈ Ω). Denote Then for 0 ≤ t ≤ t ′ max , we have the Gaussian bound while for t > t ′ max , we have the exponential bound Remark 3.24. For stationary chains, we can set t 0 = 0, and W 1 (q, π) = 0, so the terms including them can be omitted.
Now we briefly compare these results to the variance bounds and Bernstein inequalities stated in Section 3 of Paulin (2014). If the function f is Lipschitz, and its range is quite large, then the range of the Gaussian tails (t max ) can be much larger than what we would get from Bernstein-type inequalities. Moreover, our results only use the Lipschitz coefficient of f , and the coarse Ricci curvature, which can be bounded theoretically. On the other hand, the Bernstein-type bounds also require the variance, and asymptotic variance of f , which are usually difficult to compute theoretically, and need to be estimated numerically (see Section 3 of Gyori and Paulin (2014) for more details). The main disadvantage of the Ricci curvature approach is that it is very sensitive to the Lipschitz coefficient of f , and may be less precise for non-smooth functions than Bernsteintype inequalities.

Applications
In this section, we present some applications of our results. Firstly, in Section 4.1, we use the multi-step Ricci curvature (in particular, Proposition 3.5 and Theorem 3.15) to prove spectral bounds for the transposition walk on the symmetric group, and get concentration inequalities for Lipschitz functions of uniform permutations. In Section 4.2 we apply our theorems to Markov chains related to statistical physical models. First, in Section 4.2.1, we show how Dobrushin's interdependence matrix is related to the multi-step Ricci curvature, for Glauber dynamics with random scan and systemic scan. In Sections 4.2.2 and 4.2.3, we apply these bounds to the Curie-Weiss and 1D Ising models, respectively. Finally, in Section 4.3, we present an application of the recursive lower bound for κ k to a random walk on a binary cube with a forbidden region.

Split-merge random walk on partitions
The partitions of N are m-tuples of positive integers (a 1 , . . . , a m ), such that a 1 ≥ a 2 ≥ . . . ≥ a m , m i=1 a i = N , and m ≤ n. Let us denote the set of the partitions of N by Ω. The split-merge random walk can be thought as the projection of the transposition random walk on the symmetric group S N to the partitions of N , according to the cycle structure of the permutations. In each step of the split-merge walk, we either split a part into two, merge two parts, or stay in place. For a precise definition of this walk, see Definition 2 of Bormashenko (2011). For x, y ∈ Ω, we define the distance d(x, y) as the minimal number of splits or merges required to get from x to y (or vice-versa).
The following proposition estimates the multi-step Ricci curvature κ k for this random walk on the metric space (Ω, d).
Proof. First, we are going to show that κ > 0. By Proposition 3.1, it is sufficient to show that for neighbouring x and y, that is, when d(x, y) = 1. Now it is easy to construct a coupling (X, Y ) of P x and P y such that d(X, Y ) ≤ 1, and P(X = Y ) = 2/n 2 . This means that (4.1) holds with κ = 2/n 2 . The fact that κ k ≥ β for k ≥ (α + 1/2)N follows from Lemma 17 of Bormashenko (2011).
Now we can apply our results on this example. Firstly, using Proposition 3.3, and the facts that diam (Ω) = N − 1, d 0 = 1, and Similarly, using Proposition 3.5, we can see that γ * ≥ κ k k ≥ β (α+1/2)N = O(1/N ). These are likely to be of the correct order of magnitude, since similar results hold for the transposition walk on the symmetric group (as shown in Diaconis and Shahshahani (1981)). Such bounds could not have been deduced using original coarse Ricci curvature approach of Ollivier (2009) Applying Proposition 3.7 shows that diam (Ω) ≤ 2(α + 1/2)N/β, which is the correct order of magnitude.
Finally, in our concentration bounds for reversible chains (Theorem 3.13 and Theorem 3.15), we have κ c Σ ≤ (α + 1/2)N/β, thus for any f : Ω → Ê that is 1-Lipschitz with respect to d, Var π (f ) ≤ (α + 1/2)N/β and Note that this result also follows from the concentration result for functions of random permutations (see Maurey (1979), and Talagrand (1995)), since the d(x, y) can be bounded from above by the transposition distance. It would be interesting to prove similar bounds for the transposition walk on the symmetric group, too. In fact, Bormashenko (2011) uses a connection between the two walks to bound the mixing time of the transposition walk on the symmetric group, based on a coupling argument for the split-merge walk on partitions. However, this approach does not seem to be applicable to the multi-step coarse Ricci curvature.

Glauber dynamics on statistical physical models
In this section, we are going to estimate the coarse Ricci curvature of the Glauber dynamics (with random, and systemic scan) on statistical physical models. A common property of these models is that we have some random variables (spins) X 1 , X 2 , . . . , X N , that are dependent on each other, and the strength of their dependence is influenced by a parameter β (inverse temperature).
In the following, in Section 4.2.1, first we define the Dobrushin interdependence matrix (a way to measure the strength of dependence between the random variables), and then state propositions that estimate κ k in terms of this matrix in the case of Glauber dynamics. In Sections 4.2.2 and 4.2.3, we apply our results to the Curie-Weiss, and the one dimensional Ising models.
. Given a Ω valued random vector X = (X 1 , . . . , X N ) with distribution µ, we say that a matrix A := (a ij ) i,j≤N is its Dobrushin interdependence matrix if a ii = 0 for i ≤ N , and for any x, y ∈ Ω, (4.2) Here µ i (·|x −i ) denotes the conditional distribution of the X i given X −i = x −i , and W 1 denotes the Wasserstein distance with respect to the distance d Λ . Finally, we say that µ satisfies the Dobrushin condition if A 1 < 1.

Remark 4.3. A frequently used special case of this is when
For examples using other types of distances, see Wu (2006).
Proposition 4.4 (Glauber dynamics with random scan). Let (Ω, d), µ and X and A be as in Definition 4.2. Consider the Glauber dynamics Markov chain on Ω as follows. In each step, we choose a coordinate I uniformly from [N ], and then replace X I with a conditionally independent copy, given X −I . Then for this Markov chain, we have This implies, in particular, that the absolute spectral gap γ * satisfies where sp(A) denotes the spectral radius of A.
Remark 4.5. Notice that tends to 0 as k → ∞ if and only if the spectral radius of A is strictly smaller than 1. This follows from the Gelfand's formula, which says that the spectral radius of a matrix M equals lim k→∞ M k 1/k , for any induced matrix norm. This is a less restrictive criteria than A 1 < 1. In particular, A ∞ < 1, or A 2 < 1 also suffices. See Wu (2006) for a spectral gap bound for Markov processes that is similar to (4.4).
Proof. The proof is similar to the proof of Theorem 4.3 of Chatterjee (2005). We start by defining a coupling of Ω valued random variables (X k , Y k ) k∈AE , satisfying that X k ∼ P k x , Y k ∼ P k y . First, let X 0 = x, and Y 0 = y. Suppose that we have already defined (X k , Y k ) 0≤k≤r . Then let I r be uniformly distributed in [N ]. Now we define X r and Y r as equal to X r−1 and Y r−1 except in their I r th component. We define X r Ir and Y r Ir as the coupling that minimises the Wasserstein distance of the distributions µ Ir (·|X r−1 −Ir ), µ Ir (·|Y r−1 −Ir ) (if the minimising distribution does not exist, then we can make a limiting argument). For this coupling, define the vectors (l k ) k≥0 taking values in Ê N as l k . Using the definition of the Dobrushin interdependence matrix, we can show that for k ≥ 0, where the inequality is meant in each component. From this, we can see that . Finally, (4.4) follows from Gelfand's formula, and (3.3).
Proposition 4.6 (Glauber dynamics with systemic scan). Let Ω, µ, X, and A be as in Definition 4.2. Consider a Markov chain such that in each step, we go through X 1 , . . . , X n in a row, and replace them with a conditionally independent copy given the rest. For 1 ≤ i ≤ N , define B i as a matrix equal to the identity matrix, except its ith row, which is the same as the ith row of A. Let B = B n · B n−1 · . . . · B 1 . Then for k ≥ 1, Remark 4.7. Similarly to the random scan case, B k 1 → 0 as k → ∞ if and only if the spectral radius of B is less than 1.
Remark 4.8. Dyer, Goldberg and Jerrum (2008) contains an estimation of the mixing time of the systemic scan Glauber dynamics under various forms of the Dobrushin condition. In particular, in Section 7 it is proven that for any x, y ∈ Ω, Proof of Proposition 4.6. The proof is similar to the proof of Proposition 4.4, but this time we need to show that l k+1 ≤ Bl k . The details are left to the reader.

Curie-Weiss model
For any ω ∈ Ω, let the Hamiltonian function be Here β > 0 is called the inverse temperature, and h is the external field. Define the probability distribution on Ω as where Z β,h CW is a normalising constant. In the zero magnetisation case (h = 0), this model is known to undergo phase transition at β = 1. We call β < 1 the high-temperature phase, β = 1 the critical phase, and β > 1 the lowtemperature phase.
When applying the Glauber dynamics chains (with random, or systemic scan) of the previous section to this model (see Propositions 4.4 and 4.6), the distribution π β,h CW arises as their stationary distribution. The following proposition estimates the multi-step coarse Ricci curvature of these chains. Proposition 4.9 (Ricci curvature for the Curie-Weiss model). For the Curie-Weiss model described above, for any h and β, for any k ≥ 2, we have Finally, for β = 1 and h = 0 (the critical phase), there exists a universal constant C > 0 such that for any N , any k ≥ CN 3/2 log(N ), κ Gl.rand.scan. k ≥ 1/2, and (κ c Σ ) Gl.rand.scan. ≤ 2CN 3/2 log(N ).
Proof. A simple calculation shows that for the Curie-Weiss model, the following matrix is a Dobrushin interdependence matrix for any β and h (albeit not the sharp one for h = 0).
Since A CW 1 < β(N − 1)/N , κ Gl.rand.scan. ≥ 1 − β(N − 1)/N by Proposition 4.4. For the Glauber dynamics with systemic scan, we apply Proposition 4.6 with the Dobrushin interdependence matrix A CW . Let x := β/N , then after some calculations, we obtain that the matrix B is given by imum column sum), with 1 denoting a row vector of ones, and max denoting the maximal element of the vector. After a simple calculation, we get that for As we can see, κ is negative for part of the high temperature case (β < 1). Now we will use the following lemma.
Proposition 4.11. In the critical phase of the Curie-Weiss model (β = 1, h = 0), for any f : Ω → Ê that is 1-Lipschitz with respect to d (Hamming distance), for any t ≥ 0, where X ∼ π 1,0 CW , and C is an universal constant. Remark 4.12. This most likely holds without the log(N ) term as well. The constant in the exponent should be at least of order N 3/2 , as one can see from the limiting distribution of the magnetisation (f (ω) = N i=1 ω i ), where one has to normalise by N 3/4 (see Chatterjee and Shao (2011), page 466). Proposition 4 of Chatterjee and Dey (2010) shows a subgaussian (exp(−ct 4 )) concentration bound for the magnetisation.

1D Ising model
Let Ω = {−1, 1} N . Let d be the Hamming distance on Ω, as in the previous section. For any ω ∈ Ω, let the Hamiltonian function be Here β > 0 is called the inverse temperature, and h is the external field. Define the probability distribution on Ω as where Z β,h I1D is a normalising constant. This model is known to have no phase transition. The following proposition applies our results on this model, assuming that h = 0.

Random walk on a binary cube with a forbidden region
Consider a binary cube Ω 0 := {0, 1} N . We call the region F := {x ∈ Ω 0 , x i < R} the forbidden region. Let Ω := Ω 0 \ F . We consider the following random walk (a version of Glauber dynamics) on Ω. If we are in x, then we pick an index I out of {1, . . . , N } uniformly, and x i = R, and x I = 1, then we do nothing, and stay in x. The stationary distribution π is the uniform distribution on Ω (the random walk can be shown to be reversible with respect to this distribution). Because of the geodesic property, it is sufficient to look at κ k (x, y) for neighbouring x and y. Because of symmetry, we can denote this by κ k (j) := κ k (x, y) for x such that . Initially, we have negative curvature, From Proposition 3.2, we get the recursive bounds for R < j ≤ N − 1. Notice that all the coefficients of κ k (j) in these inequalities are positive. This implies that if we letκ 1 (j) := κ 1 (j) for R ≤ j ≤ N − 1, and letκ It is easy to conduct numerical simulations to see the behaviour of this recursion. The figures below show this for N = 500, R = 100. The figures show that initiallyκ k is decreasing, and stays negative, but eventually the positive curvature wins, andκ k becomes positive. The following proposition gives bounds on κ n and κ c Σ based on this recursion.

Proofs of concentration results
In this section, we present the proofs of our concentration inequalities. First, we briefly review Chatterjee's method of proving concentration inequalities via Stein's method of exchangeable pairs. We prove our variance and concentration bounds for reversible chains using this approach. Finally, we prove our variance and concentration bounds without using reversibility, by a modification of Ollivier's proofs.

Concentration inequalities via the method of exchangeable pairs
For the proof of our theorems about reversible chains, we will use Stein's method of exchangeable pairs for concentration inequalities, developed in Chatterjee (2005). Let (X, X ′ ) be an exchangeable pair taking values in a Polish space and assume that ∆(X) < ∞ almost surely. Then the following results hold.
Conversely, for a reversible Markov kernel P on Ω with stationary distribution π, we define an exchangeable pair as X ∼ π, and P(X ′ ∈ A|X = x) := P (x, A). The following lemma explains the construction of F (x, y) (this is a straightforward extension of Lemma 4.1 of Chatterjee (2005)).
(5.2) Then the function Now by (5.2), and Lebesgue's dominated convergence theorem, the left hand side will converge to a limit as N → ∞. For the right hand side, we have P N +1 f (y) − P N +1 f (x) → 0 by (5.2) for any x, y ∈ Ω. The expected value of both sides of (5.4) is 0, so lim N →∞ P N +1 f (x) = 0 for every x ∈ Ω, and the claim of the lemma follows.

Concentration of Lipschitz functions under the stationary distribution
We start with the variance bounds.
Proof of Theorem 3.13. Without loss of generality, assume Ef (X) = 0. Let (X, X ′ ) be the exchangeable pair induced by the Markov kernel P , then it is easy to see that . Condition (3.6) ensures that E(L(X, X ′ )|X) < ∞ almost surely, and Lemma 5.5 gives (5.5) By Theorem 5.1, we obtain that Now we turn to the non-reversible case. The proof of this part is similar to the proof of Proposition 32 of Ollivier (2009). Assume first that f ∞ < ∞. Then Var(f ) < ∞. Now we will show that if κ c Σ < ∞, then Var(P k f ) → 0 as k → ∞. Let B r be a ball of radius r centred at some point in Ω, then we can write If we set r = (1 − κ k ) −1/2 , then this will tend to 0 as k → ∞, since κ c Σ < ∞ implies that 1 − κ k → 0. Moreover, if κ c Σ = ∞, our bound is vacuous, so there is nothing to prove. Now it is easy to show that and then using Var(P k f ) → 0, we get Now P k (f ) is (1 − κ k )-Lipschitz, so by the definition of the local dimension n(x), we have Var Px (P k (f )) ≤ (1 − κ k ) 2 σ 2 (x)/n(x), and (3.8) follows. Finally, the f ∞ = ∞ case can be handled by a limiting argument. Now we prove concentration for the reversible case.
Proof of Theorem 3.15. As in the proof of Theorem 3.13, we can show that F (x, y) = ∞ k=0 (P k f (x) − P k f (y)), and thus Σσ 2 max , (5.6) and we get (3.9) by Theorem 5.3. From Theorem 5.3 applied to g(X) = ∆(X) − E(∆(X)) it follows that for any L > 0, Our next proof is the moment bound for reversible chains.
Proof of Theorem 3.14. From (5.6), we have ∆(X) ≤ 1 2 κ c Σσ (X) 2 , and applying Theorem 5.2 leads to this result. Now we prove concentration bounds without using reversibility. The proof of Theorem 3.16 is based on the following two lemmas (the first one is a slight variation of Lemma 38 of Ollivier (2009)).
Let t max := 2Cλ max , then for 0 ≤ t ≤ t max , we have and for t ≥ t max , we have Proof. This follows by the standard Markov inequality argument.

Concentration bounds for MCMC empirical averages
We start with the proof of the bias bound.
Proof of Proposition 3.19. It follows from the definitions that summing up from j = t 0 to N , and using 1 − κ t0+i ≤ (1 − κ t0 )(1 − κ i ) leads to this result.
We will use the following lemma (a generalisation of Lemma 9 of Joulin and Ollivier (2010)) in the proof of the variance bound (Theorem 3.20).
Lemma 5.8. For any N ≥ 1, x ∈ Ω, f : Ω → Ê, Proof. For simplicity, we omit to note the dependence in x in the following inequalities. We have

Now by the definitions it follows that
, and more generally, thus summing up leads to the result.
Proof of Theorem 3.20. First, we are going to cut the sum Z into K parts. For 1 ≤ r ≤ K, let Var q (Z r ). Now, we are going to bound Var q (Z r ), for each 1 ≤ r ≤ K. Let N r := ⌊(N − t 0 − r)/K⌋ + 1, define F (r) x1,...,xN r −1 (x Nr ) := Z r , and define, by downward induction, for each 1 ≤ i ≤ N r − 1, Finally, let Then by Lemma 3.2 (step 1) of Joulin (2009), we can show that F (r) x1,...,xi−1 is Lipschitz with constant s i given by .
A simple argument shows that thus summing up in r proves the claim of the theorem.
The proof of Theorem 3.22 is based on the following lemma (a generalisation of Lemma 10 of Joulin and Ollivier (2010)).
Proof. This result follows by the repeated application of Lemma 5.6.
The proof of Theorem 3.23 is based on the following lemma (a generalisation of Lemma 10 of Joulin and Ollivier (2010)).
In particular, Proof. This is a consequence of (5.9) and (5.10).