18.317 Combinatorics, Probability, and Computations on Groups November 2, 2001

Lecture 21

Lecturer: Igor Pak Scribe: B. Virag

1 Dirichlet forms and mixing time

Let G be a finite group, and let V be the vector space of real-valued functions from G. There is a natural inner product on this space

⟨ϕ, φ⟩ = ∑_{x∈G} φ(x)ψ(x) = |G|Eφ(X)ψ(X)

where X is chosen from g according to uniform measure. Let π be a probability distribution on G, and let P_{π} denote the transition kernel of the random walk {X_{n}} that moves from x to xy in every step, where y is distributed according to π. Just like any other transition kernel, P_{π} acts on the space of functions on G as follows

[P_{π}φ] (x) = ∑_{y∈G} φ(xy)π(y) = E[φ(X_{1}) | X_{0} = x].

Define the support of φ ∈ V in the usual way,

supp(φ) = {x ∈ G | φ(x) ≠ 0}.

We now define the Dirichlet form

E_{π}(φ, φ) = ⟨(I − P_{π})φ, φ⟩ = |G|E [(φ(X_{0}) − φ(X_{1})) φ(X_{0})]

where now X_{0} is chosen according to uniform distribution on G. Note that if Z_{0}, Z_{1} are real-valued random variables with the same distribution, then

E[(Z_{0} − Z_{1})Z_{0}] = \frac{1}{2}E(Z_{0} − Z_{1})^{2}.

Since the uniform distribution is stationary with respect to convolution, X_{0} and X_{1} have the same distribution, and we may apply this to φ(X_{0}), φ(X_{1}) to get the alternative formula for the Dirichlet form

E_{π}(φ, φ) = \frac{|G|}{2}E(φ(X_{0}) − φ(X_{1}))^{2} = \frac{1}{2} ∑_{x,y∈G}(φ(x) − φ(xy))^{2}π(y).

Now let Γ = Γ(G, S) be a Cayley graph of G with respect to a symmetric generator set S. Let γ be a function that assigns to each y ∈ G a path from the identity to y in Γ. We will assume that γ is geodesic, that is its values are shortest paths. Let μ_{s}(y) = μ_{s}(y, γ) denote the number of times a generator s appears in the decomposition

y = s_{1}s_{2} … s_{ℓ}  (1)

along the path γ(y). For C ⊆ G Let

N_{γ}(s, C) = max_{x,y∈C} μ_{s}(x^{−1}y).

We have a following version of a theorem by Diaconis and Saloff-Coste.

Theorem 1 (Comparison of Dirichlet forms) Let C ⊆ G, let \overline{C} = C ∪ ∂C, and let d = diam(\overline{C}). Consider π, π̃ symmetric probability distributions on G, and let S ⊆ supp(π). Then

E_{π}(φ, φ) ≥ \frac{1}{A}Eπ̃(φ, φ)

where

A = d max_{s∈S} \frac{N_{γ}(s, \overline{C})}{π(s)}.

Proof: Let y ∈ G, and write y in the form (1). We can write

φ(x) − φ(xy) = [φ(xs) − φ(xs_{1})] + … + [φ(xs_{1} … s_{ℓ−1} − φ(xy)].

It follows, for example, by the Cauchy-Schwarz inequality that

(φ(x) − φ(xy))^{2} ≤ ℓ^{∗} ∑_{i=1}^{ℓ}(φ(xs_{1} … s_{i−1}) − φ(xs_{1} … s_{i}))^{2}

where ℓ^{∗} is the number of nonzero terms in the sum, and is bounded above by d =diam(\overline{C}), since γ is geodesic. Summing this inequality over x ∈ G we get

∑_{x∈G}(φ(x) − φ(xy))^{2} ≤ d ∑_{z∈G,s∈S} N_{γ}(s, \overline{C})(φ(z) − φ(zs))^{2}.

Since this holds for all y ∈ G, we may average the left hand side with respect to y with weights π̃(y) to get

∑_{x,y∈G}(φ(x) − φ(xy))^{2}π̃(y) ≤ d ∑_{z∈G,s∈S} N_{γ}(s, \overline{C})(φ(z) − φ(zs))^{2}

Finally, the right hand side is clearly bounded by

A ∑_{z∈G,s∈S}(φ(z) − φ(zs))^{2}π(s)

and the statement of the theorem follows.

By the way, the symmetry assumption for S was not used.