Lecture Notes 4 Convergence (Chapter 5) 1 Various Inequalities

1 Lecture Notes 4 Convergence ( chapter 5)1 Various InequalitiesInequalities are useful for bounding quantities that might otherwise be hard to will also be used in the theory of Convergence . Our first inequality is Markov s 1 (Markov s inequality)LetXbe a non-negative random variable and supposethatE(X)exists. For anyt >0,P(X > t) E(X) >0,E(X) = 0xf(x)dx= t0xf(x)dx+ txf(x)dx txf(x)dx t tf(x)dx=tP(X > t) Theorem 2 (Chebyshev s inequality)Let =E(X)and 2= Var(X). Then,P(|X | t) 2t2andP(|Z| k) 1k2whereZ= (X )/ . In particular,P(|Z|>2) 1/4andP(|Z|>3) 1 use Markov s inequality to conclude thatP(|X | t) =P(|X |2 t2) E(X )2t2= second part follows by settingt=k . Theorem 3 (Cauchy-Schwartz inequality)IfXandYhave finite variances thenE|XY| E(X2)E(Y2).(1)Recall that a functiongisconvexif for eachx,yand each [0,1],g( x+ (1 )y) g(x) + (1 )g(y).

2 Ifgis twice differentiable andg (x) 0 for allx, thengis convex. It can be shown that ifgis convex, thenglies above any line that touchesgat some point, called a tangent functiongisconcaveif gis convex. Examples of convex functions areg(x) =x2andg(x) =ex. Examples of concave functions areg(x) = x2andg(x) = 4 (Jensen s inequality)Ifgis convex, thenEg(X) g(EX).(2)Ifgis concave, thenEg(X) g(EX).(3) (x) =a+bxbe a line, tangent tog(x) at the pointE(X). Sincegisconvex, it lies above the lineL(x). So,Eg(X) EL(X) =E(a+bX) =a+bE(X) =L(E(X)) =g(EX). Example: From Jensen s inequality we see thatE(X2) (EX) : KL distance. Define the Kullback-Leibler distance between two densitiesfandgbyD(f,g) = f(x) log(f(x)g(x)) thatD(f,f) = 0. We will use Jensen to show thatD(f,g) 0. LetX f. Then D(f,g) =Elog(g(X)f(X)) logE(g(X)f(X))= log f(x)g(x)f(x)dx= log g(x)dx= log(1) = , D(f,g) 0 and henceD(f,g) Limit TheoremsSome Convergence properties are preserved under 5 LetXn,X,Yn,Ybe random variables.

3 (a) IfXnP XandYnP Y, thenXn+YnP X+Y.(b) IfXnqm XandYnqm Y, thenXn+Ynqm X+Y.(c) IfXnP XandYnP Y, thenXnYnP 6 LetXn,X,Yn,Ybe random variables.(d) IfXn XandYn c, thenXn+Yn X+c.(e) IfXn XandYn c, thenXnYn 7 LetXn,X,Yn,Ybe random variables. Letgbe a continuous function.(f ) IfXnP X, theng(Xn)P g(X).(g) IfXn X, theng(Xn) g(X). Parts (d) and (e) are know asSlutzky s theorem Parts (f) and (g) are known asThe Continuous Mapping Theorem. It is worth noting thatXn XandYn Ydoes not in general imply thatXn+Yn X+ The Law of Large NumbersThe LLN says that the mean of a large sample is close to the mean of the distribution. Forexample, the proportion of heads of a large number of tosses of a fair coin is expected to beclose to 1/2. We now make this more ,X2,..be aniidsample, let =E(X1) and 2= Var(X1). Recall that thesample mean is defined asXn=n 1 ni=1 Xiand thatE(Xn) = and Var(Xn) = 2 8 The Weak Law of Large Numbers (WLLN).

4 IfX1,..,Xnareiid, thenXnP . Thus,Xn =oP(1).Interpretation of the WLLN: The distribution ofXnbecomes more concentratedaround asngets that < . This is not necessary but it simplifies the proof. UsingChebyshev s inequality,P(|Xn |> ) Var(Xn) 2= 2n 2which tends to 0 asn . Theorem 9 The Strong Law of Large ,X2,..be aniidsample. Let =E(X1)andE(|X1|)< . We haveXnas .3We proved in class a version of the SLLN with independent random variables each withbounded fourth moment using the Borel-Cantelli 10 LetX1,X2,..be a sequence of independent random variables, each havingthe same finite meanm, each havingE(Xi m)4 < .ThenP{limn 1n(X1+X2+..+Xn) =m}= 11 LetZ1,..,Znbe random variables. Suppose that for each >0, we have n=1P{|Zn Z| }< .Then{Zn}converges almost surely Central Limit law of large numbers says that the distribution ofXnpiles up near.

5 This isn tenough to help us approximate probability statements aboutXn. For this we need thecentral limit thatX1,..,Xnareiidwith mean and variance 2. The central limit theorem(CLT) says thatXn=n 1 iXihas a distribution which is approximately Normal withmean and variance 2/n. This is remarkable since nothing is assumed about the distri-bution ofXi, except the existence of the mean and variance. For instance, the CLT applieseven ifXis a coin toss. Although a Bernoulli distribution is far from normal, the mean ofa sequence of Bernoulli experiments is normally distributed (for a large number of tosses).Theorem 12 (The Central Limit Theorem (CLT))LetX1,..,Xnbeiidwith mean and variance 2. LetXn=n 1 ni=1Xi. ThenZn Xn Var(Xn)= n(Xn ) ZwhereZ N(0,1). In other words,limn P(Zn z) = (z) = z 1 2 e x2 : Probability statements aboutXncan be approximated using a Nor-mal distribution.

6 It s the probability statements that we are approximating, not therandom variable addition toZn N(0,1), there are several forms of notation to denote the fact thatthe distribution ofZnis converging to a Normal. They all mean the same thing. Here theyare:Zn N(0,1)Xn N( , 2n)Xn N(0, 2n) n(Xn ) N(0, 2) n(Xn ) N(0,1).Recall that ifXis a random variable, its moment generating function (mgf) is X(t) =EetX. Assume in what follows that themgfis finite in a neighborhood aroundt= 13 LetZ1,Z2,..be a sequence of random variables. Let nbe themgfofZn. LetZbe another random variable and denote itsmgfby . If n(t) (t)for alltin someopen interval around 0, thenZn n th moment:E(Xn) Central moments:E((X )n).Proof of the central limit (Xi )/ .Then,Zn=n 1/2 (t) be themgfofYi. Themgfof iYiis ( (t))nandmgfofZnis [ (t/ n)]n n(t). Now (0) =E(Y1) = 0 (0) =E(Y21) = Var(Y1) = , (t) = (0) +t (0) +t22!

7 (0) +t33! (0) + = 1 + 0 +t22+t33! (0) + = 1 +t22+t33! (0) + Now, n(t) =[ (t n)]n=[1 +t22n+t33!n3/2 (0) + ]n=[1 +t22+t33!n1/2 (0) + n]n et2/2which is themgfof a N(0,1). The result follows from the previous Theorem. In the laststep we used the fact that ifan athen(1 +ann)n ea. The central limit theorem tells us thatZn= n(Xn )/ is approximately N(0,1).However, we rarely know . Later, we will see that we can estimate 2fromX1,..,XnbyS2n=1n 1n i=1(Xi Xn) raises the following question: if we replace withSn, is the central limit theorem stilltrue? The answer is 14 Assume the same conditions as the CLT. Then,Tn= n(Xn )Sn N(0,1). have thatTn=ZnWnwhereZn= n(Xn ) andWn= N(0,1) andWnP 1. The result follows from Slutzky s detailed derivation onWnP 1 is given on board. There is also a multivariate version of the central limit 15 (Multivariate central limit theorem)LetX1.

8 ,Xnbeiidrandom vec-tors whereXi= with mean = 1 k = E(X1i)E(X2i)..E(Xki) and variance matrix . LetX= whereXj=n 1 ni=1 Xji. Then, n(X ) N(0, ).Exercises:Show thatE(X )(X )T= .4 The Delta MethodIfYnhas a limiting Normal distribution then the delta method allows us to find the limitingdistribution ofg(Yn) wheregis any smooth 16 (The Delta Method)(CB Theorem ) Suppose that n(Yn ) N(0,1)and thatgis a differentiable function such thatg ( )6= 0. Then n(g(Yn) g( ))|g ( )| N(0,1).In other words,Yn N( , 2n)implies thatg(Yn) N(g( ),(g ( ))2 2n).7 There is also a multivariate version of the delta 17 (The Multivariate Delta Method)Suppose thatYn= (Yn1,..,Ynk)is asequence of random vectors such that n(Yn ) N(0, ).Letg:Rk Rand let g(y) = g g yk .Let denote g(y)evaluated aty= and assume that the elements of are n(g(Yn) g( )) N(0, T ).Example 18 Let(X11X21),(X12X22).

9 ,(X1nX2n)beiidrandom vectors with mean = ( 1, 2)Tand variance . LetX1=1nn i=1X1i,X2=1nn i=1X2iand defineYn=X1X2. Thus,Yn=g(X1,X2)whereg(s1,s2) =s1s2. By the central limittheorem, n(X1 1X2 2) N(0, ).Now g(s) =( g s1 g s2)=(s2s1)and so T = ( 2 1)( 11 12 12 22)( 2 1)= 22 11+ 2 1 2 12+ 21 , n(X1X2 1 2) N(0, 22 11+ 2 1 2 12+ 21 22). 85 Monotone Convergence theoremA sequence of random variables{Xn} XifX1 X2 .., and also limn Xn( ) =X( ) for each . That is, the sequence{Xn}converges monotonically 19(The monotone Convergence theorem.) SupposeX1,X2,..,are random vari-ables withE(X1)> , and{Xn} X. ThenXis a random variable, andlimn E(Xn) =E(X). expected values are unchanged if we modify the random variable values onsets of probability 0, we still have limn E(Xn) =E(X) provided{Xn} Xalmost surely, , on a subset of having probability 1. Recall if{Xn}is a sequence of random variables,then limn Xnexists means that there exists an eventN B, such thatP(N) = 0and if Ncthenlimn Xnexists.

10 It also means that for ,lim supn Xn( ) = lim infn Xn( ).We will write limn Xn=X X, orXn X 20 IfXis a non-negative random variable, then k=1P(X k) =EbXc,wherebXcis the greatest integer not exceedingX. In particular, ifXis non-negative-integervalued, then k=1P(X k) =E(X).9