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

Lecture 12

Lecturer: Igor Pak Scribe: Michael Korn

More About Mixing Times

Definition 1 For a probability distribution Q, we define the total variation distance, denoted ∥Q − U∥, by

∥Q − U∥ = max_{X⊂G} (Q(X) − \frac{|X|}{|G|}) = max_{X⊂G} (\frac{|X|}{|G|} − Q(X)) = \frac{1}{2} ∑_{g∈G} |Q(g) − \frac{1}{|G|}|

Definition 2

τ_{4} = min \{t : ∥Q^{t} − U∥ < \frac{1}{4}\}

Theorem 3

\frac{1}{96}τ_{2} < τ_{4} < 2τ_{2}

where τ_{2} = min{t : sep(t) < 1/2}, as we defined in the previous lecture.

Proof: First we shall prove that τ_{4} < 2τ_{2}. In the previous lecture, we showed that ∥Q^{t} − U∥ < sep(t). In particular, ∥Q^{2τ_{2}} − U∥ < sep(2τ_{2}). By sub-multiplicativity, we have that sep(2τ_{2}) < sep(τ_{2})^{2} < 1/4. It then follows that τ_{4} < 2τ_{2}.

Claim 4 Let X = \{g ∈ G : Q(g) < \frac{1}{4|G|}\}. Assume ∥Q − U∥ < 1/4. Then |X| < \frac{|G|}{3}.

Proof: The proof of this is one line. Here is that line:

\frac{1}{4} > ∥Q − U∥ ≥ \frac{|X|}{|G|} − Q(X) > \frac{|X|}{|G|} − \frac{1}{4} \frac{|X|}{|G|} = \frac{3}{4} \frac{|X|}{|G|} ⇒ |X| < \frac{|G|}{3}

It follows that |\overline{X}| > \frac{2}{3}|G|. Now let us apply this claim. We still assume ∥Q − U∥ < 1/4. Let P = Q ∗ Q. For all g ∈ G we have

P (g) = ∑_{ab=g} Q(a)Q(b) ≥ ∑ ; \begin{matrix}a ∈ \overline{X} \\ b ∈ \overline{X} \\ ab = g \end{matrix} Q(a)Q(b).

For at least \frac{2}{3} of the elements a in G we have a ∈ \overline{X}. For at least \frac{2}{3} of the elements a in G, we have a^{−1}g ∈ \overline{X}. Therefore, for at least \frac{1}{3} of the elements a in G, both statements hold. So the latter summation in the above equation is a sum over at least \frac{|G|}{3} terms. In these terms, Q(a) and Q(b) are both at least \frac{1}{4|G|}, since a and b are in \overline{X}. Hence,

P (g) > \frac{|G|}{3} \frac{1}{4|G|} \frac{1}{4|G|} = \frac{1}{48|G|}.

Now take Q to be Q^{τ_{4}}, which makes P = Q^{2τ_{4}}. (Notice that Q^{τ_{4}} satisfies the condition ∥Q^{τ_{4}} − U∥ < 1/4.) The above argument gives us that Q^{2τ_{4}}(g) > \frac{1}{48|G|} for all g. Hence sep(2τ_{4}) < \frac{47}{48}. So

sep(48(2τ_{4})) < (1 − \frac{1}{48})^{48} < \frac{1}{e} < \frac{1}{2}.

It follows that 96τ_{4} > τ_{2}. This proves the second half of the theorem.

Stopping Times

In this section, we introduce the notion of a stopping rule or stopping time for a random walk. The intuitive notion of a stopping rule is as follows. There is a machine which observes a random walk as it progresses. It is the job of the machine to say “STOP” at some time. The time at which the machine chooses to say “STOP” will depend on the sequence of states that it has observed. The machine cannot see future states of the random walk; it can only say “STOP” based upon what it has seen up to that point. This leads us to the following definition.

Definition 5 A function κ : {X_{t}} → ℕ is called a stopping time, provided it satisfies the following condition: If κ({X_{t}}) = k, and X′_{a} = X_{a} for all a ≤ k, then κ({X′_{t}}) = k.

So formally we treat κ as a function of an infinite walk, whose output is the time (a non-negative integer) at which the machine says “STOP”. The condition in the definition ensures that the function does not depend on states of the walk beyond the point at which the machine says “STOP”. Now we generalize this concept to allow for randomness in the machine’s behavior. The machine still sees the random walk as before, but now it also has access to a random real number in [0, 1] at each time step.

Definition 6 A function κ : {X_{t}} × [0, 1]^{∞} → ℕ is called a randomized stopping time, provided it satisfies the following condition: If κ({X_{t}}, {p_{t}}) = k, X′_{a} = X_{a} for all a ≤ k, and p′_{a} = p_{a} for all a ≤ k, then κ({X′_{t}}, {p′_{t}}) = k.

From here on, all stopping times will be assumed to be randomized unless otherwise stated.

Definition 7 We define the stopping state to be η = X_{κ}.

Definition 8 κ is uniform if Pr(η = g) = \frac{1}{|G|} for all g ∈ G. κ is strong uniform if Pr(η = g | κ = k) = \frac{1}{|G|} for all g ∈ G, and for all k for which Pr(κ = k) > 0.

Let us look at an example of a uniform stopping rule. Let G = ℤ_{m}, and let {±1, 0} be our generating set. Suppose κ picks a random element of G, and tells the random walk to stop as soon as it gets to that element. (In other words, the machine uses its first random number to determine what it wants the stopping state to be, and it lets the walk progress until it happens to land on that number.) Clearly this is a uniform stopping rule. It is not strong uniform, however. If the stopping time is small, then the stopping state is more likely to be near 0, rather than near m/2 (especially if the stopping time is less than m/2).

Theorem 9 (Aldous-Diaconis) Let κ be strong uniform. Then:

(1) sep(t) ≤ Pr(κ > t) for all t, and

(2) There exists a κ which yields equality in part (1) for all t.

This will be proved in the next lecture.

Corollary 10 τ_{3} = min E(κ), where the minimum ranges over all strong uniform κ.

Proof: Recall that τ_{3} = ∑_{t=0}^{∞} sep(t). Let κ be the optimal value mentioned in part (2) of the theorem. Then sep(t) = Pr(κ > t). So

τ_{3} = ∑_{t=0}^{∞} sep(t) = ∑_{t=0}^{∞} Pr(κ > t) = ∑_{t=0}^{∞} t · Pr(κ = t) = E(κ)

The fact that this is the minimum value follows by the same argument, except with ≤ signs.

Let us apply this corollary to a specific example.

Example Let G = ℤ_{m}, where m = 2^{r}. Let our generating set be {±1, 0}, with starting point 0. (So we have a random walk on a cycle of length 2^{r}, where on each step we move forward, backward, or not at all, with probability 1/3 of each. Now we need to define a stopping rule which is strong uniform. Here is the rule we will use.

Keep walking until we reach either \frac{m}{4} or \frac{3m}{4}.

Continue walking until we reach \frac{m}{8}, \frac{3m}{8}, \frac{5m}{8}, or \frac{7m}{8}.

Continue walking until we reach \frac{m}{16}, \frac{3m}{16}, \frac{5m}{16}, \frac{7m}{16}, \frac{9m}{16}, \frac{11m}{16}, \frac{13m}{16}, or \frac{15m}{16}.

⋮

Continue walking until we reach an odd-numbered point. Continue walking until we encounter a step of +1 or 0. STOP.

Claim 11 This stopping rule is strong uniform.

Proof: Our walk begins at 0. By symmetry, we reach \frac{m}{4} and \frac{3m}{4} each with probability 1/2, regardless of the time it takes us to get there. From that point, now we have to go a distance \frac{m}{8} either forward or backward, and again both happen with equal probability, regardless of the time it takes to get there. So now it is equally likely that we stand at any of those four points. When we’ve finished all but the last stage of the protocol, we have an equal chance of being at any odd-numbered point, regardless of the time it has taken us to get there.

In doing the last stage of this procedure, we take some number of -1 steps, followed by either a 0 or +1. Let j be the number of -1 steps we take in this stage. If j is even, then right before the final step of the walk, we are at a randomly chosen odd point. When we add either +1 or 0, this takes us to a point which is randomly chosen among all possible points. Similarly, if j is odd, we are at a randomly chosen even point right before the final step, but again the final addition of +1 or 0 gets us to a point chosen uniformly from among all points. So for any value of j, we end up in a uniform distribution. Thus this rule defines a strong uniform stopping time.

Lecture 12: 5 October 2001 4 What is the expected running time of this procedure? To do the first stage requires us to do a random walk until we’ve reached a distance of \frac{m}{4} from the start. This takes expected time O ((\frac{m}{4})^{2}). The next stage is similar; it takes expected time O ((\frac{m}{8})^{2}). So the whole procedure takes time O ((\frac{1}{16} + \frac{1}{64} + \frac{1}{256} + ⋯) m^{2}) = O (\frac{1}{12}m^{2}) = O (m^{2}). By the corollary, τ_{3} ≤ E(κ) = O(m^{2}). So for the mixing time for for the random walk in this example we have mix= O(m^{2}).