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

Lecture 7

Lecturer: Igor Pak Scribe: Etienne Rassart

The Erdös-Rényi “Machine”

Let g_{1}, g_{2}, …, g_{k} ∈ G and consider h = g_{1}^{ε_{1}} ⋯ g_{k}^{ε_{k}}, where the ε_{i} ∈ {0, 1} are i.i.d. random variables. These h are called random subproducts. A theorem of Erdös and Rényi shows that when k is large, the distributions of the h becomes “close” to the uniform distribution on G. Definition 1 Pick ḡ = (g_{1}, …, g_{k}) uniformly in G^{k}, and fix it. We can then define the probability distribution

Qḡ(h) = Prε̄[g_{1}^{ε_{1}} ⋯ g_{k}^{ε_{k}} = h] ,

where the ε_{i} ∈ {0, 1} are i.i.d. random variables and ε̄ = (ε_{1}, …, ε_{k}). Theorem 2 (Erdős-Rényi, 1965) For all ϵ, δ > 0 , we have

Prḡ [max_{h∈G} |Qḡ(h) − \frac{1}{|G|}| < \frac{ϵ}{|G|}] > 1 − δ

for k > 2 log_{2} |G| + 2 log_{2} \frac{1}{ϵ} + log_{2} \frac{1}{δ} + 1. We first need the following lemma. Lemma 3

Eḡ [∑_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2}] = \frac{1}{2^{k}} (1 − \frac{1}{|G|}) .

Proof: (Lemma) From the usual formula for the variance E [(X − E[X])^{2}] = E[X^{2}] − E[X]^{2}, we first get that

Eḡ [∑_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2}] = Eḡ [∑_{h∈G} Qḡ(h)^{2}] − \frac{1}{|G|} ,

since

Eḡ[Qḡ(h)] = \frac{1}{|G|} ∀ h ∈ G .

The next step is to observe that for ḡ fixed in G^{k},

Qḡ(h) = \frac{1}{2^{k}} ∑_{ε̄:ḡε̄=h} 1 ,

Lecture 7: 24 September 2001 2 and thus that

∑_{h∈G} Qḡ(h)^{2} = \frac{1}{2^{2k}} ∑_{ε̄,ε̄′:ḡε̄=ḡε̄′} 1 ,

So when we let ḡ be variable again and take the expectation over G^{k}, we get

Eḡ [∑_{h∈G} Qḡ(h)^{2}] = \frac{1}{2^{2k}} ∑_{ε̄,ε̄′:\{0,1\}^{k}} Prḡ[g_{1}^{ε_{1}} ⋯ g_{k}^{ε_{k}} = g_{1}^{ε′_{1}} ⋯ g_{k}^{ε′_{k}}] .

The next observation is that

Prḡ[ḡε̄ = ḡε̄′] = \{ \begin{matrix}1 & if ε̄ = ε̄′ \\ \frac{1}{|G|} & otherwise. \end{matrix}

Hence

Eḡ [∑_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2}] = Eḡ [∑_{h∈G} Qḡ(h)^{2}] − \frac{1}{|G|}
= \frac{1}{2^{2k}} ∑_{ε̄,ε̄′∈\{0,1\}^{k}} Prḡ[ḡε̄ = ḡε̄′] − \frac{1}{|G|}
= \frac{1}{2^{2k}} (∑_{ε̄=ε̄′} 1 + ∑_{ε̄≠ε̄′} \frac{1}{|G|}) − \frac{1}{|G|}
= \frac{1}{2^{2k}} (2^{k} + (2^{2k} − 2^{k})\frac{1}{|G|}) − \frac{1}{|G|}
= \frac{1}{2^{k}} (1 − \frac{1}{|G|}) .

Proof: (Theorem) First observe that

max_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2} ≤ ∑_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2} .

Therefore

Prḡ [max_{h∈G} (Qḡ(h) − \frac{1}{|G|}) > \frac{ϵ}{|G|}] ≤ Prḡ [∑_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2} > \frac{ϵ^{2}}{|G|^{2}} ] .

If we let X = ∑_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2}, then Eḡ[X] = \frac{1}{2^{k}} (1 − \frac{1}{|G|}) by the previous lemma. We can then use Markov’s inequality Pr[X > λE[X]] < \frac{1}{λ} with X as above and λ = \frac{ϵ^{2}}{|G|^{2}E[X]} to get

Prḡ [max_{h∈G} (Qḡ(h) − \frac{1}{|G|}) > \frac{ϵ}{|G|}] ≤ Prḡ [∑_{h∈G} (Qḡ(h) − \frac{1}{|G|})^{2} > \frac{ϵ^{2}}{|G|^{2}} ] < \frac{|G|^{2}}{2^{k} (1 − \frac{1}{|G|}) ϵ^{2}} < \frac{|G|^{2}}{2^{k−1}ϵ^{2}} .

Lecture 7: 24 September 2001 3 In particular, this will be less than δ if

2^{k−1} > \frac{|G|^{2}}{δϵ^{2}} ,

or

k > 2 log_{2} |G| − 2 log_{2} ϵ − log_{2} δ + 1 .