18.317 Combinatorics, Probability, and Computations on Groups 26 September 2001

Lecture 8

Lecturer: Igor Pak Scribe: Bo-Yin Yang

The Plot

Our general plan for these few lectures is to prove the following will “usually” (with probability arbitrarily close to 1) happen:

1. Random O(log |G|) group elements will generate the group G.

2. Random O(log |G|) group elements will generate the group G with diameter O(log |G|), and will do so even with random products only. (Note: This is essentially what the Erdős–Rényi Theorem says.)

3. Random walks (more strongly, “lazy” random walks) on G with O(log |G|) random elements as generators mixes in O(log |G|) time.

4. Cayley graph of G with O(log |G|) random generators is an expander (we will get to this later).

At this point the Erdős–Rényi Theorem is not yet very useful since it is not that easy to obtain a random sample of elements in the first place. We aim to ameliorate this in the next two lectures.

Extending Erdős–Rényi to Words

Assume that w = w_{1}w_{2} ⋯ w_{m} is a “word” made up of “letters” w_{j}, each of which belongs to the “alphabet” {g_{1}, g_{2}, …, g_{k}}. Further assume that each of g_{1}, g_{2}, …, g_{k} appears at least once within the word.

Let Qw ; ḡ(h) ≡ Pr_{ϵ}(w_{1}^{ϵ_{1}} w_{2}^{ϵ_{2}} ⋯ w_{m}^{ϵ_{m}} = h). We aim to show that this Q has the same nice properties as P.

Proposition 1

Prḡ (max_{h∈G} |Qw ; ḡ(h) − \frac{1}{|G|}| < \frac{ϵ}{|G|}) > 1 − δ,

where k > 2 log_{2} |G| + 2 log_{2} \frac{1}{ϵ} + log \frac{1}{δ} (as previously in Erdős–Rényi).

Proof: We first define the notation of “conjugation” for a, x ∈ G (Igor: “Sorry for the slightly confusing notation, but this is how algebraists actually write it.”):

a^{x} ≡ x a x^{−1}.

Claim 2 (“obvious”)

1. (a^{x})^{y} = a^{yx} 2. (a^{x})^{ϵ} = (a^{ϵ})^{x} for ϵ = 0, or 1.

3. if a is uniformly random in G, then so is a^{x} for any fixed x ∈ G.

Now we look at the word w and “restructure” by look at repetitive reappearances of any g_{i}. For example if

w = g_{1} g_{2} g_{3} g_{4} g_{1} g_{5} g_{3} g_{7} ⋯

then we proceed as follows:

w = \overbrace{g_{1} g_{2} g_{3} g_{4} g_{1}}^{first} g_{5} g_{3} g_{7} ⋯
= g_{1}g_{2} \underbrace{g_{3}g_{4}(g_{5})^{g_{1}}(g_{3})^{g_{1}}}_{second}(g_{7})^{g_{1}} ⋯ g_{1}

= g_{1}g_{2}g_{3}g_{4}(g_{5})^{g_{1}}(g_{7})^{(g_{3}g_{1})} ⋯ g_{3}g_{1}
= ⋯

We will proceed the same way with or without the ϵ_{i} powers. What will we end up with? Let h_{1}, h_{2}, …, h_{k} be the g_{j} permuted to the order of appearance in w. Then we will eventually end with

w = (h_{1} (h_{2})^{ϕ_{2}(h_{1})} (h_{3})^{ϕ_{3}(h_{1},h_{2})} ⋯ (h_{k})^{ϕ_{k}(h_{1},...,h_{k−1})}) · ((ℓ_{1})^{ψ_{1}(h_{1},...,h_{k})} (ℓ_{2})^{ψ_{2}(h_{1},...,h_{k})} (ℓ_{m−k})^{ψ_{m−k}(h_{1},...,h_{k})}) ,

where ℓ_{1}, …, ℓ_{m−k} are “leftovers”, g_{i}’s in a permutation with repetition, and the ϕ_{i}’s and ψ_{i}’s are fixed products of the letters h_{j}.

Let ε_{j} be the corresponding ϵ_{i} power of h_{j} at each initial appearance. It is then straightforward to verify that

wϵ̄ = (h_{1}^{ε_{1}} ((h_{2})^{ϕ′_{2}})^{ε_{2}} ((h_{3})^{ϕ′_{3}})^{ε_{3}} ⋯ ((h_{k})^{ϕ′_{k}})^{ε_{k}}) · ( ∏_{i=1}^{m−k} ((ℓ_{i})^{ψ′_{i}})^{ε′_{i}})

True, now the ϕ_{i}’s not only depend on h_{j} for each j < i, but may also depend on the random powers ε′_{i} ∈ {0, 1} for every i; and each ψ′_{i} not only does depend on all the h_{j} but it also may depend on ε′_{j} for each j > i. However, we can verify that that

• for each given ε′_{1}, ε′_{2}, …, ε′_{m−k}, the “junk tail” J ≡ (∏_{i=1}^{m−k} ((ℓ_{i})^{ψ′_{i}})^{ε′_{i}}) is fixed in G.

• for each given ε′_{1}, ε′_{2}, …, ε′_{m−k} and given h_{1}, h_{2}, h_{i−1}, the function ϕ′_{i} is fixed in G; hence ((h_{i})^{ϕ′_{i}}) is

uniformly random in G if h_{i} itself is. I.e. Probability in terms of ((h_{i})^{ϕ′_{i}}) is just like probability in terms of h_{i} themselves.

• We see from the above that Qw ; ḡ(h) is some kind of average over Qh̄(d) for all d ∈ G, hence

max_{h∈G} |Qw ; ḡ(h) − \frac{1}{|G|}| < max_{h∈G} |Qḡ(h) − \frac{1}{|G|}| ,

and the proposition is proved.

Not Quite Uniform Distributions

Now we turn our attention to the situation where we have a way of sampling from a group that is not uniformly random. We can measure how “non-uniform” the sampling is in a few different ways. Assume that P is a probability distribution on G and U is the uniform distribution, then we could use the “total variation”

∥P − U∥ ≡ max_{B⊂G} |P (B) − \frac{|B|}{|G|}| = \frac{1}{2} ∑_{g∈G} (P (\{g\}) − \frac{1}{|G|});

we could also use the “separation”, defined as (note! no absolute value):

sep(P) ≡ |G| max_{g∈G} (\frac{1}{|G|} − P (\{g\})) .

The two distances satisfy 0 ≤ ∥P − U∥ ≤ sep(P) ≤ 1. Note also that sep(P) is essentially an ℓ_{∞} norm, since

Prḡ (max_{h∈G} |Qw ; ḡ(h) − \frac{1}{|G|}| > \frac{ϵ}{|G|}) < δ ⇔ Pr (sep(Q_{g}) > ϵ) < δ.

The separation is useful because when sep(P) < ϵ, we can find a distribution N where

P = (1 − ϵ) U + ϵ N.

Figuratively, to sample from P, we first pick a random variable in [0; 1], if it is less than ϵ we then sample from the “noise” distribution N, otherwise we sample from the uniform distribution U.

In other words, if sep(P) = s, then we can let k̃ = k/(1 − s), where k is the requisite number from Erdős– Rényi. If we take more than k̃ samples from P, enough of these samples – “usually” at least k – will be sampled from the “uniform” part U, hence the “lazy random walk will again be probabilistically almost uniform. We will make that more rigorous by repeating the trick used today in the next lecture to show that we will be able to approximate a uniform sampling of the group from nonrandomly generated random products.