18.317 Combinatorics, Probability, and Computations on Groups 16 November 2001

Lecture 26

Lecturer: Igor Pak Scribe: Igor Pavlovsky

Babai’s Algorithm continued: escape time

Last time, we proved

Theorem 1 Let C be a subset of the group G, S = S^{−1} a symmetric generating set, π = U(S) the uniform distribution on S, and p_{π} the “one-step evolution” of the random walk (i.e. p_{π}φ = U(S) ⋆ φ). Then for any probability distribution φ,

∥p_{π}φ∥^{2} ≤ (1 − \frac{|G\C|}{2 · A · |G|}) · ∥φ∥^{2}

where A = d · |S| · max_{s∈S} max_{g∈C̄} μ_{s}(g), d = diam(C̄, G).

We will use this theorem to bound the escape time of a random walk X_{t} generated by S. For a subset C of G, set

φ_{t}(g) = Pr[X_{t} = g and X_{i} ∈ C ∀i = 1 … t]

Obviously, supp φ_{t} ⊂ C, ∥φ_{0}∥ ≤ 1 (1 if C contains 1_{G}, 0 otherwise) and

φ_{t+1}(g) = \{ \begin{matrix}(p_{π}φ_{t})(g) & if g ∈ C \\ 0 & otherwise \end{matrix}

Inductively applying the above theorem, conclude

Corollary 2 ∥φ_{t}∥^{2} ≤ (1 − \frac{|G\C|}{2·A·|G|})^{t}

Given a bound ∥φ_{t}∥^{2} ≤ ϵ, we’d like to bound the “non-escape” probability p = ∑_{g∈C} φ_{t}(g). It is clear that

the worst situation is when φ_{t}(g) = \frac{p}{|C|} is uniform on C. In that case, ∥φ_{t}∥^{2} = ∑_{g∈C} (φ_{t}(g))^{2} = |C|\frac{p^{2}}{|C|^{2}} =

\frac{p^{2}}{|C|}. Hence, p^{2} ≤ |C|ϵ. In other words:

Lemma 3 If ∥φ_{t}∥^{2} ≤ \frac{α^{2}}{|C|}, then Pr[X_{1}, …, X_{t} ∈ C] ≤ α.

Combining the last two results, obtain

Corollary 4 Suppose |C| ≤ |G|/2. Then Pr[X_{1}, …, X_{t} ∈ C] ≤ (1 − \frac{1}{4A})^{t/2} \sqrt{|C|}.

The first tool for our main escape-time theorem is now ready:

Proposition 5 Let C be a subset of a finite group G, let {X_{t}}_{t} be a random walk on G w.r.t. some symmetric generating set. Suppose |C| ≤ |G|/2. Then Pr[X_{1}, …, X_{t} ∈ C] ≤ \frac{1}{e} for t ≥ 4A(log |C| + 2).

The following result will provide the remaining tool.

Proposition 6 Let C = C^{−1} be a symmetric subset of a finite group G, let {X_{t}}_{t} be a random walk on G w.r.t. some (arbitrary) generating set, and suppose Pr[X_{t} ∈ C^{2} for all 1 ≤ t ≤ T] ≤ 1−p. Then for m ≥ 2T,

\frac{1}{m} ∑_{t=1}^{m} Pr[X_{t} ∉ C] ≥ \frac{p}{p + 1} · \frac{T}{m}

Proof: Set τ to be the hitting time of G\C^{2}, i.e. the first t with X_{t} ∉ C^{2}; then Pr[τ ≤ T] ≥ p. Note that if τ ≤ T, then {τ, τ + 1, …, τ + T − 1} ⊂ {1, …, m}. Set z = X_{τ} and observe (z · C) ∩ C = ∅. The idea is that once the random walk wanders outside of C and in fact to a point z outside of the much bigger C^{2}, it is likely to stay in a C-neighborhood of z (which is outside of C!) for some time. Compute:

\frac{1}{m} ∑_{t=1}^{m} Pr[X_{t} ∉ C] ≥ \frac{1}{m}Pr[τ ≤ T] · ∑_{t=τ}^{τ+T −1} Pr[zX_{t} ∈ zC]

≥ \frac{p}{m} ∑_{t=τ}^{τ+T −1} Pr[X_{t} ∈ C] ≥ \frac{p}{m} (∑_{t=1}^{m} Pr[X_{t} ∈ C] − (m − T) · 1)

≥ \frac{p}{m} (T − ∑_{t=1}^{m} Pr[X_{t} ∉ C])

Here in the first line we used that X_{τ+t} has the distribution of z · X_{t}, and in the second line that the m − T extra terms Pr[X_{t} ∈ C] on the right all are ≤ 1. Now denote by q the expectation in question: q = \frac{1}{m} ∑_{t=1}^{m} Pr[X_{t} ∉ C]. The above inequality translates into q ≥ p (\frac{T}{m} − q). Solve for q.

When m = 2T and p = 1 − \frac{1}{e}, the proposition gives q ≥ \frac{e−1}{2e−1} · \frac{1}{2} > \frac{1.5}{5} · \frac{1}{2} > \frac{1}{8}. Hence, at last,

Theorem 7 Let C = C^{−1} be a symmetric subset of a finite group G, with |C^{2}| ≤ |G|/2. Let {X_{t}}_{t} be a random walk on G w.r.t. some symmetric generating set. Then for 2·T ≥ 2·4A(log |C|^{2} +2) = O(16 log |C|), the escape-expectation is “large”:

\frac{1}{2T} ∑_{t=1}^{2T} Pr[X_{t} ∉ C] > \frac{1}{8}

Therefore, in Babai’s Algorithm, run the random walk on G for a random α ∈ [1 … L] steps (L = O(log^{3} |G|) as before, > O(log |G|)). At the end of many – 1/8th – of l = O(16 log |G|) such runs, we expect to wonder away from any “small” subset. Done!