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 Gnof 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 crn2log nwhere the constant crdepends only on
the order rof G.
1. Introduction
One method often used in computational group theory for generating random elements
from a given (non-trivial) finite group Gproceeds as follows (e.g., see [2]). A fixed integer
n≥2 is initially specified. Denote by Gnthe set {(x1,...,x
n):x
i∈G, 1≤i≤n}.If
¯
x
=(
x
1
,...,x
n)∈G
n, we denote by h¯
xithe subgroup of Ggenerated by {xi:1≤i≤n
}.Let
G
∗⊆G
ndenote the set of all ¯
x∈Gnsuch that h¯
xi=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)withi6=j
. (Thus, each such pair is chosen with probability
1
n(n−1) .) We then move to one of ¯
p′=(
p
′
1
,...,p
′
n)where
p
′
k=
p
i
p
jor pip−1
jif k=i, each with probability 1/2
pkif k6=i.
This rule determines the corresponding transition matrix Qof the walk. We note that with
this rule, we always have ¯
p′∈G∗. Itisalsoeasytocheckthatforn≥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)).
1Research supported in part by NSF Grant No. DMS 95-04834
the electronic journal of combinatorics 4, no. 2 (1997), #R7 2
Starting from some fixed initial distribution f0on G∗, we apply this procedure some number
of times, say t, to reach a distribution f0Qton G∗which we hope will be close to “random”
when tis large. A crucial question which must be faced in this situation is just how rapidly
this process mixes, i.e., how large must tbe so that f0Qtis 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)n2log n,where
c(G) is a constant depending only on G,thenQ
tis already quite close to uniform (where we
usually will suppress f0).
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)areallowedinformingp
′
k=p
i
p
jor pip−1
j. These pairs can be described by a
graph Hon 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=Zpwith p=2,3,4,5,7,8,9
we know that n2log nsteps are enough whereas for G=Z6or Z10 we only know that n4log nare
enough. Even in the case of Z6it 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)n2log n
can be obtained for all groups Gwhere c(G) is a constant depending just on G. Subsequently,
they have now [8] also obtained bounds of the form c(G)n2log nfor all groups Gby 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→R
satisfying w(u, v)=w(v, u)≥0 for all u, v ∈V. The edge set Eof Γ 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 dvof a vertex vis defined by
dv:= X
u
w(u, v).
the electronic journal of combinatorics 4, no. 2 (1997), #R7 3
Further, we define the |V|×|V|matrix Lby
L(u, v)=
d
v−w(v, v)ifu=v,
−w(u, v)ifuv ∈E,u6=v,
0otherwise .
In particular, for a function f:V→R,wehave
Lf(x)= X
y
xy∈E
(f(x)−f(y))w(x, y).
Let Tdenote the diagonal matrix with the (v, v) entry having the value dv.TheLaplacian LΓ
of Γ is defined to be
L=LΓ=T−1/2LT −1/2.
In other words,
L(u, v)=
1−w(v,v)
dvif u=v,
−w(u,v)
√dudvif uv ∈E,u6=v,
0otherwise .
Since Lis 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
fsup
cP
u,v∈E
(f(u)−f(v))2w(u, v)
P
x
dx(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/dvof
moving from a vertex vto any one of its neighbors. The transition matrix Pthen satisfies
P(v, u)=(1/dvif uv ∈E,
0otherwise .
That is,
fP(u)= X
v
uv∈E
1
dv
f(v)
the electronic journal of combinatorics 4, no. 2 (1997), #R7 4
for any f:V→R.Itiseasytocheckthat
P=T
−1/2
(I−R)T
1/2=T
−1
A
where Ais the adjacency matrix of the graph.
In a random walk on a connected weighted graph Γ, the transition matrix Psatisfies
1TP =1T.
Thus, the stationary distribution is just 1T/vol(Γ), where vol(Γ) = P
x
dxand 1is the all ones
vector. Our problem is to estimate how rapidly fPkconverges to its stationary distribution,
as k→∞, starting from some initial distribution f:V→R. First, consider convergence in
the L2(or Euclidean) norm. Suppose we write
fT−1/2=X
i
a
iφ
i
where φidenotes the eigenfunction associated with λiand kφik=1. Sinceφ
0=1·T
1/2
/
pvol(Γ)
then
a0=hfT−1/2,1T1/2i
k1T1/2k=1
pvol(Γ)
since hf,1i=1. Wethenhave
kfPs−1T/vol(Γ)k=kfT−1/2(I−L)
sT1/2−a
0
φ
0
T1/2
k
=°
°
°
°
°X
i6=0
(1 −λi)saiφiT1/2°
°
°
°
°
≤(1 −λ)skfk
≤e−sλkfk
where
λ=
λ1if 1 −λ1≥λn−1−1,
2−λn−1otherwise .
So, after s≥(1/λ) log(1/ǫ) steps, the L2distance between fPsand its stationary distribution
is at most ǫkfk.
Although λoccurs in the above bound, in fact only λ1is 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 cdvto each vertex vwhere c=(λ
1+λ
n−1
)/2−1. The new
graph has (Laplacian) eigenvalues λ′
k=1
1+cλk≤1, 0 ≤k≤n−1, so that 1 −λ′
1≥λ′
n−1−1.
the electronic journal of combinatorics 4, no. 2 (1997), #R7 5
Consequently (see [3]), we only need to increase the number of steps of this “lazy” walk on Γ
to s≥(1/(λ′) log(1/ǫ)toachievethatsameL
2bound on ǫkfkwhere λ′is
λ′=
λ1if 1 −λ1≥λn−1−1,
2λ1
λ1+λn−1otherwise .
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,
whichisdefinedasfollows. Afterssteps, the relative pointwise distance of Pto its stationary
distribution πis given by
∆(s):=max
x,y
|Ps(y, x)−π(x)|
π(x).
Let δzdenote the indicator function defined by
δz(x)=(1ifx=z,
0otherwise .
Set
T1/2δx=X
i
aiφi
and
T−1/2δy=X
i
βiφi.
In particular,
α0=dx
pvol(Γ),β
0
=1
p
vol(Γ) .
Hence,
∆(t)=max
x,y
|δy(Pt)δy−π(x)|
π(x)
=max
x,y
|δyT−1/2(I−L)
t
T1/2
δ
x−π(x)|
π(x)
≤max
x,y X
i6=0
|(1 −λi)tαiβi|
dx/vol(Γ)
(2)
≤(1 −λ)tmax
x,y
kT1/2δxkkT−1/2δyk
dx/vol(Γ)
≤(1 −λ)tvol(Γ)
min
x,y pdxdy
≤e−tλ vol(Γ)
min
xdx
.
Thus, if we choose tso that
t≥1
λlog vol(Γ)
emin
xdx