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

Lecture 9

Lecturer: Igor Pak Scribe: Christopher Malon

Generalized Random Subproducts

Today, we start to upgrade the Erdős–Rényi machine to show that “most” generating sets of size O(log |G|) have a mixing time of O(log |G|). We’ll be more precise about this in due course.

First, we want to show that Erdős–Rényi is robust when we insert junk in the middle of our strings. Fix \overline{g} = (g_{1}, g_{2}, …, g_{k}) ∈ G^{k}. On Monday, we defined a probability distribution over G

Q\overline{g}(h) = Pr\overline{ϵ} [g_{1}^{ϵ_{1}} ⋯ g_{k}^{ϵ_{k}} = h]

where \overline{ϵ} = (ϵ_{1}, …, ϵ_{k}) is picked randomly, uniformly from \{0, 1\}^{k}. Now fix group elements x_{1}, …, x_{l} and integers γ_{1}, …, γ_{l}. We insert the x_{i} at intervals γ_{i}: Let

R\overline{g}(h) = Pr\overline{ϵ} [g_{1}^{ϵ_{1}} ⋯ g_{γ_{1}}^{ϵ_{γ_{1}}} x_{1}g_{γ_{1}+1}^{ϵ_{γ_{1}+1}} ⋯ g_{γ_{1}+γ_{2}}^{ϵ_{γ_{1}+γ_{2}}} x_{2} ⋯ x_{l} ⋯ g_{k}^{ϵ_{k}} = h]

Let’s look at this in the case where l = 1. In this case, we are considering products of the form

g_{1}^{ϵ_{1}} ⋯ g_{i}^{ϵ_{i}}xg_{i+1}^{ϵ_{i+1}} ⋯ g_{k}^{ϵ_{k}} = g_{1}^{ϵ_{1}} ⋯ g_{i}^{ϵ_{i}}(g_{i+1}^{x})^{ϵ_{i+1}} ⋯ (g_{k}^{x})^{ϵ_{k}}x

where i = γ_{1}, x = x_{1}, and g^{x} denotes xgx^{−1}. Declare \overline{z}(x, γ) = (1, …, 1, x, …, x), where 1’s appear in the first i positions, and write

(g_{1}, …, g_{k})^{(z_{1},...,z_{k})} = (g_{1}^{z_{1}}, …, g_{k}^{z_{k}})

Evidently,

R\overline{g}(h) = Q\overline{g}_{\overline{z}(x,γ)}(hx^{−1})

If l > 1, we just have to repeat these maneuvers to define a string \overline{z}(\overline{x}, \overline{γ}) and a function f(\overline{x}) so that

g_{1}^{ϵ_{1}} ⋯ g_{γ_{1}}^{ϵ_{γ_{1}}} x_{1}g_{γ_{1}+1}^{ϵ_{γ_{1}+1}} ⋯ g_{γ_{1}+γ_{2}}^{ϵ_{γ_{1}+γ_{2}}} x_{2} ⋯ x_{l} ⋯ g_{k}^{ϵ_{k}} = (\overline{g}^{\overline{z}(\overline{x},\overline{γ})})\overline{ϵ} · (f(\overline{x}))^{−1}

Then we have

R\overline{g}(h) = Q\overline{g}_{\overline{z}(\overline{x},\overline{γ})}(h · f(\overline{x}))  (1)

We want to show R\overline{g} is usually close to uniform.

Definition 1 A probability distribution Q on a finite group G is ϵ–uniform if

Q(h) > \frac{1 − ϵ}{|G|}

for all h ∈ G.

Two lectures ago, we proved:

Theorem 2 (Erdős–Rényi ) For all ϵ, δ > 0, Q\overline{g} is ϵ–uniform for more than 1 − δ proportion of \overline{g} ∈ G^{k}, given k > 2 log_{2} |G| + 2 log_{2} \frac{1}{ϵ} + log_{2} \frac{1}{δ}.

Multiplication by f(\overline{x}) is a bijection on the elements of G, so ϵ–uniformity of Q\overline{g}(h) over h implies ϵ– uniformity of Q\overline{g}(h · f(\overline{x})) over h. Because conjugation by \overline{z}(\overline{x}, \overline{γ}) is a bijection on G^{k}, the R\overline{g} will be ϵ–uniform for the same proportion of \overline{g} as Q\overline{g}, applying equation (1). Thus, we have Erdős–Rényi for R\overline{g}:

Theorem 3 For all ϵ, δ > 0, R\overline{g} is ϵ–uniform for more than 1 − δ proportion of \overline{g} ∈ G^{k}, given k > 2 log_{2} |G| + 2 log_{2} \frac{1}{ϵ} + log_{2} \frac{1}{δ}.

Now, we look at a probability distribution of group elements over a larger sample space, describing what happens when the x_{i} may or may not be inserted. Define

Q_{\overline{g},\overline{x}}(h) = Pr_{\overline{ϵ},\overline{α}} [g_{1}^{ϵ_{1}} ⋯ g_{γ_{1}}^{ϵ_{γ_{1}}} x_{1}^{α_{1}}g_{γ_{1}+1}^{ϵ_{γ_{1}+1}} ⋯ g_{γ_{1}+γ_{2}}^{ϵ_{γ_{1}+γ_{2}}} x_{2}^{α_{2}} ⋯ x_{l}^{α_{l}} ⋯ g_{k}^{ϵ_{k}} = h]

where \overline{α} is picked uniformly from \{0, 1\}^{l}. For fixed \overline{α}, let

R_{\overline{g},\overline{x},\overline{α}}(h) = Pr\overline{ϵ} [g_{1}^{ϵ_{1}} ⋯ g_{γ_{1}}^{ϵ_{γ_{1}}} x_{1}^{α_{1}}g_{γ_{1}+1}^{ϵ_{γ_{1}+1}} ⋯ g_{γ_{1}+γ_{2}}^{ϵ_{γ_{1}+γ_{2}}} x_{2}^{α_{2}} ⋯ x_{l}^{α_{l}} ⋯ g_{k}^{ϵ_{k}} = h]

Then we have

Q_{\overline{g},\overline{x}} = \frac{1}{2^{l}} ∑_{\overline{α}} R_{\overline{g},\overline{x},\overline{α}}  (2)

Suppose k > 2 log_{2} |G| + 2 log_{2} \frac{1}{ϵ} + log_{2} \frac{1}{δ} is fixed. Draw a grid whose rows represent the choices of \overline{g} from G^{k}, and whose columns represent the choices of \overline{α}. Keep l, \overline{γ}, and \overline{x} fixed. Mark the (\overline{g}, \overline{α}) position in this grid if R_{\overline{g},\overline{x},\overline{α}} is ϵ–uniform. Theorem 3 applies to R_{\overline{g},\overline{x},\overline{α}}, saying that in every column (i.e. for any fixed \overline{α}), the proportion of unmarked squares is less than δ. Consequently, less than \sqrt{δ} of the rows have more than \sqrt{δ} of their positions unmarked. By equation (2), for more than 1 − \sqrt{δ} of the \overline{g},

Q_{\overline{g},\overline{x}}(h) > \frac{1 − \sqrt{δ}}{|G|} (1 − ϵ)

This proves:

Theorem 4 For every ϵ, δ > 0, Q_{\overline{g},\overline{x}} is (ϵ + δ)–uniform for more than 1 − \sqrt{δ} proportion of \overline{g}, given k > 2 log_{2} |G| + 2 log_{2} \frac{1}{ϵ} + log_{2} \frac{1}{δ}.

Lazy Random Walks

Now we return to our question about mixing time.

Definition 5 Fix \overline{g} = (g_{1}, …, g_{k}), not necessarily generating G. A lazy random walk through \overline{g} is a sequence of group elements X_{t} such that X_{0} = 1 and X_{t+1} = X_{t} · g_{i_{t+1}}^{ϵ_{t+1}}, where each i_{t+1} is picked randomly, uniformly from {1, …, k}, and ϵ_{t+1} is picked randomly, uniformly from {0, 1}. Thus

X_{t} = g_{i_{1}}^{ϵ_{1}} ⋯ g_{i_{t}}^{ϵ_{t}}

Let P t ; \overline{g} be the probability distribution of the lazy random walk through \overline{g} after t steps. Today’s work has shown us: If, after t steps, we have selected k′ distinct i’s (where k′ is at least as big as in theorem 4), then P t ; \overline{g} will be close to uniform for most \overline{g}; the redundant generators chosen in the lazy random walk will take the place of \overline{x}.

From the Coupon Collector’s Problem, we can compute how big t must be in order to provide enough generators. If we need to collect all the g_{i} and \overline{g} = (g_{1}, …, g_{k}), the expected waiting time is

1 + \frac{k}{k − 1} + \frac{k}{k − 2} + … + k = k log k + O(k)

We’ll fill in more details in the next lecture.