Definition D1
Let X₁, X₂, … be mutually independent, identically distributed random variables with E(Xᵢ) = μ and Var(Xᵢ) = σ² < ∞. Define the sample mean X̄ₙ = (X₁ + … + Xₙ)/n.
Proof.
(1)The indicator 1_A of an event A is the random variable equal to 1 on A and 0 outside A.convention
(2)μ and σ² are the same for every Xᵢ.convention
∎
Definition D2
The variance of a random variable Y is Var(Y) = E((Y − E(Y))²).
Proof.
The deviation from the expectation is squared and the expectation is taken again.convention
∎
Lemma L1
If X ≥ 0 and a > 0, then P(X ≥ a) ≤ E(X)/a
Proof.
(1)Suppose X ≥ 0, a > 0, and set A = {X ≥ a}.assumption
(2)On A, a·1_A = a ≤ X; outside A, a·1_A = 0 ≤ X. Therefore a·1_A ≤ X(1), D1
(3)E(a·1_A) ≤ E(X)(2), A3
(4)E(a·1_A) = a E(1_A) = a P(X ≥ a)(1), A2, A4
(5)a P(X ≥ a) ≤ E(X)(3), (4), E
(6)a > 0, so divide both sides by a. P(X ≥ a) ≤ E(X)/a(1), (5), A8
∎
Lemma L2
If m = E(Y) and ε > 0, then P(|Y − m| ≥ ε) ≤ Var(Y)/ε²
Proof.
(1)Suppose ε > 0. (Y − m)² is non-negative, and ε² is positive.assumption, A6, N
(2)The event {|Y − m| ≥ ε} and the event {(Y − m)² ≥ ε²} are the same event.(1), A7
(3)Apply L1 with X = (Y − m)², a = ε². P((Y−m)² ≥ ε²) ≤ E((Y−m)²)/ε²(1), L1
(4)E((Y − m)²) = Var(Y)D2
(5)P(|Y − m| ≥ ε) ≤ Var(Y)/ε²(2), (3), (4), E
∎
(1)E(X₁ + … + Xₙ) = E(X₁) + … + E(Xₙ) = nμA1, D1
(2)E(X̄ₙ) = (1/n) · nμ = μ(1), A2, D1, N
∎
Lemma L4
Var(X̄ₙ) = σ²/n
Proof.
(1)X₁, …, Xₙ are mutually independent, so Var(X₁ + … + Xₙ) = Var(X₁) + … + Var(Xₙ) = nσ²A5, D1
(2)Var(cY) = E((cY − cE(Y))²) = c² E((Y − E(Y))²) = c² Var(Y)D2, A2, N
(3)Var(X̄ₙ) = (1/n²) · nσ² = σ²/n(1), (2), D1, N
∎
Theorem T1
For arbitrary ε > 0, P(|X̄ₙ − μ| ≥ ε) ≤ σ²/(nε²), and as n grows this probability converges to 0.
Proof.
(1)Suppose ε > 0.assumption
(2)E(X̄ₙ) = μ, so apply Chebyshev with Y = X̄ₙ. P(|X̄ₙ − μ| ≥ ε) ≤ Var(X̄ₙ)/ε²(1), L3, L2
(3)Var(X̄ₙ)/ε² = σ²/(nε²)(2), L4, N
(4)For arbitrary δ > 0, since σ²/ε² > 0, there is an n with σ²/(nε²) < δ, and the inequality holds for every larger n as well.A9, N
(5)Therefore, as n → ∞, P(|X̄ₙ − μ| ≥ ε) → 0. This is the definition of converging to 0.(3), (4), convention
∎
Corollary C
The precise meaning of 'approaches' is convergence in probability.
Proof.
(1)What T1 says is that for arbitrary ε, the probability of deviating goes to 0. It does not say that the average of every sequence of trials goes to μ.T1
(2)For a fair coin scored heads 1 and tails 0, μ = 1/2 and σ² = 1/4.convention, N
(3)With n = 100, ε = 0.1, the bound is (1/4)/(100 × 0.01) = 1/4(2), T1, N
(4)1/4 is a weak bound. But as n grows, the bound approaches 0 at the rate 1/n.(3), T1, N
∎