By Lemma 2, \(\operatorname {Tr}(A^{2m}) = \sum _{i=0}^{n-1}\mu _i^{2m}\). All terms are nonnegative (even powers), so \(\operatorname {Tr}(A^{2m}) - \mu _0^{2m} = \sum _{i \ge 1}\mu _i^{2m} \ge \mu _1^{2m}\). Taking \(2m\)-th roots gives \(|\mu _1| \le (\operatorname {Tr}(A^{2m}) - \mu _0^{2m})^{1/2m}\).

Let \(A = A^{*}\) be the normalized adjacency matrix; its largest eigenvalue is \(\mu _0 = 1\) (the all-ones eigenvector). By Lemma 12, \(|\mu _{1}^{*}| \le (\operatorname {Tr}(A^{2m}) - 1)^{1/2m}\). Since \(y \mapsto y^{1/2m}\) is concave, Jensen’s inequality (Lemma 3) gives \(\mathbb {E}(|\mu _{1}^{*}|) \le (\mathbb {E}(\operatorname {Tr}(A^{2m})) - 1)^{1/2m}\). The diagonal entry \((A^{2m})_{gg}\) is the probability that a length-\(2m\) walk from \(g\) is closed; by vertex transitivity (Lemma 8) this is the same for every \(g\), so \(\operatorname {Tr}(A^{2m}) = n\, P_{2m}\) and \(\mathbb {E}(\operatorname {Tr}(A^{2m})) = n\, \mathbb {E}(P_{2m})\). Substituting yields (1).

The number of ways to choose which positions of the \(2m\)-letter word form the sub-block that reduces to the identity is at most \(2^{2m}\). This block has length at least \(2m\ln \ln 2m / \ln 2m\), and with \(d = c\log _2 n\) distinct letters the probability that such a block is an identity sequence is, by Lemma 15, at most \((2/d)^{(\text{block length})/2} = (2/c\log _2 n)^{m\ln \ln 2m / \ln 2m}\). Multiplying the count of placements by this probability gives (3).

If no letter appears exactly once then the number of distinct letters in \(W\) is at most \(l(W)/2\). Expose the letters of \(W\) in two stages: first the first occurrence of each distinct letter (at most \(2^{l(W)}\) ways to place this sub-block of size at most \(l(W)/2\)), then the remaining occurrences. Each remaining letter must coincide with one already exposed, an event of probability at most \(l(W)/2c\log _2 n\), and there are at least \(l(W)/2\) such remaining letters. Hence \(\operatorname {Pr}(B) \le 2^{l(W)}(l(W)/2c\log _2 n)^{l(W)/2}\). Since \(l(W) \le 2m\), the second inequality follows.

Since neither \(A\) nor \(B\) holds, the reduced word has a letter \(\tau \) that appears exactly once. Expose the assignments of all letters except \(\tau \); write \(x(\tau )\) for the (still random) assignment of \(\tau \). The event that the word evaluates to the identity becomes a single equation \(g\, x(\tau )\, h = 1\) with \(g,h \in G\) known. As \(x(\tau )\) is uniform over the at least \(n - 2m\) group elements not yet used, this equation has probability at most \(1/(n-2m) = 1/n + O(m/n^2)\).

Following [BS], realize the random pair (set \(S\), walk) by a dynamic process: (a) choose a random word of length \(2m\) in the free monoid \(M_{2c\log _2 n}\); (b) reduce it in the free group \(F_{c\log _2 n}\); (c) assign to each letter a random element of \(G\). This is equivalent to first choosing the random Cayley graph with \(|S| = c\log _2 n\) and then a random walk of length \(2m\). The event “the walk of length \(2m\) is closed” is contained in \(A \cup B \cup C\), so

Substituting the bounds (3), (4), (5) from Lemmas 16, 17, 18 gives the claim. (When the right-hand side of (4) is at most \(1\) it is monotone decreasing in \(l(W)\), so its maximum is at the minimal \(l(W) = l(w)\); otherwise the estimate is trivial.)

Combine Lemma 19 with the trace bound (1) of Lemma 14:

Set \(2m \sim \ln n / b\) for an absolute constant \(b\). For large \(n\) the upper bound becomes

For every fixed \(1 {\gt} \delta {\gt} 0\) one can choose \(b\) and \(c\) so this is smaller than \(1 - \delta \); in particular if \(\delta {\lt} 1 - \tfrac 1e\) then \(b = 1\) and \(c \ge (1+o(1))\, 2e^4\ln 2 / [(1-\delta )e - 1]^2\) suffice, giving \(\mathbb {E}|\mu _{1}^{*}| \le 1 - \delta \).

Choose the elements \(x_1, \dots , x_d\) of \(S\) one by one in order of index, and let \(d = \lambda _0 \ge \lambda _1 \ge \dots \ge \lambda _{n-1}\) be the eigenvalues of \(X(G,S)\). Fix \(j\) with \(1 \le j \le n-1\) and let \(F_i^{j} = \mathbb {E}(\lambda _j(X(G,S)) \mid x_1, \dots , x_i)\) be the conditional expectation given the first \(i\) generators. Then \((F_0^{j}, \dots , F_d^{j})\) is a martingale, and by the variational (min–max) characterization of the \(j\)-th eigenvalue, changing a single generator moves \(\lambda _j\) by at most \(2\), so \(|F_{i+1}^{j} - F_i^{j}| \le 2\). Azuma’s inequality (Lemma 4) gives \(\operatorname {Pr}(|\lambda _j - \mathbb {E}\lambda _j| \ge 2cd^{1/2}) = \operatorname {Pr}(|F_d^{j} - F_0^{j}| \ge 2cd^{1/2}) \le 2e^{-c^2/2}\). The second largest eigenvalue in absolute value is either \(\lambda _1\) or \(\lambda _{n-1}\); applying the bound to both and taking a union bound yields the factor \(4\).

By Theorem 20, with the appropriate \(c\), the expected normalized second eigenvalue is at most \(1 - \delta \) for a \(\delta = \delta ( \varepsilon )\). By the concentration Lemma 22, \(\mu _{1}^{*}\) deviates from its mean by more than \(o(1)\) with probability tending to \(0\); hence almost surely \(\mu _{1}^{*}[X(G,S)] \le 1 - \delta + o(1) \le 1 - \delta /2\). The easy direction of the eigenvalue/expansion connection (Lemma 11) then makes \(X(G,S)\) an \(\varepsilon \)-expander almost surely.