Notes 4 : Laws of large numbers - Department of Mathematics

Notes 4 : Laws of large numbers

Math 733-734: Theory of Probability

Lecturer: Sebastien Roch

References: [Fel71, Sections V.5, VII.7], [Dur10, Sections 2.2-2.4].

1 Easy laws

Let X1, X2, . . . be a sequence of RVs. Throughout we let Sn = kn 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[XiXj] = E[Xi]E[Xj] for i = j, with E[Xi] = ? < + and Var[Xi] C < +. Then n-1Sn L2 ? and, as a result, n-1Sn P ?.

Proof: Note that

Var[Sn] = E[(Sn - E[Sn])2] = E

2 (Xi - E[Xi])

i

=

E[(Xi - E[Xi])(Xj - E[Xj])] = Var[Xi],

i,j

i

since, for i = j,

E[(Xi - E[Xi])(Xj - E[Xj])] = E[XiXj] - E[Xi]E[Xj] = 0.

Hence

Var[n-1Sn] n-2(nC) n-1C 0,

that is, n-1Sn L2 ?, and the convergence in probability follows from Chebyshev.

With a stronger assumption, we get an easy strong law. THM 4.2 (Strong Law in L4) If the Xis are IID with E[Xi4] < + and E[Xi] = ?, then n-1Sn ? a.s.

1

Lecture 4: Laws of large numbers

2

Proof: Assume w.l.o.g. that ? = 0. (Otherwise translate all Xis by ?.) Then

E[Sn4] = E XiXjXkXl = nE[X14] + 3n(n - 1)(E[X12])2 = O(n2),

i,j,k,l

where we used that E[Xi3Xj] = 0 by independence and the fact that ? = 0. (Note that E[X12] 1 + E[X14].) Markov's inequality then implies that for all > 0

P[|Sn|

>

n]

E[Sn4 ] n44

=

O(n-2),

which is summable, and (BC1) concludes the proof.

The law of large numbers has interesting implications, for instance:

EX 4.3 (A high-dimensional cube is almost the boundary of a ball) Let X1, X2, . . . be IID uniform on (-1, 1). Let Yi = Xi2 and note that E[Yi] = 1/3, Var[Yi] E[Yi2] 1, and E[Yi4] 1 < +. Then

X12

+ ? ? ? + Xn2

1 ,

n

3

both in probability and almost surely. In particular, this implies for > 0

P (1 - )

n <

3

X(n) 2 < (1 + )

n 1,

3

where X(n) = (X1, . . . , Xn). I.e., most of the cube is close to the boundary of a ball of radius n/3.

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 sufficient condition for the existence of constants (?n)n such that

Sn n

- ?n

P

0,

is n P[|X1| > n] 0.

In that case, the choice

?n = E[X11|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 n

P

E[X1].

Proof: From (DOM)

nP[|X1| > n] E[|X1 1| |X1|>n] 0,

and

?n = E[X11|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

E[Y p] = pyp-1P[Y > y]dy.

0

EX 4.7 Let X e be such that, for some 0,

1 P[X > x] = x(log x) , x e.

(There is a jump at e. The choice of e makes it clear that the tail stays under 1.) Then

E[X2] = e2 +

+

1

e 2x x(log x) dx 2

+ 1 e (log x) dx = +,

0.

(Indeed, it decays slower than 1/x which diverges.) So the L2 weak law does not apply. On the other hand,

+

1

+ 1

E[X] = e +

e

x(log x) dx = e + 1

u du.

This is + if 0 1. But for > 1

Finally,

u-+1 +

1

E[X] = e + - + 1 1

=e+

.

-1

1 nP[X > n] = (log n) 0, > 0.

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)

n

?n = E[X1Xn] = e +

e

1

1

-

x log x n log n

dx log log n.

Note, in particular, that ?n may not have a limit.

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)kn be inde-

pendent. Let bn with bn + and let Xn,k = 1 Xn,k |Xn,k|bn. Suppose that

1.

n k=1

P[|Xn,k |

>

bn]

0.

2. b-n 2

n k=1

Var[Xn,k ]

0.

If we let Sn =

n k=1

Xn,k

and

an

=

n k=1

E[Xn,k

]

then

Proof: Let Sn =

Sn - an bn

P

0.

n k=1

Xn,k .

Clearly

P

Sn - an bn

>

P[Sn = Sn] + P

Sn - an > . bn

For the first term, by a union bound

n

P[Sn = Sn] P[|Xn,k| > bn] 0.

k=1

For the second term, we use Chebyshev's inequality:

P

Sn - an bn

>

Var[Sn] 2b2n

=

1 2b2n

n

Var[Xn,k ]

k=1

0.

Lecture 4: Laws of large numbers

5

Proof: (of sufficiency in Theorem 4.4) We apply Theorem 4.4 with bn = n. Note that an = n?n. Moreover,

n-1Var[Xn,1] n-1E[(Xn,1)2]

= n-1

2yP[|Xn,1| > y]dy

0

n

= n-1 2y[P[|Xn,1| > y] - P[|Xn,1| > n]]dy

0

1n

2

n

yP[|X1| > y]dy

0

0,

since we are "averaging" a function going to 0. Details in [D]. The other direction is proved in the appendix.

3 Strong laws

Recall: DEF 4.9 (Tail -algebra) Let X1, X2, . . . be RVs on (, F , P). Define

Tn = (Xn+1, Xn+2, . . .), T = Tn.

n1

By a previous lemma, T is a -algebra. It is called the tail -algebra of the sequence (Xn)n.

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.

EX 4.11 Let X1, X2, . . . be independent. Then

lim sup n-1Sn

n

and

lim inf

n

n-1Sn

are almost surely a constant.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download