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

Lecture 22

Lecturer: Igor Pak Scribe: Nate Ackerman

Theorem 1 (This is a special case of the theorem from last class.) Suppose Γ = Γ(G, S), υ = set of paths in Γ, and γ = {γ_{x}: path from id to x}. Also suppose that π, π̃ are symmetric, s ⊆ support(π), diam υ = max_{x} |γ_{x}| = d and μ_{s}(x) = number of generators s in γ_{x} = s_{i_{1}}s_{i_{2}} · · ·.

Then E_{π}(φ, φ) ≥ (1/|A|) · Eπ̃(φ, φ) where A = d · max_{s∈S}(max_{x∈G} μ_{s}(x))/π(s).

We shall prove the following important corollary from the Theorem.

Lemma 2 Suppose Eπ̃(φ, φ) ≤ A · E_{π}(φ, φ) ∀φ. Then

1 − λ̃_{i} ≤ A(1 − λ_{i}),

where λ_{i} are the eigenvalues of M_{π}.

For every probability distribution π, consider the matrix

M_{π} = (a_{xy})_{|G|×|G|}, a_{xy} = π(x^{−1}y)

Here it is important π is symmetric so all eigenvectors are real: 1 = λ_{0} ≥ λ_{1} ≥ ⋯ ≥ −1.

Recall that E_{π}(φ, φ) = ⟨(I − P_{π})φ, φ⟩, where P_{π} is exactly convolution with π. Then M_{π} is then exactly the matrix of that operation. Consider the scalar product of a function and an operator on that function.

Lets call this operation Q = I − P_{π}.

Lemma 3 For every symmetric operator Q,

min_{φ} \frac{⟨Qφ, φ⟩}{⟨φ, φ⟩}

is equal to the smallest eigenvalue of Q.

Proof: To see this let us look at it the other way. We see easily from linear algebra that max_{φ}⟨Qφ, φ⟩/⟨φ, φ⟩ is just the maximal eigenvalue of Q. Similarly

min_{φ} \frac{⟨Qφ, φ⟩}{⟨φ, φ⟩} = min_{φ: Σφ=0} \frac{⟨Qφ, φ⟩}{⟨φ, φ⟩} = λ_{1}

We just need one more well known result from linear algebra to complete the proof of Lemma 2.

Theorem 4 (min-max principle) Let Q be a symmetric linear operator on V with eigenvalues q_{0} ≤ q_{1} ≤ ⋯ ≤ q_{n}. Let m(W) = min{⟨Qf, f⟩/⟨f, f⟩ : f ∈ W ⊆ V }. Then

q_{i} = max{m(W) : dim(W) = i}

This follows when you consider vector spaces generated by first i eigenvectors.

This is all we need to complete the proof of Lemma 2. Indeed, Theorem 4 implies: 1 − λ̃_{i} ≤ A(1 − λ_{i}). Therefore λ_{1} ≤ 1 − (1 − λ̃_{1})/A

Let π̃ = U(G) = uniform distribution on the group, and let π = U(S) be a uniform distribution on the generating set. Assume our generating set is the whole group (S = G). Then the transition matrix Mπ̃ is given by

\frac{1}{|G|} ( \begin{matrix}1 & 1 & 1 & ⋯ \\ 1 & 1 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This matrix has an eigenvalue of 1. But, because it also has rank 1, we know that all remaining eigenvalues are 0. Thus, λ_{0} = 1, λ_{i} = 0, and therefore λ̃_{1} = 0. Finally, we conclude λ_{1} ≤ 1 − 1/A Recall that

A = d · max_{s∈S} max_{g∈G} \frac{μ_{s}(x)}{π(s)},

where d = diameter(γ), and π(s) = 1/|S| since π is the uniform distribution. Therefore,

A = d · |S| · max_{s∈S} N_{γ}(S, G),

and we obtain:

Theorem 5 Let G be a finite group, let S = S^{−1} be a symmetric generating set, and let Γ = Γ(G, S) be a Cayley graph with diameter d. Then

λ_{1} ≤ 1 − \frac{1}{A} ≤ 1 − \frac{1}{d · |S| · N_{γ}} ≤ 1 − \frac{1}{d^{2} |S|},

where N_{γ} = max_{s∈S} N_{γ}(S, G).

Corollary 6

a) The relaxation time τ_{1} = 1/(1 − λ_{1}) ≤ d · |S| · N_{γ}.

b) The mixing time of the lazy random walk W on Γ(G, S) satisfies:

τ_{3} ≤ d · |S| · N_{γ} log |G| ≤ d^{2}|S| log |G|

Part b) in the corollary follows from part a) and τ_{3}^{∗} ≤ τ_{1} log |G|, where * refers to the lazy random walk. Now, let us consider several special cases

\underline{Example 1} Let G = ℤ_{n}, S = \{±1\}. The corollary gives mix = O(n^{2} log(n)), which is slightly weaker from the tight bound mix = O(n^{2}).

\underline{Example 2} Let G = ℤ_{2}^{n}, S = \{(a_{1}, ⋯, a_{n}) : a_{i} = 1 and the rest are 0, for 1 ≤ i ≤ n\}. To calculate the mixing time we need the diameter (d) and |S|. Since d=n, and |S| = n, we obtain

τ_{3}^{∗} ≤ d^{2}|S| log |G| = O(n^{4}).

On the other hand, a stronger inequality τ_{3}^{∗} ≤ d|S|N_{γ} log |G| gives us a better (but still not great) upper bound. Indeed, since N_{γ} = 1, we get τ_{3}^{∗} ≤ O(n^{3}). This should be compared with τ_{3}^{∗} = O(n log n) we obtained by a stopping times argument.

\underline{Example 3} Let G = S_{n}, R = \{(12)(13) ⋯ (1n)\} Consider d = diam Γ(S_{n}, R)). The largest distance to identity has a permutation g = (23)(45) ⋯ (2m, 2m + 1), n = 2m + 1. This implies that

diam Γ(S_{n}, R) =∼ 3/2n + O(1).

We also have |S| = n − 1 = O(n), and log |G| = O(n log(n)), so, mix ≤ d^{2}|R| log |G| ≤ O(n^{4} log(n)).

On the other hand, we know that N_{γ} is small. In fact, an easy check shows that N_{γ} is at most 2, and so

mix ≤ d |R| N_{γ} log |G| = O(n^{3} log(n))

Recall that by a stopping time argument we obtained a tight upper bound of O(n log n) in this case.

\underline{Example 4} Let G = S_{n}, R = \{(ij) : 1 ≤ i < j ≤ n\} We can do a similar stopping argument to show that in fact mix= Cn log(n). However, the upper bound given by corollary is not nearly that good. We have: |R| = O(n^{2}), d = O(n), and N_{γ} = 1. Therefore, have mix≤ d N_{γ} |R| log |G| = O(n^{4} log(n)).

This is another example of weakness of the bound given by Corollary 6. The larger the generating set, the bigger the bound on the mixing time. This is unfortunate, as the larger the generating set, the smaller the mixing time tends to be.

Multicomodity flows Imagine we have an industrial structure that looks like a Cayley graph, and each place has to trade commodities with the other places. In particular between any two plans 1 commodity must flow. However, the 1 unit flow along different paths. All that matters is that the sum total of the flow is 1 unit (so the flows look like a probability distribution on the paths between any two sites.)

Let γ = {γ_{x} = flow from id to x in G}. So γ_{x} can consist of several different paths so long as the flows add to 1.

N_{γ} = max_{s∈S} max_{x∈S} μ_{s}(γ_{x}) (= expected number of times s occurs in a path from id to x)

\underline{Claim} Theorem 1 and Corollary 6 remain correct under this generalization.

Corollary 7 If Γ = Γ(G, S) is vertex transitive. (e.g. if H ⊆Aut(G) then H acts transitively on S) Then the relaxation time τ_{1} = O(d^{2}), and the mixing time τ_{3} = O(d^{2} log |G|)

Indeed, consider a uniform distribution on all paths giving a shortest decomposition of an element. Then N_{γ} = d/|S|, and we have d|S|N_{γ} = d^{2}. In a special case of the Example 4 the corollary gives O(n^{3} log n) bound now.