Random walks on generating sets for finite groups

F. R. K. Chung ^{1} University of Pennsylvania Philadelphia, PA 19104

R. L. Graham AT&T Research Murray Hill, NJ 07974

Submitted: August 31, 1996; Accepted: November 12, 1996

Dedicated to Herb Wilf on the occasion of his sixty-fifth birthday

Abstract We analyze a certain random walk on the cartesian product G^{n} of a finite group G which is often used for generating random elements from G. In particular, we show that the mixing time of the walk is at most c_{r}n^{2} log n where the constant c_{r} depends only on the order r of G.

1. Introduction

One method often used in computational group theory for generating random elements from a given (non-trivial) finite group G proceeds as follows (e.g., see [2]). A fixed integer n ≥ 2 is initially specified. Denote by G^{n} the set {(x_{1}, …, x_{n}) : x_{i} ∈ G, 1 ≤ i ≤ n}. If x̄ = (x_{1}, …, x_{n}) ∈ G^{n}, we denote by ⟨x̄⟩ the subgroup of G generated by {x_{i} : 1 ≤ i ≤ n}. Let G^{∗} ⊆ G^{n} denote the set of all x̄ ∈ G^{n} such that ⟨x̄⟩ = G. We execute a random walk on G^{∗} by taking the following general step. Suppose we are at a point p̄ = (p_{1}, …, p_{n}) ∈ G^{∗}. Choose a random pair of indices (i, j) with i ≠ j. (Thus, each such pair is chosen with probability \frac{1}{n(n−1)}.) We then move to one of p̄′ = (p′_{1}, …, p′_{n}) where

p′_{k} = \{ \begin{matrix}p_{i}p_{j} or p_{i}p_{j}^{−1} & if k = i, each with probability 1/2 \\ p_{k} & if k ≠ i . \end{matrix}

This rule determines the corresponding transition matrix Q of the walk. We note that with this rule, we always have p̄′ ∈ G^{∗}. It is also easy to check that for n ≥ n_{0}(G), this walk is irreducible and aperiodic (see Section 5 for more quantitative remarks), and has a stationary distribution π which is uniform (since G^{∗} is a multigraph in which every vertex has degree 2n(n − 1)). the electronic journal of combinatorics 4, no. 2 (1997), #R7 2

1Research supported in part by NSF Grant No. DMS 95-04834

Starting from some fixed initial distribution f_{0} on G^{∗}, we apply this procedure some number of times, say t, to reach a distribution f_{0}Q^{t} on G^{∗} which we hope will be close to “random” when t is large. A crucial question which must be faced in this situation is just how rapidly this process mixes, i.e., how large must t be so that f_{0}Q^{t} is close to uniform. In this note, we apply several rather general comparison theorems to give reasonably good bounds on the mixing time for Q. In particular, we show (see Theorem 1) that when t ≥ c(G)n^{2} log n, where c(G) is a constant depending only on G, then Q^{t} is already quite close to uniform (where we usually will suppress f_{0}).

This problem belongs to a general class of random walk problems suggested recently by David Aldous [1]. In fact, he considers a more general walk in which only certain pairs of indices (i, j) are allowed in forming p′_{k} = p_{i}p_{j} or p_{i}p_{j}^{−1}. These pairs can be described by a graph H on the vertex set {1, 2, ·, n}. The case studied in this note corresponds to taking H to be a complete graph.

We first learned of this problem from a preprint of Diaconis and Saloff-Coste [6], part of which has subsequently appeared [7]. In it, they wrote “ ⋯ for G = ℤ_{p} with p = 2, 3, 4, 5, 7, 8, 9 we know that n^{2} log n steps are enough whereas for G = ℤ_{6} or ℤ_{10} we only know that n^{4} log n are enough. Even in the case of ℤ_{6} it does not seem easy to improve this.” Our main contribution in this note is to show that by direct combinatorial constructions, a mixing time of c(G)n^{2} log n can be obtained for all groups G where c(G) is a constant depending just on G. Subsequently, they have now [8] also obtained bounds of the form c(G)n^{2} log n for all groups G by including a more sophisticated path construction argument than they had previously used in [6].

2. Background

A weighted graph Γ = (V, E) consists of a vertex set V, and a weight function w : V ×V → ℝ satisfying w(u, v) = w(v, u) ≥ 0 for all u, v ∈ V. The edge set E of Γ is defined to be the set of all pairs uv with w(u, v) > 0. A simple (unweighted) graph is just the special case in which all weights are 0 or 1. The degree d_{v} of a vertex v is defined by

d_{v} := ∑_{u} w(u, v) .

Further, we define the |V | × |V | matrix L by

L(u, v) = \{ \begin{matrix}d_{v} − w(v, v) & if u = v, \\ −w(u, v) & if uv ∈ E, u ≠ v, \\ 0 & otherwise . \end{matrix}

In particular, for a function f : V → ℝ, we have

Lf(x) = ∑_{{y \atop xy∈E}} (f(x) − f(y))w(x, y) .

Let T denote the diagonal matrix with the (v, v) entry having the value d_{v}. The Laplacian L_{Γ} of Γ is defined to be

L = L_{Γ} = T^{−1/2}LT^{−1/2} .

In other words,

L(u, v) = \{ \begin{matrix}1 − \frac{w(v,v)}{d_{v}} & if u = v, \\ −\frac{w(u,v)}{\sqrt{d_{u}d_{v}}} & if uv ∈ E, u ≠ v, \\ 0 & otherwise . \end{matrix}

Since L is symmetric and non-negative definite, its eigenvalues are real and non-negative. We denote them by

0 = λ_{0} ≤ λ_{1} ≤ ⋯ ≤ λ_{n−1}

where n = |V |.

It follows from standard variational characterizations of eigenvalues that

λ_{1} = inf_{f} sup_{c} \frac{∑_{u,v∈E}(f(u) − f(v))^{2}w(u, v)}{∑_{x} d_{x}(f(x) − c)^{2}} . (1)

For a connected graph Γ, the eigenvalues satisfy

0 < λ_{i} ≤ 2

for i ≥ 1. Various properties of the eigenvalues can be found in [3].

Now, the usual random walk on an unweighted graph has transition probability 1/d_{v} of moving from a vertex v to any one of its neighbors. The transition matrix P then satisfies

P (v, u) = \{ \begin{matrix}1/d_{v} & if uv ∈ E, \\ 0 & otherwise . \end{matrix}

That is,

fP (u) = ∑_{{v \atop uv∈E}} \frac{1}{d_{v}} f(v)

for any f : V → ℝ. It is easy to check that

P = T^{−1/2}(I − R)T^{1/2} = T^{−1}A

where A is the adjacency matrix of the graph.

In a random walk on a connected weighted graph Γ, the transition matrix P satisfies

1T P = 1T .

Thus, the stationary distribution is just 1T/vol(Γ), where vol(Γ) = ∑_{x} d_{x} and 1 is the all ones vector. Our problem is to estimate how rapidly fP^{k} converges to its stationary distribution, as k → ∞, starting from some initial distribution f : V → ℝ. First, consider convergence in the L^{2} (or Euclidean) norm. Suppose we write

fT^{−1/2} = ∑_{i} a_{i}ϕ_{i}

where ϕ_{i} denotes the eigenfunction associated with λ_{i} and ∥ϕ_{i}∥ = 1. Since ϕ_{0} = 1·T^{1/2}/\sqrt{vol(Γ)} then

a_{0} = \frac{⟨fT^{−1/2}, 1 T^{1/2}⟩}{∥1 T^{1/2}∥} = \frac{1}{\sqrt{vol(Γ)}}

since ⟨f, 1⟩ = 1. We then have

∥fP^{s} − 1T/vol(Γ)∥ = ∥fT^{−1/2}(I − L)^{s}T^{1/2} − a_{0}ϕ_{0}T^{1/2}∥
= ∥∑_{i≠0}(1 − λ_{i})^{s}a_{i}ϕ_{i}T^{1/2}∥
≤ (1 − λ)^{s}∥f∥
≤ e^{−sλ}∥f∥

where

λ = \{ \begin{matrix}λ_{1} & if 1 − λ_{1} ≥ λ_{n−1} − 1, \\ 2 − λ_{n−1} & otherwise . \end{matrix}

So, after s ≥ (1/λ) log(1/ϵ) steps, the L_{2} distance between fP^{s} and its stationary distribution is at most ϵ∥f∥.

Although λ occurs in the above bound, in fact only λ_{1} is crucial, in the following sense. If it happens that 1 − λ_{1} < λ_{n−1} − 1, then we can consider a random walk on the modified graph Γ′ formed by adding a loop of weight cd_{v} to each vertex v where c = (λ_{1} + λ_{n−1})/2 − 1. The new graph has (Laplacian) eigenvalues λ′_{k} = \frac{1}{1+c}λ_{k} ≤ 1, 0 ≤ k ≤ n − 1, so that 1 − λ′_{1} ≥ λ′_{n−1} − 1.

Consequently (see [3]), we only need to increase the number of steps of this “lazy” walk on Γ to s ≥ (1/(λ′) log(1/ϵ) to achieve that same L_{2} bound on ϵ∥f∥ where λ′ is

λ′ = \{ \begin{matrix}λ_{1} & if 1 − λ_{1} ≥ λ_{n−1} − 1, \\ \frac{2λ_{1}}{λ_{1}+λ_{n−1}} & otherwise . \end{matrix}

We note that we have λ′ ≥ 2λ_{1}/(2 + λ_{1}) ≥ 2λ_{1}/3.

A stronger notion of convergence is measured by the L_{∞}, or relative pointwise distance, which is defined as follows. After s steps, the relative pointwise distance of P to its stationary distribution π is given by

Δ(s) := max_{x,y} \frac{|P^{s}(y, x) − π(x)|}{π(x)} .

Let δ_{z} denote the indicator function defined by

δ_{z}(x) = \{ \begin{matrix}1 & if x = z, \\ 0 & otherwise . \end{matrix}

Set

T^{1/2}δ_{x} = ∑_{i} a_{i}ϕ_{i}

and

T^{−1/2}δ_{y} = ∑_{i} β_{i}ϕ_{i} .

In particular,

α_{0} = \frac{d_{x}}{\sqrt{vol(Γ)}}, β_{0} = \frac{1}{\sqrt{vol(Γ)}} .

Hence,

Δ(t) = max_{x,y} \frac{|δ_{y}(P^{t})δ_{y} − π(x)|}{π(x)}
= max_{x,y} \frac{|δ_{y}T^{−1/2}(I − L)^{t}T^{1/2}δ_{x} − π(x)|}{π(x)}
(2)  ≤ max_{x,y} ∑_{i≠0} \frac{|(1 − λ_{i})^{t}α_{i}β_{i}|}{d_{x}/vol(Γ)}
≤ (1 − λ)^{t} max_{x,y} \frac{∥T^{1/2}δ_{x}∥∥T^{−1/2}δ_{y}∥}{d_{x}/vol(Γ)}
≤ (1 − λ)^{t} \frac{vol(Γ)}{min_{x,y} \sqrt{d_{x}d_{y}}}
≤ e^{−tλ} \frac{vol(Γ)}{min_{x} d_{x}} .

Thus, if we choose t so that

t ≥ \frac{1}{λ} log \frac{vol(Γ)}{e min_{x} d_{x}}

the electronic journal of combinatorics 4, no. 2 (1997), #R7 6

then after t steps, we have Δ(t) ≤ ϵ. We also remark that requiring Δ(t) → 0 is a rather strong condition. In particular, it implies that another common measure, the total variation distance Δ_{T V} (t) goes to zero just as rapidly, since

Δ_{T V} (t) = max_{A⊂V} max_{y∈V} |∑_{x∈A} P^{t}(y, x) − π(x)|
≤ max_{{A⊂V \atop vol(A)≤ \frac{1}{2} vol(Γ)}} ∑_{x∈A} π(x)Δ(t)
≤ \frac{1}{2}Δ(t) .

We point out here that the factor _{\frac{vol(Γ)}{min_{x} d_{x}}} can often be further reduced by the use of so-called logarithmic Sobolev eigenvalue bounds (see [9] and [3] for surveys). In particular, Diaconis and Saloffe-Coste have used these methods in their work on rapidly mixing Markov chains. We will follow their lead and apply some of these ideas in Section 4.

3. An eigenvalue comparison theorem

To estimate the rate at which Δ(t) → 0 as t → ∞, we will need to lower bound λ_{1}(Γ^{∗}), the smallest non-zero Laplacian eigenvalue of the graph Γ^{∗} on G^{∗}, defined by taking as edges all pairs x̄ȳ ∈ E^{∗} where x̄ ∈ G^{∗} and ȳ can be reached from x̄ by taking one step of the process Q. Our comparison graph Γ^{n} on G^{n} will have all edges x̄ȳ ∈ E where x̄ and ȳ are any two elements of G^{n} which differ in a single coordinate (so that Γ^{n} is just the usual Cartesian product of G with itself n times). Lemma 1. Suppose Γ = (V, E) is a connected (simple) graph and Γ′ = (V′, E′) is a connected multigraph with Laplacian eigenvalues λ_{1} = λ_{1}(Γ) and λ′_{1} = λ_{1}(Γ′), respectively. Suppose ϕ : V → V′ is a surjective map such that:

(i) If d_{x} and d′_{x′} denote the degrees of v ∈ V and x′ ∈ V′, respectively, then for all x′ ∈ V′

we have

∑_{x∈ϕ^{−1}(x′)} d_{x} ≥ ad′_{x′} .

(ii) For each edge e = xy ∈ E there is a path P (e) between ϕ(x) and ϕ(y) in E′ such that:

(a) The number of edges of P (e) is at most ℓ;

(b) For each edge e′ ∈ E′, we have

|{xy ∈ E : e′ ∈ P (e)| ≤ m .

the electronic journal of combinatorics 4, no. 2 (1997), #R7 7

Then we have

λ′_{1} ≥ \frac{a}{ℓm}λ_{1} (3)

Proof. For h : V → ℂ, define h^{2} : E → ℂ by setting h^{2}(e) = (h(x) − h(y))^{2} for e = xy ∈ E (with a similar definition for h : V′ → ℂ and h^{2} : E′ → ℂ).

We start by letting g : V′ → ℂ be a function achieving equality in (1) (or rather, the version of (1) for λ′_{1}). Define f : V → ℂ by setting

f(x) = g(ϕ(x)) for x ∈ V .

Thus,

λ′_{1} = sup_{c} \frac{∑_{e′∈E′} g^{2}(e′)}{∑_{v′∈V′}(g(v′) − c)^{2}d′_{v′}}
(4)  ≥ \frac{∑_{e′∈E′} g^{2}(e′)}{∑_{v′∈V′}(g(v′) − c)^{2}d′_{v′}} for all c
= \frac{∑_{e′∈E′} g^{2}(e′)}{∑_{e∈E} f^{2}(e)} · \frac{∑_{e∈E} f^{2}(e)}{∑_{v∈V} (f(v) − c)^{2}d_{v}} · \frac{∑_{v∈V} (f(v) − c)^{2}d_{v}}{∑_{v′∈V′}(g(v′) − c)^{2}d′_{v′}}
= I × II × III .

First, we treat factor I. Using Cauchy-Schwarz, we have for all e ∈ E,

f^{2}(e) ≤ ℓ ∑_{e′∈P (e)} g^{2}(e′)

by (a). Hence by (b),

m ∑_{e′∈E} g^{2}(e′) ≥ ∑_{e∈E} ∑_{e′∈E′} g^{2}(e′) ≥ \frac{1}{ℓ} ∑_{e∈E} f^{2}(e)

i.e.,

\frac{∑_{e′∈E′} g^{2}(e′)}{∑_{e∈E} f^{2}(e)} ≥ \frac{1}{ℓm} (5)

which gives a bound for factor I. To bound factor III, we have

∑_{x∈V}(f(x) − c)^{2}d_{x} = ∑_{x′∈V′} ∑_{x∈ϕ^{−1}(x′)}(f(x) − c)^{2}d_{x}
(6)  = ∑_{x′∈V′}(g(x′) − c)^{2} ∑_{x∈ϕ^{−1}(x′)} d_{x}
≥ a ∑_{x′∈V′}(g(x′) − c)^{2}d′_{x′}  by (i) .

Finally, for factor II we choose c_{0} so that

sup_{c} \frac{∑_{e∈E} f^{2}(e)}{∑_{v∈V} (f(v) − c)^{2}d_{v}} = \frac{∑_{e∈E} f^{2}(e)}{∑_{v∈V} (f(v) − c_{0})^{2}d_{v}} ≥ λ_{1} (7)

by (1).

Hence, by (4), (5), (6) and (7) we have

λ′_{1} ≥ \frac{a}{ℓm}λ_{1}

which is just (3).

Note that in the case that Γ and Γ′ are regular with degrees k and k′, respectively, then (i) holds with a = k/k′, and (3) becomes

(3′)  λ′_{1} ≥ \frac{k}{k′ℓm}λ_{1} .

4. A comparison theorem for the log-Sobolev constant

Given a connected weighted graph Γ = (V, E), the log-Sobolev constant α = α(Γ) is defined by

α = inf_{f≠constant} \frac{∑_{e∈E} f^{2}(e)}{∑_{x} f^{2}(x)d_{x} log _{\frac{f^{2}(x)}{∑_{y} f^{2}(y)π(y)}}} (8)

where f ranges over all non-constant functions f : V → ℝ and π is the stationary distribution of the nearest neighbor random walk on Γ. In a recent paper [9], Diaconis and Saloffe-Coste show that

(9) Δ_{T V} (t) ≤ e^{1−c} if t ≥ \frac{1}{2α} log log \frac{vol(Γ)}{min_{x} d_{x}} + \frac{c}{λ_{1}} .

This is strengthened in [3], where the slightly stronger inequality is proved

(10) Δ(t) ≤ e^{2−c} if t ≥ \frac{1}{2α} log log \frac{vol(Γ)}{min_{x} d_{x}} + \frac{c}{λ_{1}}

and

(11) Δ_{T V} (t) ≤ e^{1−c} if t ≥ \frac{1}{4α} log log \frac{vol(Γ)}{min_{x} d_{x}} + \frac{c}{λ_{1}}

using the alternate (equivalent) definition:

α = inf_{f≠constant} \frac{∑_{e∈E} f^{2}(e)}{S(f)} (12)

the electronic journal of combinatorics 4, no. 2 (1997), #R7 9

where

(13) S(f) := inf_{c>0} ∑_{x∈V}(f^{2}(x) log f^{2}(x) − f^{2}(x) − f^{2}(x) log c + c)d_{x} .

While (10) is typically stronger than (2), it depends on knowing (or estimating) the value of α, which if anything is harder to estimate than λ_{1} for general graphs. We can bypass this difficulty to some extent by the following (companion) comparison theorem for α. Its statement (and proof) is in fact quite close to that of Lemma 1.

Lemma 2. Suppose Γ = (V, E) is a connected (simple) graph and Γ′ = (V′, E′) is a connected multigraph, with logarithmic Sobolev constants α = α(Γ) and α′ = α(Γ′), respectively. Suppose ϕ : V → V′ is a surjective map such that (i), (ii) and (iii) of Lemma 1 hold. Then

α′ ≥ \frac{a}{ℓm}α . (14)

Proof: Consider a function g : V′ → ℝ achieving equality in (14). Define f : V → ℝ as in the proof of Lemma 1. Then we have

α′ = \frac{∑_{e′∈E′} g^{2}(e′)}{S(g)}
(15)  = \frac{∑_{e′∈E′} g^{2}(e′)}{∑_{e∈E} f^{2}(e)} · \frac{∑_{e∈E} f^{2}(e)}{S(f)} · \frac{S(f)}{S(g)}
= I′ × II′ × III′ .

Exactly as in the proof of Lemma 1, we obtain

I′ ≥ \frac{1}{ℓm}, II′ ≥ α .

It remains to show III′ ≥ a (which we do using a nice idea of Holley and Stroock; cf. [9]). First, define

F (ξ, ζ) := ξ log ξ − ξ log ζ − ξ + ζ

for all ξ, ζ > 0. Note that F (ξ, ζ) ≥ 0 and for ζ > 0, F (ξ, ζ) is convex in ξ. Thus, for some c_{0} > 0,

S(f) = ∑_{x∈V} F (f^{2}(x), c_{0})d_{x}
= ∑_{x′∈V′} ( ∑_{x∈ϕ^{−1}(x′)} d_{x}) F (g(x′)^{2})

the electronic journal of combinatorics 4, no. 2 (1997), #R7 10

≥ ∑_{x′∈V′} ad′_{x′}F (g(x′)^{2}) since F ≥ 0
≥ a ∑_{x′∈V′} F (g(x′)^{2}d′_{x′}) by convexity
= aS(g) .

This implies III′ ≥ a and (14) is proved.

As in (3′), if Γ and Γ′ are regular with degrees k and k′, respectively, then

(13′)  α′ ≥ \frac{k}{k′ℓm}α .

5. Defining the paths

In this section we describe the key path constructions for our proof. For our finite group G, we say that B ⊆ G is a minimal basis for G if ⟨B⟩ = G but for any proper subset B′ ⊂ B, we have ⟨B′⟩ ≠ G. Define

b(G) := max{|B| : B is a minimal basis for G} .

Further, define w(G) to be the least integer such that for any minimal basis B, and any g ∈ G, we can write g as a product of at most w terms of the form x^{±1}, x ∈ B. Finally, define s(G) to be the cardinality of a minimum basis for G. We abbreviate b(G), w(G) and s(G) by b, w and s, respectively, and, as usual, we set r := |G|. In particular, the following crude bounds always hold:

(16) s ≤ b ≤ \frac{log r}{log 2} = log_{2} r, w < r . Let R denote ⌊log_{2} r⌋. We will assume n > 2(s + R). To apply Lemmas 1 and 2, we must define the map ϕ : Γ^{n} → Γ^{∗} and the paths P (e), e ∈ E^{n}. Let {g_{1}, …, g_{s}} be a fixed minimum basis for G.

For x̄ = (x_{1}, …, x_{n}) ∈ Γ^{n}, define

ϕ(x̄) = \{ \begin{matrix}x̄ & if ⟨x̄⟩ = G, \\ (g_{1}, …, g_{s}, x_{s+1}, …, x_{n}) & if ⟨x̄⟩ ≠ G . \end{matrix}

Next, for each edge e = x̄ȳ ∈ E^{n}, we must define a path P (e) between ϕ(x̄) and ϕ(ȳ) in Γ^{∗}. Suppose x̄ and ȳ just differ in the i^{th} component so that

x̄ = (x_{1}, …, x_{i}, …, x_{n}), ȳ = (y_{1}, …, y_{i}, …, y_{n})

where x_{j} = y_{j} for j ≠ i, and x_{i} ≠ y_{i}. There are three cases:

(I) x̄ ∈ G^{∗}, ȳ ∈ G^{∗}. Let I denote interval

\{ \begin{matrix}\{i + 1, …, i + s + 2R\} & if i ≤ n − s − 2R, \\ \{n − s − 2R, …, n\} \ \{i\} & if i > n − s − 2R . \end{matrix}

Choose a subset J ⊂ I so that:

(i) |J| = s
(ii) ⟨{x_{k} : k ∈ [n] \ |J|}⟩ = G
(iii) ⟨{y_{k} : k ∈ [n] \ |J|}⟩ = G .

That is, the values x_{j} = y_{j}, j ∈ J, are not needed in generating G using the x_{k} or the y_{k}. Write J as {j_{1}, j_{2}, …, j_{s}}. In this case ϕ(x̄) = x̄, ϕ(ȳ) = ȳ. To form P (e):

(i) Use a basis from the elements x_{k}, k ∉ J, to change x_{j_{1}} to g_{1}, x_{j_{2}} to g_{2}, …, x_{j_{s}} to g_{s}. This takes at most ws steps;

(ii) Next, use g_{1}, …, g_{s} to change x_{i} to y_{i}. This takes at most w steps;

(iii) Finally, use a basis from the elements y_{k}, k ∉ J, to change g_{1} back to x_{j_{1}} = y_{j_{1}}, …, g_{s} back to x_{j_{s}} = y_{j_{s}}. This takes at most ws steps. Hence, for case (I), P (e) has length at most w(2s + 1).

(II) x̄ ∉ G^{∗}, ȳ ∈ G^{∗}. In this case, ϕ(x̄) = (g_{1}, …, g_{s}, x_{s+1}, …, x_{n}), ϕ(ȳ) = (y_{1}, …, y_{n}) where x_{j} = y_{j} for j ≠ i, and x_{i} ≠ y_{i}. This time we locate a set J of s indices j_{1}, …, j_{s}, with i < j_{1} < ⋯ < j_{s} ≤ i + s + R so that ⟨{y_{k} : k ∈ [n] \ J}⟩ = G. If there is not enough room, i.e., i > n − s − R, then we locate J to lie in {n − s − R, …, n} \ {i}. In addition, if it happens that i ≤ s, then we take J ⊆ {s + 1, …, 2s + R}. Now, to form P (e):

(i) Use g_{1}, …, g_{s} in ϕ(x̄) to change x_{j_{1}} to g_{1}, x_{j_{2}} to g_{2}, …, x_{j_{s}} to g_{s}.

(ii) Use the newly formed g_{1}, …, g_{s} (with indices in J) to change coordinate 1 from g_{1} to y_{1}, coordinate 2 from g_{2} to y_{2}, …, coordinate s from g_{s} to y_{s}. Then change x_{i} to y_{i}.

(iii) Finally use a basis in {y_{k} : k ∉ [n] \ J} to change coordinates j_{1}, …, j_{s} to y_{j_{1}}, …, y_{j_{s}}, respectively. In this case, the length of P (e) is at most w(3s + 1). the electronic journal of combinatorics 4, no. 2 (1997), #R7 12

III) x̄ ∉ G^{∗}, ȳ ∉ G^{∗}. Thus, ϕ(x̄) = (g_{1}, …, g_{s}, x_{s+1}, …, x_{n}), ϕ(ȳ) = (g_{1}, …, g_{s}, y_{s+1}, …, y_{n}) and of course, x_{j} = y_{j}, j ≠ i, and x_{i} ≠ y_{i}. If i > s then we can change x_{i} to y_{i} in at most w steps (and this forms P (e)). If i ≤ s then ϕ(x̄) = ϕ(ȳ) and P (e) does not have to be defined.

The main point in the preceding slightly complicated construction is that it guarantees a rather small value of m. The reason is that the only coordinates u which change in edges of P (e) are either in {1, 2, …, s} or fairly close to i, e.g. |i − u| ≤ 2(s + R). Furthermore, if a changing coordinate u ∈ {1, …, s} and i > 2(s + R), so that we have some edge e′ = (z_{1}, …, z_{s}, …, z_{u}, …, z_{n}), (z_{1}, …, z_{s}, …, z′_{u}, …, z_{n}) in Γ^{∗}, then we search (z_{1}, …, z_{n}) for the first interval of length 2(s + R) which contains g_{1}, …, g_{s}, say {w + 1, …, w + 2(s + R)}. By our construction, such an interval must exist.

Furthermore, it is not hard to see that in this case |i − w| < 4(s + R) (and this is somewhat generous). Consequently, the original point x̄ in e must agree with (z_{1}, …, z_{n}) in all but at most 10(s + R) coordinates. If follows that for these choices of ϕ and P (e), e ∈ E^{n}, we have

m ≤ 10(s + R)r^{10(s+R)} . (17)

Also by previous remarks, we have ℓ ≤ w(3s + 1) . (18) Observe that deg Γ^{n} = (r − 1)n and deg Γ^{∗} = 2n(n − 1).

Consequently, by (3′), (13′), (17) and (18) (after some simplifications)

λ′_{1} ≥ \frac{λ_{1}}{1600R^{2}r^{20R}n}, α′ ≥ \frac{α}{1600R^{2}r^{20R}n} . (19)

6. Putting it all together

The final pieces we need to bound Δ(t) in (10) are the values of λ_{1}(Γ^{n}) and α(Γ^{n}). Fortunately, these are easy to derive since λ_{1} and α behave very nicely under Cartesian products. In particular, we have

λ_{1}(Γ^{n}) = α(Γ^{n}) = \frac{(r − 1)}{r} · \frac{1}{n} . (20)

Note that

vol(Γ^{∗}) ≤ vol(Γ^{n}) = |Γ^{n}| · 2n(n − 1) .

Thus, by (10) we have

Δ(t) ≤ e^{2−c} if t ≥ \frac{1}{2α′} log log |Γ^{n}| + \frac{c}{λ′_{1}}

and, by (11) we have

Δ_{T V} (t) ≤ e^{1−c} if t ≥ \frac{1}{4α′} log log |Γ^{n}| + \frac{c}{λ′_{1}} .

This implies

Theorem 1.

(21) Δ(t) ≤ e^{2−c} if t ≥ 800R^{2}r^{20R+1}n^{2}(log n + log log r + c) .

In other words, c_{r}n^{2} log n steps are enough to force the distribution to be close to uniform, which is what we claimed in the Introduction. Also, we have

Theorem 2.

(22) Δ_{T V} (t) ≤ e^{1−c} if t ≥ 400R^{2}r^{20R+1}n^{2}(log n + log log r + c) .

7. Concluding remarks

Of course, the preceding techniques using comparison theorems can be applied to many other random walk problems of this general type. For example, one could restrict the preceding moves so that p_{i} → p_{i}p_{j}^{±1} is only allowed if (i, j) belongs to some specified set (this determines an underlying digraph).

It is probably true that the correct answer in (21) is actually c_{r}n log n (this is conjectured in [6]). Some evidence in favor of this is our recent result in [4] that O(n log n) steps do suffice when G = ℤ_{2}.

References

[1] David Aldous, talk at 1994 National IMS meeting.

[2] F. Celler, C. R. Leedham-Green, S. Murray, A. Niemeyer and E. A. Obrien, Generating random elements of a finite group, Comm. Alg., 23 (1995), 4931–4948.

[3] F. R. K. Chung, Spectral Graph Theory, Amer. Math. Soc., Providence, RI (to appear 1996).

[4] F. R. K. Chung and R. L. Graham, Stratified random walk on an n-cube, preprint. the electronic journal of combinatorics 4, no. 2 (1997), #R7 14

[5] P. Diaconis, R. L. Graham and J. A. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions, Random Structures and Algorithms, 1 (1990), 51–72.

[6] P. Diaconis and L. Saloffe-Coste, Walks on generating sets of group, Stanford Technical Report No. 481, July 1995, 36 pages.

[7] P. Diaconis and L. Saloffe-Coste, Walks on generating sets of abelian groups, Probab. Theory Relat. Fields, 105 (1996), 393-421.

[8] P. Diaconis and L. Saloffe-Coste, Walks on generating sets of groups, Stanford Technical Report No. 497, July 1996, 40 pages. Probab. Theory Relat. Fields, 105 (1996), 393-421.

[9] P. Diaconis and L. Saloffe-Coste, Logarithmic Sobolev inequalities for finite Markov chains (preprint 1995).

[10] P. Diaconis and M. Shashahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal., 18 (1987), 208–218.