Spectral Gap and log–Sobolev Constant for Balanced Matroids

Mark Jerrum^{∗} Division of Informatics University of Edinburgh The King’s Buildings Edinburgh, EH9 3JZ, UK

mrj@dcs.ed.ac.uk

Jung–Bae Son^{†} Division of Informatics University of Edinburgh The King’s Buildings Edinburgh, EH9 3JZ, UK j.b.son@sms.ed.ac.uk

We compute tight lower bounds on the log–Sobolev constant of a class of inductively defined Markov chains, which contains the bases–exchange walks for balanced matroids studied by Feder and Mihail. As a corollary, we obtain improved upper bounds for the mixing time of a variety of Markov chains. An example: the “natural” random walk on spanning trees of a graph G as proposed by Broder — which has been studied by a number of authors — mixes in time O(mn log n), where n is the number of vertices of G and m the number of edges. This beats the best previous upper bound on this walk by a factor n^{2}.

1 Introduction

The most successful approach in recent years to sampling combinatorial structures (and hence estimating their number) has been Markov chain simulation. This technique is the basis of the so–called Markov chain Monte Carlo method. In order to obtain useful performance guarantees, it is important to have tight bounds on the convergence rates of the Markov chains in question to equilibrium. Our interest in this article is in a class of inductively defined Markov chains, which we call “π–recursive”. This class will be defined precisely in Section 3, but, roughly speaking, a π– recursive Markov chain is one that is either trivial or can be decomposed into two π–recursive (sub-) Markov chains, such that the transitions between the two chains support a matching of a certain kind.

The paradigmatic example of a π–recursive Markov chain is the Boolean cube, but the class extends well beyond this simple case to cover, for example, the “bases–exchange walk” (Alg. 6.1) on balanced matroids studied by Feder and Mihail [7]. The main results of this paper are lower bounds on the spectral gap (Theorem 4.4) and log–Sobolev constant (Theorem 5.4) of π–recursive Markov chains. Our approach yields a tight bound on spectral gap for the random walk on the Boolean cube (cf. Example 6.3). Furthermore, our bound on log–Sobolev constant for the cube is within a factor 4 of the spectral gap. Thus, owing to a result by Rothaus [19], our bound on the log–Sobolev constant is tight up to a constant factor.

Both spectral gap and log–Sobolev constant of the cube were already known by other methods [5]; however, the advantage of our “hands–on” approach is that it is robust and extends to π–recursive Markov chains in general. Since the log–Sobolev constant is more tightly related to mixing time, as measured by convergence to stationary in total variation distance, we obtain mixing times that are typically about Õ(k) shorter than those currently known. Here k is the roughly the “dimension” of the Markov chain, or the depth of recursion defining it.

As a specific example, consider the “natural” random walk on spanning trees of a graph G as defined by Broder [3]: Suppose the current spanning tree (state) is T; choose an edge e ∈ E(G) and another f ∈ T uniformly at random (u.a.r.); if T′ = T ∪ {e} \ {f} is a spanning tree then T′ is the new state, otherwise we remain at T. (This is a special case of the bases–exchange walk for matroids mentioned earlier.) We show that the mixing time of this random walk is O(mn log n), where n is the number of vertices of G and m the number of edges. As far as we are aware, the best previously known bound^{1} was O(mn^{3} log m), established by Feder and Mihail.

The rest of the paper is organised as follows. In Section 2 we give definitions of spectral gap and log–Sobolev constants and how they result in bounds on mixing time. Section 3 defines the above mentioned π–recursive Markov chains. In Section 4 lower bounds on the spectral gap of such Markov chains are derived and in Section 5 lower bounds on the log–Sobolev constant. Section 6 contains applications of the results found in Section 4 and 5.

∗supported by EPSRC grant “Sharper Analysis of Randomized Algorithms: a Computational Approach” and the IST Programme of the EU under contract IST-1999-14036 (RAND-APX)

†supported by a DAAD grant

1Note that this is the best result for general m and n. For particular m and n there exist better results, e.g. [18]. Also note that the modified random walk by Feder and Mihail can mix faster.

2 Spectral gap, log–Sobolev constants and mixing time

Unless stated otherwise, let throughout the paper M = (X_{0}, X_{1}, X_{2}, …) be a time–reversible, irreducible and aperiodic Markov chain on finite state space Ω with transition kernel P (x, y). Since M is finite, irreducible and aperiodic, it is also ergodic and has a unique stationary distribution π. Furthermore,

P^{t}(x, y) = Pr(X_{t} = y | X_{0} = x),

the probability that after t steps the chain M is at state y if it was initially at state x, converges toward the stationary distribution, i.e. lim_{t→∞} P^{t}(x, y) → π(y) for all x, y ∈ Ω. For the Markov chain Monte Carlo method to be of any practical significance, the Markov chain M has to converge quickly towards its stationary distribution. The earliest techniques for bounding the rate of convergence (or mixing time) were coupling [1] and conductance [14]. Since then, an abundance of work has been carried out and we refer readers to survey articles such as [16] and [12] and the references given therein. This might be particularly helpful to readers unfamiliar with this area since here, we will only mention concepts immediately relevant for this paper.

Given two probability distributions μ and ζ on state space Ω their total variation distance is

∥μ − ζ∥_{TV} = \frac{1}{2} ∑_{x∈Ω} |μ(x) − ζ(x)| .

There are various definitions of mixing time τ. Here let it be defined as

τ = max_{x∈Ω} min {t > 0 : ∥P^{t}(x, ·) − π∥_{TV} ≤ e^{−1}} .

Among the various techniques for bounding mixing time are spectral gap and logarithmic–Sobolev constants. The logarithmic Sobolev constant of a chain M is defined as

α_{M} = inf_{f} \{\frac{E_{M}(f, f)}{L_{π}(f)} : L_{π}(f) ≠ 0\} ,

where f : Ω → ℝ,

E_{M}(f, f) = \frac{1}{2} ∑_{x,y∈Ω}(f(x) − f(y))^{2}π(x)P (x, y)

is the Dirichlet–form with respect to the Markov chain M with transition kernel P and stationary distribution π, and

L_{π}(f) = ∑_{x∈Ω} |f(x)|^{2}π(x) log \frac{|f(x)|^{2}}{∥f∥_{2,π}^{2}}

is an entropy like quantity, with

∥f∥_{2,π} = \sqrt{∑_{x∈Ω} |f(x)|^{2}π(x)}.

Formally, the log–Sobolev constant resembles the definition of the spectral gap

λ_{M} = inf_{f} \{\frac{E_{M}(f, f)}{Var_{π}(f)} : Var_{π}(f) ≠ 0\} ,

f : Ω → ℝ, of the chain, where Var_{π}(f) is variance with respect to (w.r.t.) probability distribution π. But while spectral gap can be regarded as the difference between the first two largest eigenvalues of the transition kernel P (x, y), there seems to be no analogous interpretation for log– Sobolev constants. The bounds on mixing time using spectral gap and log–Sobolev constants [5] are:

τ ≤ \frac{2 + log[1/π_{∗}]}{2λ}

and

τ ≤ \frac{4 + log log[1/π_{∗}]}{4α},  (1)

where π_{∗} = min_{x∈Ω} {π(x)} (we dropped the subscripts of α and λ as they were inessential). Suppose that n measures input size, then typically 1/π_{∗} = 2^{O(n)}; thus using (1) gains a factor of n/ log n whenever λ and α are of similar magnitude. It has been shown that α ≤ λ/2 (see [19], [5]). However, in contrast to spectral gap, log–Sobolev constants are notoriously hard to compute. But in the few cases where both spectral gap and log–Sobolev constant are explicitly known the above bound has proven to be amazingly tight: for the symmetric two–point space, the Ornstein–Uhlenbeck process on ℝ^{d} or the standard diffusion on the n–sphere α = λ/2 (see [2], [8], [9]). A diffusion where α = λ/4 is given in [15]. On the other hand, cases are known where α ≪ λ. Examples are random walks on generic regular r–graphs (see [5]) or complete graphs (see [11]). Very recent work [11] shows how quantities that are easier to compute, e.g. spectral gap or conductance, can be used to lower bound log–Sobolev constants. Here, we will directly compute the spectral gap and log– Sobolev constant of π–recursive Markov chains and show that our bound on the log–Sobolev constant is sometimes tight up to a constant factor. This is achieved by splitting the chain up into two sub–chains and applying induction to obtain the desired result. Other work where decomposition yields bounds on spectral gap and log–Sobolev constant is [4] and [17].

3 π–recursive Markov chains

Let G = (V, E) be an undirected graph. The subgraph G_{S} of G induced by a subset S ⊆ V has vertex set S and edges E_{S} = {{x, y} ∈ E | x, y ∈ S}.

Let M = (Ω, P) be a Markov chain. Recall that we stipulated that M be finite, time–reversible, irreducible and aperiodic. Hence, it converges towards a unique stationary distribution, say π. For S ⊆ Ω the restriction chain of M on S is the Markov chain M_{S} = (S, P_{S}) with

P_{S}(x, y) = \{ \begin{matrix}P (x, y) & if x, y ∈ S, x ≠ y \\ 1 − ∑_{{y∈S \atop y≠x}} P (x, y) & if x = y. \end{matrix}

Notice that M = M_{Ω}. Since M is time–reversible, it fulfils the detailed balance condition, which says that

π(x)P (x, y) = π(y)P (y, x) for all x, y ∈ Ω.

This condition is extremely useful because if a probability distribution μ meets detailed balance, then μ is a stationary distribution. Now observe that if M_{S} itself is irreducible, then its unique stationary distribution is π_{S}, where π_{S}(x) = π(x)/π(S) for x ∈ S and π(S) = ∑_{x∈S} π(x); this is because π_{S} fulfils detailed balance (or equivalently M_{S} is time–reversible with respect to π_{S}).

Observe that M is equivalent to a random walk on an undirected graph G = (V, E) with V = Ω and E = {{x, y} | P (x, y) > 0} where for current vertex x the subsequent vertex y is chosen with probability P (x, y). Call G the underlying graph of M. Let A ≠ ∅, Ā ≠ ∅ be a bipartition of Ω. The set of crossedges C(A, Ā) ⊆ E is the set of edges with one endpoint in A and the other in Ā. Any assignment w : C(A, Ā) → ℝ^{+} satisfying

∑_{y∈Ā} w(x, y) = π_{A}(x) and ∑_{x∈A} w(x, y) = πĀ(y)

is a π–matching. The graph G is called π–matchable if there exists a bipartition A, Ā that allows a π–matching. The breaking up of G into the disjoint subgraphs G_{A} and GĀ such that A, Ā allows a π–matching is referred to as a split (of G) (or alternatively we say that G is split into G_{A} and GĀ). By a series of splits we mean a sequence G = G_{S_{1}}, G_{S_{2}}, …, G_{S_{l}} = G_{S}, l ∈ ℕ, where each G_{S_{i}}, i = 2 … l, is obtained by splitting G_{S_{i−1}} and G_{S} is said to be obtained by a series of splits. A Markov chain M is π–recursive on G if:

1. Ω is of size 1, or

2. G is π–matchable and if G is split into, say G_{A} and GĀ, then M_{A} is π_{A}–recursive on G_{A} and MĀ is πĀ– recursive on GĀ.

A prototypical example is the random walk on the Boolean cube.

4 Spectral gap of π–recursive Markov chains

Our ultimate goal is to establish a lower bound on the log–Sobolev constant. However our approach is more easily understood in the context of spectral gap. So we consider this parameter first, on the one hand as a warm up exercise, on the other as a benchmark for our bound on the log–Sobolev constant.

Suppose that M = (Ω, P) is π–recursive on an underlying graph G = (Ω, E). The main result of this section is a lower bound on the spectral gap of M (Theorem 4.4). The idea of the proof is to find a value λ̂_{M} s.t. E_{M}(f, f) ≥ λ̂_{M}Var_{π}(f) for all f : Ω → ℝ. Then, from the definition of spectral gap, λ_{M} ≥ λ̂_{M} is an immediate consequence. We will find such a value λ̂_{M} by decomposition/induction.

The first ingredient is the observation that variance and Dirichlet form can be split up w.r.t. a partition of the state space:

Lemma 4.1 Let A, Ā be a partition of Ω, f : Ω → ℝ and π a probability distribution on Ω, then

Var_{π}(f) = π(A)Var_{π_{A}}(f) + π(Ā)Var_{πĀ}(f) + ct_{Var_{π}}(f),

where

ct_{Var_{π}}(f) = π(A)π(Ā)(E_{π_{A}}[f] − E_{πĀ}[f])^{2}

is a weighted crossterm,

E_{π_{A}}[f] = ∑_{x∈A} π_{A}(x)f(x),

Var_{π_{A}}(f) = ∑_{x∈A} π_{A}(x) (f(x) − E_{π_{A}}[f])^{2}

are expectation and variance w.r.t. π_{A} and similarly for E_{πĀ}[f] and Var_{πĀ}(f).

Proof. Despite the fact that the lemma is standard knowledge now, we will include a proof for the sake of completeness. A proof of

Var_{π}(f) = π(A)Var_{π_{A}}(f) + π(Ā)Var_{πĀ}(f)
+ π(A)(E_{π_{A}}[f] − E_{π}[f])^{2}
+ π(Ā)(E_{πĀ}[f] − E_{π}[f])^{2}

can be found in [13]. Now, observe that

π(A)(E_{π_{A}}[f] − E_{π}[f])^{2} + π(Ā)(E_{πĀ}[f] − E_{π}[f])^{2}

= π(A)(E_{π_{A}}[f] − π(A)E_{π_{A}}[f] − π(Ā)E_{πĀ}[f])^{2}

+ π(Ā)(E_{πĀ}[f] − π(A)E_{π_{A}}[f] − π(Ā)E_{πĀ}[f])^{2}

= π(A)(π(Ā)E_{π_{A}}[f] − π(Ā)E_{πĀ}[f])^{2}

+ π(Ā)(π(A)E_{πĀ}[f] − π(A)E_{π_{A}}[f])^{2}

= π(A)π(Ā)^{2}(E_{π_{A}}[f] − E_{πĀ}[f])^{2}

+ π(Ā)π(A)^{2}(E_{πĀ}[f] − E_{π_{A}}[f])^{2}

= π(Ā)π(A)(E_{πĀ}[f] − E_{π_{A}}[f])^{2}.

□

Similarly,

Lemma 4.2 For a partition A, Ā of Ω, f : Ω → ℝ and a probability distribution π on Ω

E_{M}(f, f) = π(A)E_{M_{A}}(f, f) + π(Ā)E_{MĀ}(f, f) + ct_{E_{M}} (f),

where ct_{E_{M}} (f) = ∑_{{x∈A \atop y∈Ā}} (f(x) − f(y))^{2}π(x)P (x, y).

Proof. As before, the lemma is standard and the proof included for the sake of completeness. Observe that given a partition A and Ā the Dirichlet form can be rewritten as

E_{M}(f, f) = \frac{1}{2} ∑_{x,y∈A}(f(x) − f(y))^{2}π(x)P (x, y)

+\frac{1}{2} ∑_{x,y∈Ā}(f(x) − f(y))^{2}π(x)P (x, y)

+ ∑_{{x∈A \atop y∈Ā}}(f(x) − f(y))^{2}π(x)P (x, y).

Since

π(A)E_{M_{A}}(f, f) = \frac{1}{2} ∑_{x,y∈A}(f(x) − f(y))^{2}π(x)P (x, y)

and

π(Ā)E_{MĀ}(f, f) = \frac{1}{2} ∑_{x,y∈Ā}(f(x) − f(y))^{2}π(x)P (x, y),

the lemma holds. □

The following lemma is the main stepping stone for the induction in Theorem 4.4.

Lemma 4.3 Assume that M = (Ω, P) is a finite, time– reversible, irreducible and aperiodic Markov chain with stationary distribution π on a π–matchable graph G = (Ω, E). Then

ct_{E_{M}} (f) ≥ 2 min_{{x,y}∈E} {P (x, y)} ct_{Var_{π}}(f).

Proof. Since G allows a π–matching, there exists a bipartition A, Ā and an assignment w such that π(x)/π(A) = ∑_{y∈Ā} w(x, y) and thus E_{π_{A}}[f] = ∑_{{x∈A \atop y∈Ā}} w(x, y)f(x); similarly for E_{πĀ}[f]. Thus:

ct_{Var_{π}}(f)

= π(A)π(Ā)( ∑_{{x∈A \atop y∈Ā}} \sqrt{w(x, y)}(f(x) − f(y))\sqrt{w(x, y)} )^{2}.

Observe that ∑_{{x∈A \atop y∈Ā}} w(x, y) = 1. Applying the Cauchy– Schwarz inequality yields:

ct_{Var_{π}}(f) ≤ π(A)π(Ā) ∑_{{x∈A \atop y∈Ā}} w(x, y)(f(x) − f(y))^{2}.

Thus, to complete the proof it suffices to find a factor η such that

η π(A)π(Ā) ∑_{{x∈A \atop y∈Ā}} w(x, y)(f(x) − f(y))^{2}

≤ ∑_{{x∈A \atop y∈Ā}} π(x)P (x, y)(f(x) − f(y))^{2}.

Observe that since M is time–reversible, we can always choose A such that π(Ā) ≤ π(A). Furthermore, w(x, y) ≤ ∑_{y∈Ā} w(x, y) = \frac{π(x)}{π(A)}. Thus

π(A)π(Ā)w(x, y) ≤ π(A)π(Ā)\frac{π(x)}{π(A)}
≤ \frac{1}{2}π(x) ≤ \frac{π(x)P (x, y)}{2 min_{\{x,y\}∈E}\{P (x, y)\}}.

This shows that our claim is valid for η = 2 min_{{x,y}∈E}{P (x, y)}. □

The significance of Lemma 4.3 is that 2 min_{{x,y}∈E}{P (x, y)} is exactly the value λ̂_{M} we were looking for, i.e. it satisfies E_{M}(f, f) ≥ λ̂_{M}Var_{π}(f) for all f : Ω → ℝ. This is made rigorous next.

Theorem 4.4 Given a finite, time–reversible, irreducible and aperiodic Markov chain M = (Ω, P) with stationary distribution π on a graph G = (Ω, E) such that M is π– recursive on G. The spectral gap of M is lower bounded by twice the minimum transition probability of M, i.e.:

λ_{M} ≥ 2 min_{{x,y}∈E}{P (x, y)}.

Proof. It suffices to show that for any f : Ω → ℝ and for all S ⊆ Ω where G_{S} is obtained by a series of splits of G the following holds: E_{M_{S}}(f, f) ≥ 2 min_{{x,y}∈E}{P (x, y)} Var_{π_{S}}(f). The proof is by induction on the size of the state space of the restriction chain M_{S} = (S, P_{S}). For |S| = 1 the variance Var_{π_{S}}(f) = \frac{1}{2} ∑_{x,y∈S}(f(x) − f(y))^{2}π_{S}(x)π_{S}(y) = 0 and the induction hypothesis is trivially true.

Assume that |S| > 1 and M_{S} has stationary distribution π_{S}. Since M is π–recursive on G, the chain M_{S} is π_{S}– recursive on G_{S}. Thus there is a split of G_{S} into, say G_{A}, GĀ. By Lemma 4.2: E_{M_{S}}(f, f) = π_{S}(A)E_{M_{A}}(f, f) + π_{S}(Ā)E_{MĀ}(f, f)+ct_{E_{M_{S}}} (f) which is by induction hypothesis greater than 2 min_{{x,y}}{P (x, y)}(π_{S}(A)Var_{π_{A}}(f) + π_{S}(Ā)Var_{πĀ}(f)) + ct_{E_{M_{S}}} (f). By Lemma 4.3: ct_{E_{M_{S}}} (f) ≥ 2 min_{{x,y}∈E}{P (x, y)}ct_{Var_{π_{S}}} (f). Thus, applying Lemma 4.1 we obtain: E_{M_{S}}(f, f) ≥ 2 min_{{x,y}∈E}{P (x, y)} Var_{π_{S}}(f). □

Remark: An unnatural feature of Theorem 4.4 (and later Theorem 5.4) is that the existence of one single lowprobability transition is enough to degrade the bound. What we mean is the following: let M = (Ω, P) be a Markov chain whose transition probabilities are similar in size (i.e. differ by at most a small constant factor). We define a “perturbed chain” M^{†} = (Ω, P^{†}) whose transition probabilities agree with M except between a pair of distinguished states x and y. For this pair x, y, we arrange that P (x, y) = P (y, x) = 0 while 0 < P^{†}(x, y), P^{†}(y, x) < δ, where δ is some small value much less than min_{{x,y}∈E}{P (x, y)}. (The stationary distribution π may be retained by choosing P^{†}(x, y) and P^{†}(y, x) to satisfy detailed balance.) Then our bound for λ_{M^{†}} is much smaller than that for λ_{M}, even though the spectral gap of M^{†} is actually slightly larger than that of M. This is counter–intuitive since the addition of a tiny extra edge should not have such a huge impact. This paradox can be resolved by a closer look at the proof of Lemma 4.3 and Theorem 4.4. Both continue to hold if 2 min_{{x,y}∈E}{P (x, y)} is replaced by

min_{\{x,y\}∈C(A,Ā)} \frac{π(x)P (x, y)}{π(A)π(Ā)w(x, y)}.  (2)

Thus, the tiny transition probability can be compensated for as long as the π–matching does not assign it significant weight. In general, this will apply whenever a vertex is incident to more than one edge of the cut. Thus, an alternative formulation of Lemma 4.3 and Theorem 4.4 involving (2) will be closer to the truth. However, later on we will only be dealing with Markov chains whose transition probabilities are uniform, i.e. all non–zero transition probabilities are identical, and for those chains the current versions of Lemma 4.3 and Theorem 4.4 are sufficiently well suited.

5 log–Sobolev constant of π–recursive Markov chains

A similar inductive proof can be used to obtain a lower bound on the log–Sobolev constant of π–recursive Markov chains. As before, we assume that M = (Ω, P) is π– recursive on the underlying graph G = (Ω, E) (Theorem 5.4). Again, we will identify a value α̂_{M} such that if G_{S} is obtained by a series of splits: E_{M_{S}}(f, f) ≥ α̂_{M}L_{π_{S}}(f) for all f : Ω → ℝ. The approach is along the same lines as the proof of Theorem 4.4. Similar to variance and Dirichlet–form, the entropy–like quantity L_{π}(f) can be split up with respect to a bipartition A, Ā of Ω.

Lemma 5.1

L_{π}(f) = π(A)L_{π_{A}}(f) + π(Ā)L_{πĀ}(f) + ct_{L_{π},}(f),

where

ct_{L_{π}}(f) = π(A) ∥f∥_{2,π_{A}}^{2} log \begin{matrix}∥f∥ & {2 \atop 2,π_{A}} \\ ∥f∥ & {2 \atop 2,π} \end{matrix}

+ π(Ā) ∥f∥_{2,πĀ}^{2} log \begin{matrix}∥f∥ & {2 \atop 2,πĀ} \\ ∥f∥ & {2 \atop 2,π} \end{matrix}

is a weighted crossterm,

∥f∥_{2,π_{A}} = \sqrt{∑_{x∈A} |f(x)|^{2} π_{A}(x)}

and

L_{π_{A}}(f) = ∑_{x∈A} |f(x)|^{2} π_{A}(x) log \begin{matrix}|f(x)| & 2 \\ ∥f∥ & {2 \atop 2,π_{A}} \end{matrix}

and accordingly for ∥f∥_{2,πĀ} and L_{πĀ}(f).

Proof. Again, the proof is standard and included merely for the sake of completeness. Recall that

L_{π}(f) = ∑_{x∈Ω} |f(x)|^{2} π(x) log \begin{matrix}|f(x)| & 2 \\ ∥f∥ & {2 \atop 2,π} \end{matrix} .  (3)

Splitting up (3) with respect to A, Ā yields

L_{π}(f) = ∑_{x∈A} |f(x)|^{2} π(x) log |f(x)|^{2}

+ ∑_{x∈Ā} |f(x)|^{2} π(x) log |f(x)|^{2}

− ∥f∥_{2,π}^{2} log ∥f∥_{2,π}^{2} .

Notice that ∥f∥_{2,π}^{2} = π(A) ∥f∥_{2,π_{A}}^{2} + π(Ā) ∥f∥_{2,πĀ}^{2} and

∑_{x∈A} |f(x)|^{2}π(x) log |f(x)|^{2}

= π(A)L_{π_{A}}(f) + π(A) ∥f∥_{2,π_{A}}^{2} log ∥f∥_{2,π_{A}}^{2} .

Then

L_{π}(f) = π(A)L_{π_{A}}(f) + π(Ā)L_{πĀ}(f)

+ π(A) ∥f∥_{2,π_{A}}^{2} log ∥f∥_{2,π_{A}}^{2}

+ π(Ā) ∥f∥_{2,πĀ}^{2} log ∥f∥_{2,πĀ}^{2}

− log ∥f∥_{2,π}^{2} (π(A) ∥f∥_{2,π_{A}}^{2} + π(Ā) ∥f∥_{2,πĀ}^{2} )

and observe that this is merely an alternative formulation of the claim. □

Section 4 related the crossterms of Dirichlet form to variance. Now, we have to relate the crossterms of Dirichlet form and L_{π}(f).

Lemma 5.2 Assume that M = (Ω, P) is a finite, time– reversible, irreducible and aperiodic Markov chain with stationary distribution π on a π–matchable graph G = (Ω, E). Then

ct_{E_{M}} (f) ≥ \frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\} ct_{L_{π}}(f).

Proof. Let A, Ā be a split of G. Using ln x ≤ x − 1 we obtain

ct_{L_{π}}(f) ≤ π(A) ∥f∥_{2,π_{A}}^{2} \frac{∥f∥_{2,π_{A}}^{2} − ∥f∥_{2,π}^{2}}{∥f∥_{2,π}^{2}}

+ π(Ā) ∥f∥_{2,πĀ}^{2} \frac{∥f∥_{2,πĀ}^{2} − ∥f∥_{2,π}^{2}}{∥f∥_{2,π}^{2}} .

Since ∥f∥_{2,π}^{2} = π(A) ∥f∥_{2,π_{A}}^{2} + π(Ā) ∥f∥_{2,πĀ}^{2} we see that the right–hand side of the above inequality is equal to

π(A)π(Ā)\frac{(∥f∥_{2,π_{A}}^{2} − ∥f∥_{2,πĀ}^{2})^{2}}{∥f∥_{2,π}^{2}} .

It is then enough to show that

ct_{E_{M}} (f) ≥ \frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\}

× π(A)π(Ā)\frac{(∥f∥_{2,π_{A}}^{2} − ∥f∥_{2,πĀ}^{2})^{2}}{∥f∥_{2,π}^{2}} .

This can be done with the help of two intermediate inequalities. The first is

∑_{{x∈A \atop y∈Ā}}(f(x) − f(y))^{2}π(x)P (x, y)

≥ \frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\} ∑_{{x∈A \atop y∈Ā}}(f(x) − f(y))^{2}w(x, y),

and the second one

∑_{{x∈A \atop y∈Ā}}(f(x) − f(y))^{2}w(x, y)

≥ π(A)π(Ā)\frac{(∥f∥_{2,π_{A}}^{2} − ∥f∥_{2,πĀ}^{2})^{2}}{∥f∥_{2,π}^{2}} .  (4)

As regards the first inequality, observe the following. Since M is time–reversible w.r.t. π, we can choose A such that π(Ā) ≤ π(A) without affecting the very first inequality which upper bounds ct_{L_{π}}(f) and remember that M allows a π–matching between A and Ā such that w(x, y) ≤ ∑_{y∈Ā} w(x, y) = \frac{π(x)}{π(A)}. Thus,

w(x, y) ≤ \frac{π(x)}{π(A)} ≤ 2 π(x) ≤ \frac{2 π(x)P (x, y)}{min_{\{x,y\}∈E}\{P (x, y)\}} .

This establishes the first inequality. To finish the proof we must show that the second inequality (4) is valid. Set F_{A} = ∑_{x∈A} |f(x)|^{2}π(x) and FĀ analogously, then the

RHS turns into \frac{π(A)π(Ā)}{(F_{A}+FĀ)}(\frac{F_{A}}{π(A)} − \frac{FĀ}{π(Ā)})^{2}. Observe that

∑_{{x∈A \atop y∈Ā}}(f(x) − f(y))^{2}w(x, y)

= \frac{F_{A}}{π(A)} − 2 ∑_{{x∈A \atop y∈Ā}} f(x)f(y)w(x, y) + \frac{FĀ}{π(Ā)}.

According to the Cauchy–Schwarz inequality

∑_{{x∈A \atop y∈Ā}} f(x)\sqrt{w(x, y)}f(y)\sqrt{w(x, y)} ≤ \sqrt{\frac{F_{A}FĀ}{π(A)π(Ā)}}

and so

∑_{{x∈A \atop y∈Ā}}(f(x) − f(y))^{2}w(x, y) ≥ (\sqrt{\frac{F_{A}}{π(A)}} − \sqrt{\frac{FĀ}{π(Ā)}} )^{2} .

It therefore suffices to show that

(\sqrt{\frac{F_{A}}{π(A)}} − \sqrt{\frac{FĀ}{π(Ā)}} )^{2} ≥ \frac{π(A)π(Ā)}{(F_{A} + FĀ)} (\frac{F_{A}}{π(A)} − \frac{FĀ}{π(Ā)})^{2}

which is equivalent to

(\sqrt{\frac{F_{A}}{π(A)}} − \sqrt{\frac{FĀ}{π(Ā)}} )^{2} ≥ π(A)π(Ā) (\frac{F_{A}}{π(A)} − \frac{FĀ}{π(Ā)})^{2} ,

where F_{A} + FĀ has been normalised to 1. Below, in Lemma 5.3 we will show that the last inequality is valid, which concludes the proof of Lemma 5.2. □

Lemma 5.3 Let x, y ∈ (0, 1). Then

(\sqrt{\frac{x}{y}} − \sqrt{\frac{1 − x}{1 − y}})^{2} − y(1 − y) (\frac{x}{y} − \frac{1 − x}{1 − y})^{2} ≥ 0.

Proof. The claimed inequality is equivalent to

1 − \frac{y(1 − y)(\frac{x}{y} − \frac{1−x}{1−y})^{2}}{(\sqrt{\frac{x}{y}} − \sqrt{\frac{1−x}{1−y}} )^{2}} ≥ 0

and hence to

y(1 − y) (\sqrt{\frac{x}{y}} + \sqrt{\frac{1 − x}{1 − y}} )^{2} ≤ 1.  (5)

Since x, y ∈ (0, 1), inequality (5) is equivalent to

\sqrt{x(1 − y)} + \sqrt{y(1 − x)} ≤ 1.

Then use x = cos^{2} a and y = sin^{2} b for a, b ∈ ℝ to conclude the proof. □

We can now formulate the main result

Theorem 5.4 Given a finite, time–reversible, irreducible and aperiodic Markov chain M = (Ω, P) with stationary distribution π on a graph G = (Ω, E) such that M is π– recursive on G. The logarithmic Sobolev constant of M is lower bounded by half the minimum transition probability of M, i.e.:

α_{M} ≥ \frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\}.

Proof. The proof is of a similar flavour as the proof of Theorem 4.4. It is carried out by induction on the size of state spaces of restriction chains of M. Let M_{S} = (S, P_{S}) with stationary distribution π_{S} be a restriction chain on underlying graph G_{S} = (S, E_{S}) obtained by a series of splits of G.

If |S| = 1, then π_{S}(x) = 1 for x ∈ S, in which case \frac{1}{2} ∑_{x,y∈S}(f(x) − f(y))^{2}π_{S}(x)P_{S}(x, y) ≥

\frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\} ∑_{x∈S} |f(x)|^{2} π_{S}(x) log \begin{matrix}|f(x)| & ^{2} \\ ∥f∥ & {2 \atop 2,π_{S}} \end{matrix} =

0 is trivially true.

Inductive step: As M_{S} is π_{S}–recursive, the underlying graph G_{S} can be split into two non–empty sets A and Ā such that: E_{M_{S}}(f, f) = π_{S}(A)E_{M_{A}}(f, f) + π_{S}(Ā)E_{MĀ}(f, f)+ct_{E_{M_{S}}} (f). By induction hypothesis this is greater than \frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\}(π_{S}(A)L_{π_{A}}(f) + π_{S}(Ā)L_{πĀ}(f)) + ct_{E_{M_{S}}} (f). By Lemma 5.2 this in turn is greater than \frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\}(π_{S}(A)L_{π_{A}}(f) + π_{S}(Ā)L_{πĀ}(f) + ct_{L_{π_{S}}} (f)) and finally using Lemma 5.1: E_{M_{S}}(f, f) ≥ \frac{1}{2} min_{\{x,y\}∈E}\{P (x, y)\}L_{π_{S}}(f). □

Remark: The bound on the log–Sobolev constant we state here is nearly tight in that any significant improvement, specifically by a factor greater than 2, would implicitly lead to an improvement in the bound on λ stated in Theorem 4.4. (This follows from the known inequality α ≤ λ/2 [19], [5]). But the bound in Theorem 4.4 is tight, e.g in the case of the hypercube.

6 Application

In this section we will discuss some applications of Theorem 4.4 and Theorem 5.4. The applications we have in mind are random walks on bases–exchange walks on balanced matroids.

6.1 Balanced matroids

Matroids are algebraic structures that capture the concept of linear independence. Formally, a pair M = (S, I) with a finite ground set S and independent sets I ⊆ 2^{S} forms a matroid if

1. ∅ ∈ I,

2. if A ∈ I and B ⊆ A then B ∈ I, and

3. if A, B ∈ I and |B| = |A| + 1 then there exists e ∈

B \ A such that A ∪ {e} ∈ I.

A matroid can be entirely defined by its set of maximal independent sets or bases B ⊆ 2^{S} (sometimes we will use B(M) to denote the bases of a matroid M or conversely M(B) to denote the matroid with bases B). Bases possess the following two properties:

1. all bases are of the same size, namely the rank of M and

2. for every pair of bases X, Y ∈ B and every element e ∈ X there exists an element f ∈ Y s.t. (X \ {e}) ∪ {f} ∈ B.

The properties of matroid bases suggest a very natural random walk on B. Define the bases–exchange graph G(M) = (B, E) as the undirected graph with vertex set B and two vertices X, Y ∈ G(M) are connected by an edge if |X ⊕ Y | = 2, i.e. only one element of X is not in Y and vice versa. In future, we will call every random walk on the bases–exchange graph a bases–exchange walk. As an example take the following random walk:

Algorithm 6.1 Let X be the current basis. We move on to basis X′ according to the rule

1.) Choose a ground set element e and an element f ∈ X u.a.r.

2.) If (X\{f})∪{e} ∈ B, then set X′ = (X\{f})∪{e}, otherwise let X′ = X (stay at the current basis).

Next, we introduce two important operations on matroids. For a ground set element e ∈ S the matroid M \ e obtained by deleting e has ground set S(M \ e) = S \ {e} and set of bases B(M \ e) = {X ∈ B | e ∉ X}. The matroid M/e obtained by contracting e has ground set S(M/e) = S\{e} and set of bases B(M/e) = {X \ {e} | X ∈ B ∧ e ∈ X}. Any matroid obtained from M by a series of contractions and deletions is a minor of M.

Let X be a basis chosen uniformly at random (u.a.r.) from B and e ∈ S a ground set element. With abuse of notation, let e denote the event e ∈ X and ē the event e ∉ X; juxtaposition expresses the conjunction of events, i.e. ēf means e ∉ X ∧ f ∈ X. A matroid is negatively correlated if the inequality Pr[ef] ≤ Pr[e]Pr[f] holds for all pairs of distinct elements e, f ∈ S. We say that a matroid M is balanced if M and all its minors are negatively correlated. All regular (and thus graphic) matroids are known to be balanced. Feder and Mihail introduced the notion of balance and showed that Algorithm 6.1 on balanced matroids has mixing time polynomial in the rank n and size of ground set m, i.e., is rapidly mixing (cf. [7]).

6.1.1 Fractional matchings

In the same paper ([7]), Feder and Mihail discovered that vertices of the bases–exchange graph G(M) of every balanced matroid have a natural bipartition into A, Ā, such that the transitions between A and Ā support a fractional matching. Let A and Ā be the natural isomorphic copies of B(M \ e) and B(M/e) in M respectively for some ground set element e. A fractional matching is a function ψ : A × Ā → ℕ assigning integer weights to the cutset (the edges of G(M) spanning A and Ā) such that

∀x ∈ A : ∑_{y∈Ā} ψ(x, y) = |Ā|

and

∀y ∈ Ā : ∑_{x∈A} ψ(x, y) = |A| .

Note that if π is uniform over A and Ā, then the probability distribution

P_{ψ} = ((x, y) ↦ \frac{ψ(x, y)}{|A| |Ā|}) : A × Ā → [0, 1]

on the cutset is a π–matching.

6.2 Spectral gap and log�Sobolev constant of balanced matroids

Let M = (B, P) be a bases–exchange walk with constant transition probabilities, i.e. P (x, y) = p if x ≠ y and x ∼ y, i.e. x and y are connected by an edge, and P (x, x) = 1 − ∑_{{x,y}∈E} P (x, y) > 0 (so that the chain is aperiodic), on a matroid M(B) and G(M(B)) = (B, E) the underlying bases–exchange graph. Note that M is finite and irreducible; thus it has unique stationary distribution π. Since M fulfils the detailed balance condition (i.e. is time–reversible) w.r.t. the uniform distribution on B, the stationary distribution π must be the uniform distribution on B. Observe that if M′ with bases B′ is a minor of M(B), then the restriction chain M_{B′} is time–reversible with stationary distribution 1/ |B′|. Furthermore if M is a balanced matroid, then every fractional matching gives rise to a \frac{1}{|B|}–matching with weights P_{ψ}(·, ·). These observations show that the bases–exchange walk M = (B, P) with constant transition probabilities is \frac{1}{|B|}–recursive on the bases–exchange graph^{2}.

Corollary 6.2 Let M = (B, P) be a bases–exchange walk with constant transition probabilities, i.e. P (x, y) = p if x ≠ y, x ∼ y and P (x, x) = 1 − ∑_{{x,y}∈E} P (x, y) > 0, on a balanced matroid M(B) with bases–exchange graph G(M(B)) = (B, E). The spectral gap and log– Sobolev constant of M are lower bounded by:

λ_{M} ≥ 2p and α_{M} ≥ \frac{p}{2}.

Proof. Apply Theorems 4.4 and 5.4. □ We will give two example applications of Corollary 6.2:

Example 6.3 Random walk on a hypercube:

Consider the d–dimensional hypercube. The vertices can be denoted by d–tuples from {0, 1}^{d} and edges connect vertices whose Hamming distance is 1, i.e. tuples that differ by exactly one entry. Consider the random walk M with transition probabilities P (x, y) = 1/(d + 1) whenever x and y are connected by an edge. This random process has been studied quite extensively before (see [6] and the references given therein) and has uniform stationary distribution π(x) = 1/2^{d}. It is already known that the walk on the hypercube has spectral gap λ = 2/(d + 1) and log–Sobolev constant α = 1/(d + 1) (see [5] and [6] for a discussion). There are several ways to see that this Markov chain is π– recursive. The easiest way is to split the hypercube into two sub–cubes of dimension d − 1. Since each vertex of a sub– cube has only one neighbour in the other sub–cube, the π– matching is given by w(x, y) = 2/2^{d}. Using Theorem 4.4 and Theorem 5.4 we obtain the bounds λ ≥ 2/(d + 1) and α ≥ 1/2(d + 1). While our bound on spectral gap is identical to the aforementioned result, our bound on log– Sobolev constant is off by the factor 2. However, for the random walk on hypercubes it can be shown that Lemma 5.2 and Theorem 5.4 hold for ct_{E_{M}} (f) ≥ ct_{L_{π}}(f)/p, which recovers the result given in [5] by Diaconis and Saloff–Coste.

2Observe that some minors of a matroid are empty. This can happen if the minor is obtained by contracting an element that is in no basis or by deleting an element that is in every basis. In this case the minors do not constitute a split. However, unless a matroid has only one basis, there will always exist non-empty minors and thus a split of the bases-exchange graph.

The next example is more interesting.

Example 6.4 Balanced matroids:

Let M be a matroid of rank n on a ground set S of size m. Assume that transitions are done as specified in Algorithm 6.1. For the sake of simplicity add self–loops with probability at least 1/2 and reduce all other transition probabilities by 1/2, i.e. P (x, y) = 1/2mn for x ∼ y and P (x, x) = 1 − ∑_{{x,y}∈E} P (x, y) ≥ 1/2, this will ensure that M is irreducible, aperiodic and time–reversible w.r.t. the uniform distribution on B. If M is balanced, then applying Theorem 5.4 yields the lower bound α ≥ 1/4mn on the log–Sobolev constant. Remember that log–Sobolev constants can be used to upper bound mixing time thus by (1) we obtain: τ ≤ O(mn(log n + log log m)). This greatly improves on the mixing time for this walk given in [18]: τ ≤ O(m^{3/2}n^{2}(log n + log log m)). Using a result by Heller [10] which says that for simple regular matroids, i.e. regular matroids with no parallel elements, m < n(n + 1) we can infer that for regular matroids with only a constant number of parallel elements m = O(n^{2}). Thus for such matroids our bound on the log–Sobolev constant yields a mixing time of O(n^{3} log n) for this walk. This is at present the best bound on mixing time for this random walk on the bases–exchange graph of regular matroids with constant number of parallel elements^{3}.

Acknowledgement

We would like to thank the anonymous reviewer of this paper for an elegant and short version of the proof of Lemma 5.3.

References

[1] D. Aldous. Random walks on finite groups and rapidly mixing markov chains. In A. Dols and B. Eckmann, editors, Séminaire de Probabilités XVII 1981/82, number 986 in Springer Lecture Notes in Mathematics, pages 243–297. Springer, 1986.

[2] D. Bakry. L’hypercontractivité et son utilisation en théorie des semigroups. In Ecole d’Été de Saint Flour 1992, number 1581 in Lecture Notes in Mathematics. Springer, Berlin, 1994.

[3] A. Broder. Generating random spanning trees. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 442–447. IEEE, 1989.

[4] P. Caputo and F. Martinelli. Asymmetric diffusion and the energy gap above the 111 ground state of the quantum $xxz$ model. Communications in Mathematical Physics, 226(2):323–375, 2002.

[5] P. Diaconis and L. Saloff-Coste. Logarithmic sobolev inequalities for finite markov chains. Ann. Appl. Probab., 6(3):695–750, 1996.

[6] P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of markov chains. Ann. Appl. Probab., 1(1):36–61, 1991.

[7] T. Feder and M. Mihail. Balanced matroids. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 26–38. ACM Press, 1992.

[8] L. Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97:1061–1083, 1976.

[9] L. Gross. Logarithmic Sobolev inequalities and contractivity properties of semigroups. Number 1563 in Lecture Notes in Mathematics. Springer, Berlin, 1993.

[10] I. Heller. On linear systems with integral valued solutions. Pacific Journal of Mathematics, 7:1351–1364, 1957.

[11] C. Houdré. Mixed and isoperimetric estimates on the log– sobolev constants of graphs and markov chains. Combinatorica, 21(4):489–513, 2001.

[12] M. Jerrum. Mathematical foundations of the markov chain monte carlo method. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pages 116– 159. Springer Verlag, Berlin Heidelberg, 1998.

[13] M. Jerrum. Counting, sampling and integrating. In Algorithms and Complexity. Birkhäuser, Basel, 2002.

[14] M. Jerrum and A. Sinclair. Approximating the permament. SIAM Journal on Computing, 18:1149–1178, 1989.

[15] A. Korzeniowski and D. Stroock. An example in the theory of hypercontractive semigroups. Proceedings of the American Mathematical Society, 94:87–90, 1985.

[16] L. Lovász. Random walks on graphs: a survey. In Paul Erdös is Eighty (Volume 2), number 2 in Combinatorics, pages 1–46. Bolyai Society Mathematical Studies, Keszthely (Hungary), 1993.

[17] S. L. Lu and H.-T. Yau. Spectral gap and logarithmic sobolev inequality for kawasaki and glauber dynamics. Communications in Mathemtical Physics, 156(2):399–433, 1993.

[18] R. Montenegro and J.-B. Son. Edge isoperimetry and rapid mixing on matroids and geometric markov chains. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 704–711. ACM Press, 2001.

[19] O. Rothaus. Diffusion on compact riemannian manifolds and logarithmic sobolev inequalities. Journal of Functional Analysis, 42:102–109, 1981.

3However, if the size of the groundset is larger, say m = Ω(n^{3}), then Feder and Mihail’s modified random walk on balanced matroids (see [7], Theorem 5.2) with τ ≤ O(n^{4} log m) converges faster.