Gradprob Notes4
Gradprob Notes4
Gradprob Notes4
1 Easy laws
P
Let X1 , X2 , . . . be a sequence of RVs. Throughout we let Sn = k≤n Xk .
We begin with a straighforward application of Chebyshev’s inequality.
THM 4.1 (L2 weak law of large numbers) Let X1 , X2 , . . . be uncorrelated RVs,
i.e., E[Xi Xj ] = E[Xi ]E[Xj ] for i 6= j, with E[Xi ] = µ < +∞ and Var[Xi ] ≤
C < +∞. Then n−1 Sn →L2 µ and, as a result, n−1 Sn →P µ.
since, for i 6= j,
Hence
Var[n−1 Sn ] ≤ n−2 (nC) ≤ n−1 C → 0,
that is, n−1 Sn →L2 µ, and the convergence in probability follows from Chebyshev.
THM 4.2 (Strong Law in L4 ) If the Xi s are IID with E[Xi4 ] < +∞ and E[Xi ] =
µ, then n−1 Sn → µ a.s.
1
Lecture 4: Laws of large numbers 2
where we used that E[Xi3 Xj ] = 0 by independence and the fact that µ = 0. (Note
that E[X12 ] ≤ 1 + E[X14 ].) Markov’s inequality then implies that for all ε > 0
E[Sn4 ]
P[|Sn | > nε] ≤ = O(n−2 ),
n 4 ε4
which is summable, and (BC1) concludes the proof.
2 Weak laws
In the case of IID sequences we get the following.
THM 4.4 (Weak law of large numbers) Let (Xn )n be IID. A necessary and suf-
ficient condition for the existence of constants (µn )n such that
Sn
− µn →P 0,
n
is
n P[|X1 | > n] → 0.
In that case, the choice
µn = E[X1 1|X1 |≤n ],
works.
Lecture 4: Laws of large numbers 3
COR 4.5 (L1 weak law) If (Xn )n are IID with E|X1 | < +∞, then
Sn
→P E[X1 ].
n
Proof: From (DOM)
and
µn = E[X1 1|X1 |≤n ] → E[X1 ].
Before proving the theorem, we give an example showing that the condition in
Theorem 4.4 does not imply the existence of a first moment. We need the following
important lemma which follows from Fubini’s theorem. (Exercise.)
LEM 4.6 If Y ≥ 0 and p > 0, then
Z ∞
E[Y p ] = py p−1 P[Y > y]dy.
0
(Indeed, it decays slower than 1/x which diverges.) So the L2 weak law does not
apply. On the other hand,
Z +∞ Z +∞
1 1
E[X] = e + α
dx = e + α
du.
e x(log x) 1 u
This is +∞ if 0 ≤ α ≤ 1. But for α > 1
+∞
u−α+1 1
E[X] = e + =e+ .
−α + 1 1
α−1
Finally,
1
nP[X > n] = → 0, ∀α > 0.
(log n)α
Lecture 4: Laws of large numbers 4
(In particular, the WLLN does not apply for α = 0.) Also, we can compute µn in
Theorem 4.4. For α = 1, note that (by the change of variables above)
Z n
1 1
µn = E[X 1X≤n ] = e + − dx ∼ log log n.
e x log x n log n
2.1 Truncation
To prove sufficiency, we use truncation. In particular, we give a weak law for
triangular arrays which does not require a second moment—a result of independent
interest.
THM 4.8 (Weak law for triangular arrays) For each n, let (Xn,k )k≤n be inde-
0
pendent. Let bn with bn → +∞ and let Xn,k = Xn,k 1|Xn,k |≤bn . Suppose that
Pn
1. k=1 P[|Xn,k | > bn ] → 0.
Pn
2. b−2
n
0
k=1 Var[Xn,k ] → 0.
Sn − an
→P 0.
bn
Pn
Proof: Let Sn0 = 0
k=1 Xn,k . Clearly
0
Sn − an 0
Sn − an
P
> ε ≤ P[Sn 6= Sn ] + P
>ε .
bn bn
Proof: (of sufficiency in Theorem 4.4) We apply Theorem 4.4 with bn = n. Note
that an = nµn . Moreover,
n−1 Var[Xn,1
0
] ≤ n−1 E[(Xn,1
0
)2 ]
Z ∞
= n−1 0
2yP[|Xn,1 | > y]dy
0
Z n
= n−1 2y[P[|Xn,1 | > y] − P[|Xn,1 | > n]]dy
0
Z n
1
≤2 yP[|X1 | > y]dy
n 0
→ 0,
3 Strong laws
Recall:
THM 4.10 (Kolmogorov’s 0-1 law) Let (Xn )n be a sequence of independent RVs
with tail σ-algebra T . Then T is P-trivial, i.e., for all A ∈ T we have P[A] = 0
or 1. In particular, if Z ∈ mT then there is z ∈ [−∞, +∞] such that
P[Z = z] = 1.
Sn
→ µ, a.s.
n
If instead E|X1 | = +∞ then
Sn
P lim exists ∈ (−∞, +∞) = 0.
n n
Proof: For the converse, assume E|X1 | = +∞. From Lemma 4.6
+∞
X
+∞ = E|X1 | ≤ P[|X1 | > n].
n=0
By (BC2)
P[|Xn | > n i.o.] = 1.
Because
Sn Sn+1 (n + 1)Sn − nSn+1 Sn − nXn+1 Sn Xn+1
− = = = − ,
n n+1 n(n + 1) n(n + 1) n(n + 1) n + 1
we get that
where the next to last line follows from the sum of a geometric series and the
last line follows from the next lemma—proved later:
Tk(n)
→ µ, a.s.
k(n)
Tk(n) Tm Tk(n+1)
≤ ≤ ,
k(n + 1) m k(n)
1 Tm Tm
E[X1 ] ≤ lim inf ≤ lim sup ≤ αE[X1 ].
α m m m m
Lecture 4: Laws of large numbers 8
Since α > 1 is arbitrary, we are done. But it remains to prove the lemma:
Proof: By Fubini’s theorem
+∞ +∞
X Var[Yi ] X E[Y 2 ] i
≤
i2 i2
i=1 i=1
+∞ Z ∞
X 1
= 2yP[|Yi | > y]dy
i2 0
i=1
+∞ Z ∞
1
1{y≤i} 2yP[|Yi | > y]dy
X
=
i2 0
i=1
+∞
!
Z ∞
1
1
X
= 2y P[|Yi | > y]dy
0 i2 {y≤i}
i=1
Z ∞
≤ C 0 P[|Yi | > y]dy
0
0
≤ C E|X1 |,
Sn SM
lim inf ≥ lim inf n = E[XiM ] ↑ +∞,
n n n n
as M → +∞ by (MON) applied to the positive part.
3.2 Applications
An important application of the SLLN:
THM 4.15 (Glivenko-Cantelli) Let (Xn )n be IID and, for x ∈ R,
1X
Fn (x) = 1{Xk ≤ x},
n
k≤n
Lecture 4: Laws of large numbers 9
Proof: Pointwise convergence follows immediately from the SLLN. Uniform con-
vergence then follows from the boundedness and monotonicity of F and Fn . See
[D] for details.
References
[Dur10] Rick Durrett. Probability: theory and examples. Cambridge Series in
Statistical and Probabilistic Mathematics. Cambridge University Press,
Cambridge, 2010.
A Symmetrization
To prove the other direction of the weak law, we use symmetrization.
DEF 4.16 Let X ∼ F . We say that X is symmetric if X and −X have the same
distribution function, that is, if at points of continuity we have F (x) = 1 − F (−x)
for all x.
Proof: For the first one, at least one of |X1 | > t/2 or |X̃1 | > t/2 must be satisfied.
For the second one, the following are enough
LEM 4.19 Let {Yk }k≤n be independent and symmetric with Sn = nk=1 Yk and
P
Mn equal to the first term among {Yk }k≤n with greatest absolute value. Then
1
P[|Sn | ≥ t] ≥ P [|Mn | ≥ t] . (3)
2
Moreover, if the Yk ’s have a common distribution F then
1
P[|Sn | ≥ t] ≥ (1 − exp(−n[1 − F (t) + F (−t)])) . (4)
2
Proof: We start with the second one. Note that
By symmetry, the four combinations (±Mn , ±(Sn − Mn )) have the same distribu-
tion. Indeed Mn and Sn − Mn are not independent but their sign is because Mn is
defined by its absolute value and Sn − Mn is the sum of the other variables. Hence,
and the two terms on the RHS are equal. Plugging this back into (5), we are done.
Note that X
Sn◦ = (Sn − nµn )◦ = Xk◦ .
k≤n
Lecture 4: Laws of large numbers 11
for ε small enough and n large enough. Since the LHS goes to 0, we are done.
B St-Petersburg paradox
EX 4.20 (St-Petersburg paradox) Consider an IID sequence with
P X1 = 2j = 2−j , ∀j ≥ 1.
(indeed it is a geometric series and the sum is dominated by the first term) and
therefore we cannot apply the WLLN. Instead we apply the WLLN for triangular
arrays to a properly normalized sum. We take Xn,k = Xk and bn = n log2 n. We
check the two conditions. First
n
X n
P[|Xn,k | > bn ] = Θ → 0.
n log2 n
k=1
0
To check the second one, let Xn,k = Xn,k 1|Xn,k |≤bn and note
So
n
1 X 0 2 2n2 log2 n
E[(Xn,k ) ] = → 0.
b2n n2 (log2 n)2
k=1
Lecture 4: Laws of large numbers 12
Finally,
so that
Sn − an
→P 0,
bn
and
Sn
→P 1.
n log2 n
P
THM 4.21 Let (Xn )n be IID with E|X1 | = +∞ and Sn = k≤n Xk . Let an be
a sequence
P with an /n increasing. Then lim supn |Sn |/an = 0 or + ∞ according
as n P[|X1 | ≥ an ] < +∞ or = +∞.