18.317 Combinatorics, Probability, and Computations on Groups 3 October 2001

Lecture 11

Lecturer: Igor Pak Scribe: N. Ackerman

1. Random Walks on Groups

Let G be a finite Group and let S be a set of generators of G. We say that S is symmetric if S = S^{−1}. In other words S is symmetric if ∀s ∈ S, s^{−1} ∈ S

Definition 1.1. We define Γ = Γ(G, S) as the \underline{Cayley graph} of G with respect to S. This is the graph which has a vertices for each g ∈ G and edges between each (g, h) such that g^{−1}h ∈ S.

Observe that if S is symmetric then the Cayley graph of G with respect to S, Γ(G, S) is unoriented. Also observe that if S contains the identity (id ∈ S) then the Cayley graph of G with respect to S, Γ(G, S) has loops.

Definition 1.2. On a walk of a Cayley graph we define x_{t} as the place you reach after t steps.

We define a \underline{random walk} as just a random walk on the Cayley graph starting at the identity. In other words at each step you choose (randomly and uniformly) which direction to go. (x_{t+1} = x_{t} · s, x_{0} = id, s ∈ S (uniform in S))

We similarly define a \underline{lazy random walk} as a random walk, except before each step you choose first whether to move or stay where you are. Then, if you have decided to move, you decide independently where to move (x_{t+1} = x_{t} · s^{e}, s ∈ S, e ∈ {0, 1}).

We define Q^{t}(g) = P r(x_{t} = g) as the probability that after t steps on the walk you will be at vertex g.

Proposition 1.3. If the Cayley graph is not bipartite then Q^{t}(g) → 1/|G|, as as t → ∞.

For example, if S contains the identity (id ∈ S) then this proposition is true for the lazy random walk.

\underline{Example:} If G = ℤ_{m} and S = \{±1\} then the Cayley graph Γ(G, S) is bipartite if and only if m is even.

\underline{Example:} If G = S_{m} and S = \{(i, j)|1 ≤ i < j ≤ n\} then the Cayley graph Γ(G, S) is bipartite.

Definition 1.4. If P and Q are probability distributions on G then we define the \underline{convolution} of P and Q as

P ∗ Q(g) = ∑_{h∈G} P (h)Q(h^{−1}g)

Observe that if P is the probability distribution

P (g) = \{ \begin{matrix}1/|S|, g ∈ S \\ 0 otherwise \end{matrix}

then Q^{t} = \underbrace{P ∗ P ∗ ⋯ ∗ P} t times

Definition 1.5. We then define the separation distance after t steps as

sep(t) = |G| · max_{g∈G}(1/|G| − Q^{t}(g))

Proposition 1.6.

a) sep(t+1) ≤ sep(t)

b) sep(t+l) ≤ sep(t) · sep(l)

c) sep(t)∼ cρ^{t} as t → ∞, 0 ≤ ρ ≤ 1,

where f(x) ∼ g(x) means that f(x) = g(x · (1 + o(1)))

Proof. a) Observe that sep(t) < ϵ is equivalent to saying that Q^{t} = (1 − ϵ)U + ϵN where U is the uniform distribution, and N is some other distribution. Therefore we know that because Q^{t+1} = Q^{t} ∗ P,

Q^{t+1} = ((1 − ϵ)U + ϵN) ∗ P = (1 − ϵ)U ∗ P + ϵN ∗ P

But we know U ∗P is still the uniform distribution, and min_{g∈G} N ∗P ≥ min_{g∈G} N by the construction of P. So min_{g∈G} Q^{t+1}(g) ≥ min_{g∈G} Q^{t}(g). And so finally sep(t+1) ≤ sep(t).

b) Let Q^{t} = (1 − ϵ)U + ϵN_{1} and Q^{l} = (1 − δ)U + δN_{2}. We know that this is equivalent to sep(t) < ϵ and sep(l) < δ

We then have

Q^{t+l} = ((1 − ϵ)U + ϵN_{1}) ∗ ((1 − δ)U + δN_{2})

and, after we condense terms it is easy to see that

Q^{t+l} = (1 − δϵ)U + δϵN_{1} ∗ N_{2}

And so we have that sep(t+l) < sep(t) · sep(l) (because sep(t+1)< δϵ and δ and ϵ are arbitrary).

c) Let A = (a_{gh})_{g,h∈G} be a matrix such that a_{gh} = P (hg^{−1}). We then let A^{t} = A ∗ ⋯ ∗ A. Then observe that

Q^{t} = [A^{t} · ( 1 0 0 ⋮ 0 )]_{g}

We then have

A^{t} · ( 1 0 0 ⋮ 0 ) = ( 1/|G| ; 1/|G| ; ⋮ ; 1/|G| ) + λ_{1}^{t}(v_{1}) + ⋯ + λ_{n}^{t}(v_{n})

Where v_{i} and λ_{i} are eigenvectors and eigenvalues. And so

Q^{t}(g) = λ_{1}^{t}(w_{1}) + ⋯ + λ_{n}^{t}(w_{n})

Now, if we let q_{t} = min_{g∈G} Q^{t}(g) then q_{t} = 1/|G| + w_{1}λ_{1}^{t} + ⋯ and

1/|G| − q_{t} = w_{1}λ_{1}^{t} + σC

Also observe that if we do this same thing for the lazy random walk we have λ′_{i} = 1/2(1 + λ_{i}).

□

Definition 1.7. We define the \underline{relaxation time} as: τ_{1} = 1/(1 − λ_{1}) We then define the \underline{mixing time} as minimum time for the separation time to be less than one half: τ_{2} = min{t : sep(t)≤ 1/2}. Finally, we define the \underline{optimal time} as: τ_{3} = ∑_{t=0}^{∞} sep(t)

Proposition 1.8. 1/2τ_{3} < τ_{2} < 2τ_{3}

Proof. Now, we can see from the definitions that τ_{3} ≥ \underbrace{1/2 + 1/2 + ⋯ + 1/2} ≥ 1/2τ_{2}

τ_{2}

Now we also know from the definitions that τ_{3} ≤ \underbrace{1 + 1 + ⋯ + 1} + \underbrace{1/2 + 1/2 + ⋯ + 1/2} + \underbrace{1/4 + 1/4 + ⋯ + 1/4} + ⋯

τ_{2} τ_{2} τ_{2}

= τ_{2}(1 + 1/2 + 1/4 + ⋯) = 2τ_{2} And this completes the proof. □

Proposition 1.9. τ_{2} < τ_{1} log(|G|)

Proof. First, note that

|1/|G| − Q^{t}(g)| < ∑ w_{i}λ_{i}^{t} < |G|λ_{1}^{t}

(Note that λ = ρ if s = s^{−1}).

Likewise, from the definitions we see that: |G| · |1/|G| − Q^{t}(g)| < |G|^{2}(1 − 1/τ_{1})^{t} ≤ 1/e < 1/2 · q_{t}, t = 2 log(|G|)

□

4 Lecture 11: 3 October 2001

\underline{Example} If G = ℤ_{m} and S = \{±1\} then

A = [ \begin{matrix}0 & 1/2 & 0 & 0 & 1/2 \\ 1/2 & 0 & ... & 0 & 0 \\ 0 & ... & ... & ... & 0 \\ 0 & 0 & ... & 0 & 1/2 \\ 1/2 & 0 & 0 & 1/2 & 0 \end{matrix} ]

One can show that λ_{j} = cos(2πj/m), so

λ_{1} = 1 − \frac{(2π)^{2}}{m^{2}} + o (\frac{1}{m^{4}} ) = 1 − \frac{c}{m^{2}} + o (\frac{1}{m^{4}} ) .

Now Proposition 1.9 implies that mix = o(m^{2} log m). In the future we will show that mix = θ(m^{2}).