Let X=(X1,X2,X3,…)\pmb X = (X_1, X_2, X_3, \ldots) be a countable sequence of independent Rademacher random variables. For each n∈N+n \in \mathbb{N}_+, denote Sn=∑i∈[n]XiS_n = \sum_{i \in [n] } X_i.

Weak Law of Large Numbers. ∀ϵ>0\forall \epsilon > 0, it holds that

lim⁡nPr⁡[∣1n⋅Sn∣≥ϵ]=0. \lim_{n } \Pr \left[ \left| \frac{1}{n} \cdot S_n \right| \ge \epsilon \right] = 0.

Proof. Via Hoeffding's inequality, we have

Pr⁡[∣1n⋅Sn∣≥ϵ]≤exp⁡(−n⋅ϵ22). \Pr \left[ \left| \frac{1}{n} \cdot S_n \right| \ge \epsilon \right] \le \exp \left( - \frac{n \cdot \epsilon^2 }{ 2 } \right).

Letting n→∞n \rightarrow \infty, the right hand side converges to 00.

□\square

Strong Law of Large Numbers. Let

A≐{x∈{−1,1}N:lim⁡n(1n∑i∈[n]xi)=0} A \doteq \left\{ \pmb x \in \{-1, 1\}^{ \mathbb{N} } : \lim_n \left( \frac{1}{n} \sum_{i \in [n] } x_i \right) = 0 \right\}

be the set consisting of those x\pmb x whose partial sums converges to 0. Then

Pr⁡[X∈A]=1. \Pr[ \pmb X \in A] = 1.

Proof. For each n≥2n \ge 2, let ϵn=2⋅(ln⁡n)/n\epsilon_n = 2 \cdot \sqrt{(\ln n) / n}, and define the set

Bn≐{x∈{−1,1}N:∣1n∑i∈[n]xi∣≥ϵn}. B_n \doteq \left\{ \pmb x \in \{-1, 1\}^{ \mathbb{N} } : \left| \frac{1}{n} \sum_{i \in [n] } x_i \right| \ge \epsilon_n \right\}.

Via Hoeffding's inequality, we see that

Pr⁡[X∈Bn]≤1n2. \Pr[ X \in B_n ] \le \frac{1}{n^2}.

Let Ck≐∪n≥kBkC_k \doteq \cup_{n \ge k} B_k. For each x∈Aˉ\pmb x \in \bar A, ∃ϵ>0\exists \epsilon > 0, s.t.,

x∈(∩k≥1∪n≥k{x∈{−1,1}N:∣1n∑i∈[n]xi∣≥ϵ})⊂(∩k≥2Ck). \pmb x \in \left( \cap_{k \ge 1} \cup_{n \ge k} \left\{ \pmb x \in \{-1, 1\}^{ \mathbb{N} } : \left| \frac{1}{n} \sum_{i \in [n] } x_i \right| \ge \epsilon \right\} \right) \subset \Big( \cap_{ k \ge 2 } C_k \Big).

It follows that Aˉ⊂(∩k≥2Ck)=lim⁡kCk\bar A \subset \Big( \cap_{k \ge 2} C_k \Big)= \lim_k C_k. Further, for each k≥2k \ge 2,

Pr⁡[X∈Ck]≤∑n≥kPr⁡[X∈Bn]≤1k. \Pr[ X \in C_k ] \le \sum_{n \ge k} \Pr[ X \in B_n] \le \frac{1}{k}.

Hence,

Pr⁡[X∈lim⁡kCk]=lim⁡kPr⁡[X∈Ck]=0. \Pr[ X \in \lim_k C_k ] = \lim_k \Pr [ X \in C_k ] = 0.

□\square