Logarithmic Sobolev techniques for random walks on graphs

F. R. K. Chung University of Pennsylvania Philadelphia 19104

Abstract Recently, Diaconis and Sarloff-Coste used logarithmic Sobolev inequalities to improve convergence bounds for random walks on graphs. We will give a strengthened version by showing that the random walk on a graph G on n vertices reach the stationarity (under total variation distance) after about \frac{1}{4α} log log n steps where α denotes the log-Sobolev constant. Under the relative pointwise distance (which is a slight stronger notion), the random walk converges in about \frac{1}{2α} log log n steps.

1 Random walks on graphs

In a graph G, a walk is just a sequence of vertices (x_{0}, x_{1}, ⋯, x_{s}) with {x_{i−1}, x_{i}} ∈ E(G) for all 1 ≤ i ≤ s. A random walk is determined by the transition probabilities P (u, v) = P rob(x_{i+1} = v|x_{i} = u), which is independent of i. Clearly, for each vertex u,

∑_{v} P (u, v) = 1.

For any initial distribution f : V → ℝ with ∑_{v} f(v) = 1, the distribution after k steps is just fP^{k} (i.e., a matrix multiplication with f viewed as a row vector where P is the matrix of transition probabilities). The random walk is said to be ergodic if there is a unique stationary distribution π(v) satisfying

lim_{s→∞} fP^{s}(v) = π(v).

Necessary and sufficient conditions for the ergodicity of P are (i) irreducibility, i.e., for any u, v ∈ V, there exists some s such that P^{s}(u, v) > 0 (ii) aperiodicity, i.e., gcd {s : P^{s}(u, v) > 0} = 1. The problem of interest is to determine the number of steps s required for P^{s} to be close to its stationary distribution, given an arbitrary initial distribution.

We say a random walk is reversible if

π(u)P (u, v) = π(v)P (v, u).

An alternative description for a reversible random walk can be given by considering a weighted connected graph with edge weights satisfying

w(u, v) = w(v, u) = π(v)P (v, u)/c

where c can be any constant to be chosen for simplifying the values. (For example, we can take c to be the average of π(v)P (v, u) over all (v, u) with P (v, u) ≠ 0, so that the values for w(v, u) are either 0 or 1 for a simple graph.) The random walk on a weighted graph has as its transition probabilities

P (u, v) = \frac{w(u, v)}{d_{u}},

where d_{u} = ∑_{z} w(u, z) is the (weighted) degree of u. The two conditions for ergodicity are equivalent to the conditions that the graph be (i) connected and (ii) not bipartite. To simplify notation and eliminate possible confusion, for a random walk problem, we will just deal with the associated weighted graph. In particular, in the next section we will discuss the Laplacian and the heat kernel of a graph which are self-adjoint and very useful for understanding the behavior of the random walk.

2 The Laplacian and heat kernel of a weighted graph

A weighted undirected graph G (possibly with loops) has associated with it a weight function w : V × V → ℝ satisfying

w(u, v) = w(v, u)

and

w(u, v) ≥ 0.

We note that if {u, v} ∉ E(G) , then w(u, v) = 0. A simple (unweighted) graph is just the special case where all the weights are 0 or 1. The degree d_{v} of a vertex v is defined to be:

d_{v} = ∑_{u} w(u, v).

We define

L(u, v) = \{ \begin{matrix}d_{v} − w(v, v) & if u = v, \\ −w(u, v) & if u and v are adjacent, \\ 0 & otherwise. \end{matrix}

In particular, for a function f : V → ℝ, we have

Lf(x) = ∑_{\begin{matrix}y \\ x∼y \end{matrix}}(f(x) − f(y))w(x, y).

Let T denote the diagonal matrix with the (v, v)-th entry having value d_{v}. The Laplacian of G is defined to be

L = T^{−1/2}LT^{−1/2}.

In other words, we have

L(u, v) = \{ \begin{matrix}1 − \frac{w(v, v)}{d_{v}} & if u = v, \\ −\frac{w(u, v)}{\sqrt{d_{u}d_{v}}} & if u and v are adjacent, \\ 0 & otherwise. \end{matrix}

Since L is symmetric, its eigenvalues which are all real and non-negative are denoted by

0 = λ_{0} ≤ λ_{1} ≤ ⋯ ≤ λ_{n−1}

where n = |V |. We can use the variational characterization of the eigenvalues as follows:

λ_{G} := λ_{1} = inf_{g⊥T^{1/2}1} \frac{⟨g, Lg⟩}{⟨g, g⟩}  (1)
= inf_{\begin{matrix}f \\ ∑ f(x)d_{x}=0 \end{matrix}} \frac{∑_{x∈V} f(x)Lf(x)}{∑_{x∈V} f^{2}(x)d_{x}}

= inf_{\begin{matrix}f \\ ∑ f(x)d_{x}=0 \end{matrix}} \frac{∑_{x∼y}(f(x) − f(y))^{2}w(x, y)}{∑_{x∈V} f^{2}(x)d_{x}}.

For a connected graph G, the eigenvalues satisfy

0 < λ_{i} ≤ 2

for i ≥ 1. Various properties of the eigenvalues can be found in [4].

Suppose we write

L = ∑_{i=0}^{n−1} λ_{i}I_{i}

where I_{i} is the projection to the ith eigenfunction ϕ_{i} of the graph. For any t ≥ 0, the heat kernel H_{t} of G is defined to be the n × n matrix

H_{t} = ∑_{i} e^{−λ_{i}t}I_{i}
= e^{−tL}
= I − tL + \frac{ϵ^{2}}{2} L^{2} − …

In particular,

H_{0} = I.

For a function f : V → ℝ, we consider

F (x, t) = ∑_{y∈S∪δS} H_{t}(x, y)f(y)
= (H_{t}f)(x).

Then F satisfies the following properties (see [4]):

(i) F (x, 0) = f(x),

(ii) For a fixed x,

∑_{y} H_{t}(x, y)\sqrt{d_{y}} = \sqrt{d_{x}}

(iii) F satisfies the heat equation:

\frac{∂F}{∂t} = −LF

(iv)

LF (x, t) = ∑_{\begin{matrix}y \\ \{x,y\} \end{matrix}}(\frac{F (x, t)}{\sqrt{d_{x}}} − \frac{F (y, t)}{\sqrt{d_{y}}}) = 0

(v) ∑_{\{x,y\}∈E}(\frac{F (x, t)}{\sqrt{d_{x}}} − \frac{F (y, t)}{\sqrt{d_{y}}})^{2}w(x, y) = ∑_{x} F (x, t)LF (x, t)

3 The rate of convergence for random walks

In a random walk with an associated weighted connected graph G, the transition matrix P satisfies

1T P = 1T

and therefore the stationary distribution is exactly 1T/vol G, where vol G = ∑_{x} d_{x}. We want to show that when k is large enough, for any initial distribution f : V → ℝ, fP^{k} converges rapidly to its stationary distribution.

Here ∥ · ∥ denotes the L_{2} norm. We have

∥fP^{s} − 1T/volG∥ ≤ ∥fT^{−1/2}(I − L)^{s}T^{1/2} − I_{0}∥
≤ ∥T^{−1/2}(∑_{i≠0} I_{i}^{s})T^{1/2}∥ ∥f∥
≤ (1 − λ)^{s}∥f∥

where

λ = \{ \begin{matrix}λ_{1} & if 1 − λ_{1} ≥ λ_{n−1} − 1 \\ 2 − λ_{n−1} & otherwise. \end{matrix}  (2)

So, after s ≥ (1/λ) log(1/ϵ) steps, the L_{2} distance between fP^{s} and its stationary distribution is less than ϵ∥f∥.

We note that the convergence of the random walk P^{s} is related to the heat kernel h_{s} as follows:

∥P^{s} − T^{−1/2}I_{0}T^{1/2}∥ = ∥ ∑_{i≠0} I_{i}^{s}T^{1/2}∥  (3)
≤ ∥H_{s} − I_{0}∥
≤ e^{−sλ}

Although λ occurs in the above upper bound for the distance between the stationary distribution and the s-step distribution, in fact, only λ_{1} is crucial in the following sense. Note that λ is either λ_{1} or 2 − λ_{n−1}. Suppose the latter holds, i.e., λ_{n−1} − 1 ≥ 1 − λ_{1}. We can consider a modified random walk, called the lazy walk, on the graph G′ formed by adding a loop of weight d_{v} to each vertex v. The new graph has Laplacian eigenvalues λ̃_{k} = λ_{k}/2 ≤ 1, which follows from equation (1). Therefore,

1 − λ̃_{1} ≥ 1 − λ̃_{n−1} ≥ 0,

and the convergence bound in L_{2} distance in (4) for the modified random walk becomes

2/λ_{1} log(\frac{max_{x} \sqrt{d_{x}}}{ϵ min_{y} \sqrt{d_{y}}}).

In general, suppose a weighted graph with edge weights w(u, v) has eigenvalues λ_{i} with λ_{n−1}−1 ≥ 1 − λ_{1}. We can then modify the weights by choosing, for some constant c,

w′(u, v) = \{ \begin{matrix}w(v, v) + cd_{v} & if u = v \\ w(u, v) & otherwise. \end{matrix}  (4)

The resulting weighted graph has eigenvalues

λ′_{k} = \frac{λ_{k}}{1 + c} = \frac{2λ_{k}}{λ_{n−1} + λ_{k}}

where

c = \frac{λ_{1} + λ_{n−1}}{2} − 1 ≤ \frac{1}{2}.

Then we have

1 − λ′_{1} = λ′_{n−1} − 1 = \frac{λ_{n−1} − λ_{1}}{λ_{n−1} + λ_{1}} .

In particular we set

λ = λ′_{1} = \frac{2λ_{1}}{λ_{n−1} + λ_{1}} .

Therefore the modified random walk corresponding to the weight function w′ has an improved bound for the convergence rate in L_{2} distance:

\frac{1}{λ} log \frac{max_{x} \sqrt{d_{x}}}{ϵ min_{y} \sqrt{d_{y}}}

where λ = λ_{1} if λ_{n−1} + λ_{1} ≤ 2 and λ = 2λ_{1}/(λ_{n−1} + λ_{1}) otherwise. Note that λ ≥ 2λ_{1}/(2 + λ_{1}) ≥ 2λ_{1}/3.

We remark that for many applications in sampling, the convergence in L_{2} distance seems to be too weak since it does not capture the convergence at each vertex. A stronger notion of convergence is measured by the relative pointwise distance, which is defined as follows (also see [8]): After s steps, the relative pointwise distance (r.p.d.) of P to the stationary distribution π(x) is given by

Δ(s) = max_{x,y} \frac{|P^{s}(y, x) − π(x)|}{π(x)}.

Let f_{x} denote

f_{x}(y) = \{ \begin{matrix}1 & if y = x, \\ 0 & otherwise, \end{matrix}

We have

Δ(t) = max_{x,y} \frac{|f_{y} (P^{t}) f_{x} − π(x)|}{π(x)}
= max_{x,y} \frac{|f_{y} T^{−1/2} (I − L)^{t} T^{1/2} f_{x} − π(x)|}{π(x)}
= max_{x,y} |f_{y}T^{−1/2}(∑_{i≠0} I_{i}^{t})T^{1/2}f_{x}|volG
≤ max_{x,y} |f_{y}T^{−1/2}(H_{t} − I_{0})T^{1/2}f_{x}|volG
≤ e^{−tλ} max_{x,y} ∥T^{−1/2}f_{x}∥ ∥T^{−1/2}f_{y}∥volG
≤ e^{−tλ} \frac{vol G}{min_{x} d_{x}} .  (5)

So if we choose t such that

t ≥ \frac{1}{λ} log \frac{vol G}{ϵ min_{x} d_{x}} ,

then, after t steps, we have Δ(t) ≤ ϵ where λ is as defined in (2) or for the lazy walk as defined in (4), λ can be taken to be

λ = \{ \begin{matrix}λ_{1} & if 1 − λ_{1} ≥ λ_{n−1} − 1 \\ \frac{2λ_{1}}{λ_{n−1} + λ_{1}} & otherwise \end{matrix}  (6)

Here we note that the factor of \frac{vol G}{min_{x} d_{x}} in (5 ) can be further reduced by the Logarithmic Sobolev techniques which we will discuss in the next section.

4 The log-Sobolev constant

Let G denote a weighted graph on n vertices. For a function f : V (G) → ℝ. We may view f as a column vector, 1 × n matrix or a row vector. The stationary distribution π(x) = d_{x}/vol G will be viewed as a column or row vector. Let π denote the diagonal matrix with value π(x) as the (x, x)-entry.

The log-Sobolev constant α of a weighted graph G is the least constant satisfying the following log-Sobolev inequality for any nontrivial function f : V → ℝ:

∑_{\{x,y\}∈E}(f(x) − f(y))^{2}w_{x,y} ≤ α ∑_{x∈V} f^{2}(x)d_{x} log \frac{f^{2}(x)vol G}{∑_{z∈V} f^{2}(z)d_{z}}

In other words, α can be expressed as follows:

α_{G} = α = inf_{f≠0} \frac{∑_{\{x,y\}∈E}(f(x) − f(y))^{2}w_{x,y}}{∑_{x∈V} f^{2}(x)d_{x} log \frac{f^{2}(x)vol G}{∑_{z∈V} f^{2}(z)d_{z}}}  (7)

where f ranges over all nontrivial functions f : V → ℝ.

Logarithmic Sobolev inequalities first arose in the analysis of elliptic differential operators in infinite dimensions. Many developments and applications can be found in several survey papers [1, 6, 7, 9]. Diaconis and Salaff-Coste [5] introduced a discrete version of logarithmic sobolev inequality to prove that for a regula graph on n vertices

Δ_{T V} (t) ≤ e^{1−c} if t ≥ \frac{1}{2α} log log n + \frac{c}{λ}.

We will give a simple proof of the above result by deriving the following slightly stronger statements.

Theorem 1 In a weighted graph G with log-Sobolev constant α, we have Δ(t) ≤ e^{2−c} if

t ≥ \frac{1}{2α} log log \frac{vol G}{min_{x} d_{x}} + \frac{c}{λ}.

Theorem 2 In a weighted graph G with log-Sobolev constant α, we have Δ_{T V} (t) ≤ e^{1−c}/2 if

t ≥ \frac{1}{4α} log log \frac{vol G}{min_{x} d_{x}} + \frac{c}{λ}.

The proofs for the above theorem will be given in the next section.

5 Proofs of the main theorems

For a function f : V (G) → ℝ, we define the (π; p)-norm of f, denoted by _{π}∥f∥_{p}, to be

π∥f∥_{p} = ( ∑_{x∈V (G)} f^{p}(x)π(x))^{1/p} .

In particular,

π∥f∥_{2} = (∑_{x} f^{2}(x)π(x))^{1/2} = ∥π^{1/2}f∥_{2}.

The main proof for Theorems 1 and 2 consists of two parts. In the first part (Theorem 3), we will see that the inequality (8) relating the p-norm to the 2-norm, for certain p, implies the improved convergence bound for random walks. The second part (Theorem 5) states that the inequality (8) can be derived from the log-Sobolev inequality.

Theorem 3 Suppose that in a weighted graph G, its heat kernel H_{s} satisfies

π∥f π^{1/2} H_{s} π^{−1/2}∥_{p} ≤ _{π}∥f∥_{2}  (8)

for all f : V (G) → ℝ, and p = e^{βs} for some positive value β. Then the random walk on G satisfies

Δ(t) ≤ e^{2−c}

if

t ≥ \frac{2}{β} log log \frac{volG}{min_{x} d_{x}} + \frac{c}{λ}.

Proof: We define q satisfying

\frac{1}{p} + \frac{1}{q} = 1.

For a vertex x of G, let ψ_{x} denote the characteristic function satisfying ψ_{x}(y) = 1 if x = y, and 0 otherwise. For a function f : V → ℝ, we consider

|ψ_{x}π^{−1/2}H_{s}π^{1/2}f|
= | (ψ_{x}π^{−1+1/q}) (π^{1/p−1/2}H_{s}π^{1/2}f)|
≤ (∑_{y}(ψ_{x} π^{−1}(y))^{q}π(y))^{1/q} (∑_{y}(fπ^{1/2}H_{s} π^{−1/2}(y))^{p}π(y))^{1/p}
= _{π}∥ψ_{x}π^{−1}∥_{q} _{π}∥fπ^{1/2}H_{s}π^{−1/2}∥_{p}  (9)

by using Hölder’s inequality.

We consider

π∥ψ_{x}π^{−1}∥_{q} = (∑_{y}(ψ_{x} π^{−1}(y))^{q}π(y))^{1/q}
= (π(x)^{1−q})^{1/q}
= π(x)^{−1/p}
≤ (\frac{volG}{min_{x} d_{x}})^{1/p}.

Using the hypothesis that p = e^{βs} and the choice of s satisfying

s = \frac{1}{β} log log \frac{volG}{min_{x} d_{x}} ,

we have

(\frac{volG}{min_{x} d_{x}})^{1/p} = e^{e^{log log \frac{volG}{minx dx} −βs}} = e

From (8) and (9), we have, for any f,

|ψ_{x}π^{−1/2}H_{s}π^{1/2}f| ≤ e _{π}∥fπ^{1/2}H_{s}π^{−1/2}∥_{p}
≤ e _{π}∥f∥_{2}.

In particular, for the heat kernel and the projection I_{0} into the 0-th eigenfunction, we have

|ψ_{x}π^{−1/2}(H_{s+r} − I_{0})π^{1/2}f| ≤ |ψ_{x}π^{−1/2}H_{s}(H_{r} − I_{0})π^{1/2}f|
≤ e _{π}∥π^{−1/2}(H_{r} − I_{0})π^{1/2}f∥_{2}
≤ e∥(H_{r} − I_{0})π^{1/2}f∥_{2}
≤ e∥(H_{r} − I_{0})∥_{2} ∥π^{1/2}f∥_{2}
≤ e^{1−λr} _{π}∥f∥_{2}.

This is equivalent to

|ψ_{x}π^{−1/2}(H_{s+r} − I_{0})g| ≤ e^{1−λr}∥g∥_{2}

for all g. This implies

∥ψ_{x}π^{−1/2}(H_{s+r} − I_{0})∥_{2} ≤ e^{1−λr}.  (10)

Therefore, the random walk on G converges to the stationary distribution under relative pairwise distance as follows (see (5)):

Δ(2s + 2r) ≤ max_{x,y} |ψ_{x}π^{−1/2}(H_{2s+2r} − I_{0})π^{−1/2}ψ_{y}|
≤ max_{x,y} ∥ψ_{x}π^{−1/2}(H_{s+r} − I_{0})∥_{2} · ∥ψ_{y}π^{−1/2}(H_{s+r} − I_{0})∥_{2}
≤ e^{2−2λr}

by using (10) and the Cauchy schwarz inequality. Now, we take r = \frac{c}{2λ} , t = 2s + 2r, and the proof is complete. □

We can also obtain a similar statement for the convergence bound under the total variation distance.

Theorem 4 Suppose that in a weighted graph G, its heat kernel H_{s} satisfies

π∥f π^{1/2} H_{s} π^{−1/2}∥_{p} ≤ _{π}∥f∥_{2}

for all f : V (G) → ℝ, and p = e^{βs} for some positive value β. Then the random walk on G satisfies

Δ_{T V} (t) ≤ \frac{1}{2}e^{1−c}

if

t ≥ \frac{1}{β} log log \frac{volG}{min_{x} d_{x}} + \frac{c}{λ}.

Proof: We follow the notation in Theorem 3.

Δ_{T V} = \frac{1}{2} max_{x} ∑_{y} |ψ_{x}P^{s+r}(y) − π(y)|
≤ \frac{1}{2} max_{x} ∑_{y} |ψ_{x}π^{−1/2}(H_{s+r} − I_{0})π^{1/2}(y)|
≤ \frac{1}{2} max_{x} ∑_{y} e^{1−λr}π(y)
≤ \frac{1}{2}e^{1−λr}

by using (10). □

Now we proceed to show that the log-Sobolev constant can be used to determine β in the above theorems. This proof is very similar to the continuous case (see [5]).

Theorem 5 In a graph G with log-Sobolev constant α, its heat kernel H_{t} satisfies

π∥f π^{1/2} H_{t} π^{−1/2}∥_{p} ≤ _{π}∥f∥_{2}

for any t > 0, p = e^{4αt} + 1, and for any f : V (G) → ℝ. Proof: From the definition of α, we have

∑_{x∼y}(f(x) − f(y))^{2}w(x, y) ≥ α ∑_{x} f^{2}(x)d_{x} log \frac{f^{2}(x)^{2}}{∑_{z} f^{2}(z)π(z)}

for any nontrivial function f. In particular, we can replace f by f^{p/2} and we have

∑_{x∼y}(f^{p/2}(x) − f^{p/2}(y))^{2}w(x, y) ≥ α ∑_{x} f^{p}(x)d_{x} log \frac{f(x)^{p}}{∑_{z} f^{p}(z)π(z)}.  (11)

Now we need the following inequality which is not hard to prove:

4(p − 1)(a^{p/2} − b^{p/2})^{2} ≤ p^{2}(a − b)(a^{p−1} − b^{p−1}).  (12)

for all a, b ≥ 0 and p ≥ 1. From (11) and (12), we have

α ∑_{x} f^{p}(x)π(x) log \frac{f(x)^{p}}{∑_{z} f^{p}(z)π(z)}

≤ ∑_{x∼y}(f^{p/2}(x) − f^{p/2}(y))^{2}w(x, y)
≤ \frac{p^{2}}{4(p − 1)} ∑_{x∼y}(f^{p−1}(x) − f^{p−1}(y))(f(x) − f(y))w_{x,y}  (13)

We now replace f by g = fπ^{1/2}H_{t}π^{−1/2} in the above inequality and define p as a function of t:

p = p(t) = 1 + e^{4αt}.

Note that p′ = p′(t) = 4α(p − 1). From (13), we have

\frac{p′}{p^{2}} ∑_{x} g^{p}(x)π(x) log \frac{|g(x)|^{p}}{∑_{z} g^{p}(z)π(z)} − ∑_{x∼y}(g^{p−1}(x) − g^{p−1}(y))(g(x) − g(y))w_{x,y} ≤ 0  (14)

Now we define

F (t) = _{π}∥g∥_{p}.

Clearly, F (0) = _{π}∥f∥_{2}. If we can show that the derivative F′(t) ≤ 0, then we have _{π}∥g∥_{p} = F (t) ≤ F (0) = _{π}∥f∥_{2} as desired. It remains to show F′(t) ≤ 0. Since

F (t) = (∑_{x}(fπ^{1/2}H_{t}π^{−1/2}(x))^{p}π(x))^{1/p} = (G(t))^{1/p},

we have

F′(t) = (−\frac{p′}{p^{2}} log G(t) + \frac{G′(t)}{pG(t)}) F (t).  (15)

We note that

G′(t) = p ∑_{x} g^{p−1}π(x)(fπ^{1/2} \frac{d}{dt}H_{t}π^{−1/2}(x)) + p′ ∑_{x} g^{p}(x)π(x) log g(x)
= I + II

We consider the above sum of I as a product of matrices (where A^{∗} denotes the transpose of A):

I = p g^{p−1}π^{1/2} \frac{d}{dt}H_{t}π^{1/2}f^{∗}
= −p g^{p−1}π^{1/2}LH_{t}π^{1/2}f^{∗}
= −p g^{p−1}π^{1/2}Lπ^{1/2}g^{∗}
= −\frac{p}{vol G} ∑_{x∼y}(g^{p−1}(x) − g^{p−1}(y))(g(x) − g(y))w_{x,y}

by using the heat equation in the weighted version of Lemma 10.3. Substituting into (15), we obtain

F′(t)
= \frac{p′}{p^{2}} (∑_{x} g^{p}(x)π(x) log g^{p}(x) − log G(t)) − \frac{1}{vol G} ∑_{x∼y}(g^{p−1}(x) − g^{p−1}(y))(g(x) − g(y))
= \frac{1}{vol G} (\frac{p′}{p^{2}} ∑_{x} ∑_{x} g^{p}(x)d_{x} log \frac{g^{p}(x)}{log G(t)} − ∑_{x∼y}(g^{p−1}(x) − g^{p−1}(y))(g(x) − g(y))w_{x,y})
≤ 0

by using (14). Theorem 5 is proved. □

Together with Theorem 3 and 4, we have completed the proofs for the main results in Theorem 1 and 2.

References

[1] D. Bakry, L’hypercontractivité et son utilisation en théorie des semigroups, In Ecole d’ été de Saint Flour 1992, Springer LNM 1581.

[2] W. Beckner, Inequalities in fourier analysis, Annals of Mathematics 102 (1975) 159-182.

[3] F. R. K. Chung and S. -T. Yau, Eigenvalues of graphs and Sobolev inequalities, Combinatorics, Probability and Computing, 4 (1995) 11-26.

[4] F. R. K. Chung, Spectral Graph Theory, CBMS Lecture Notes, 1996 , AMS Publication.

[5] P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, preprint.

[6] L. Gross, Logarithmic Sobolev inequalitities, Amer. J. Math. 97, (1976) 1061-1083.

[7] L. Gross, Logarithmic Sobolev inequalitities and contractivity properties of semi-groups, in Lecture Notes in Math. (1993) Springer LNM 1563.

[8] A.J. Sinclair, Algorithms for Random Generation and Counting, Birkhauser, 1993.

[9] D. Stroock, Logarithmic Sobolev inequalitities for Gibbs states, in Lecture Notes in Math. (1993) Springer LNM 1563.