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

Lecture 13

Lecturer: Igor Pak Scribe: Bo-Yin Yang

More on Strong Uniform Stopping Times

Theorem 1 We have a tight bound on group random walks with a strong uniform stopping time:

1. For any strong uniform stopping time κ, sep(t) ≤ Pr(κ > t), ∀t;

2. (For any given group random walk) There exists a strong uniform stopping time κ, such that sep(t) = Pr(κ > t), ∀t;

We first give an application of this theorem, let G = ℤ_{2}^{n}, define a lazy random walk with generating set

S = {(0, …, 1^{i−th}, …, 0), i ∈ {1..n}},

where the random walk rules are:

1. Pick j uniformly randomly from 1 … n.

2. Flip a coin.

3. If heads, then move in the direction; if tails nothing happens.

4. Repeat.

A stopping time for this random walk is κ: mark a coordinate j when it is “picked” regardless of the coin toss. Stop when all coordinate directions have been marked. It is trivial that this κ is strong uniform, hence the mixing time for this random walk is O(n log n). Proof: If R_{j}^{t}(g) = Pr(X_{t} = g|κ = j), then ∀t > j, R_{j}^{t} = R_{j}^{j} ∗ Q^{t−j} = U, since R_{j}^{j} = U by definition. So

Pr(X_{t} = g) = ∑_{j=1}^{t} \overbrace{Pr(X_{t} = g|κ = j)}^{(=1/|G|)} Pr(κ = j) + Pr(X_{t} = g|κ > t) Pr(κ > t)
≥ ∑_{j=1}^{t} Pr(κ = j) · \frac{1}{|G|} = Pr(κ ≥ t) · \frac{1}{|G|}.

Hence

sep(t) = |G| max_{g∈G}(\frac{1}{|G|} − Pr(X_{t} = g)) > Pr(κ > t).

This ends the first part of the proof. To prove the second part we will construct explicitly a stopping time.

Let q_{t} ≡ min_{g∈G} Q^{t}(g). The stopping rule is: if X_{t} = g, we stop with probability \frac{q_{t} − q_{t−1}}{Q^{t}(g) − q_{t−1}} , else keep

walking. We want, and it is easy to verify by mathematical induction that

Pr(X_{t} = g|κ ≥ t) = Q^{t}(g) − q_{t−1},

hence

Pr(κ = t) = ∑_{g∈G} Pr(X_{t} = g|κ ≥ t) \frac{q_{t} − q_{t−1}}{Q^{t}(g) − q_{t−1}} = |G|(q_{t} − q_{t−1}),

and

Pr(κ > t) = 1 − ∑_{j=1}^{t} Pr(κ = j) = 1 − |G| · q_{t} = |G| min_{g∈G} (\frac{1}{|G|} − Q^{t}(g)) = sep(t).

We will now give an example of a strong uniform stopping time in S_{n}, with the generating set being the exchanges R = {r_{i} = (1 i) | i = 1, …, n} (so r_{1} = id). The Stopping Rule to define κ is to think of the numbers as a deck of cards and:

1. First mark n.

2. When the number on the first card is an unmarked number, and r_{j} (with j is a marked index) appears or r_{1} appears, is first, then mark the first card (number in first position).

3. Wait until all cards are marked, then stop.

We wish to show that κ is strong uniform.

Claim 2 If S are the set of marked numbers, and I are the numbers appearing in the places whose locations correspond to the marked numbers in S, then at all times

Pr(π = ω||S| = |I| = k) = \frac{1}{k!}, ∀ω : I → S.

Proof: By mathematical induction. It’s clearly true at the beginning when k = 1. When |S| and |I| both increase by 1 (we mark another card), this card has an equal chance of being exchanged with any of the cards in marked locations or not being exchanged at all. So from the properties of S_{n} we know that this is true.

Corollary 3 Mixing time for this random walk is O(n log n).

Proof: We know from the preceeding claim that κ as defined is strong uniform. So we know that

τ_{3} ≤ E(κ) = ∑_{k=1}^{n−1} \frac{n}{k + 1} + ∑_{k=2}^{n−1} \frac{n}{n − k} = 2n log n + O(n).

Why the sum? Because it is now a double Coupon Collector’s Problem, in that we have to wait until we get a marked number, then until we get an unmarked number, then until we get a marked number again .... until everything is marked.

In our next lecture we will talk about Random Walks on other groups, in particular nilpotent groups of a certain kind.