Lecture Notes 4 Convergence (Chapter 5) 1 Random Samples

1 Lecture Notes 436-705In today s Lecture we discuss the Convergence of Random variables. At a high-level, ourfirst few lectures focused on non-asymptotic properties of averages the tail bounds wederived applied for any fixed sample sizen. For the next few lectures we focus on asymptoticproperties, we ask the question: what happens to the average Random variablesasn .Roughly, from a theoretical perspective the idea is that many expressions will consider-ably simplify in the asymptotic regime. Rather than have many different tail bounds, wewill derive simple universal results that hold under extremely weak conditions. From aslightly more practical perspective, asymptotic theory is often useful to obtain approximateconfidence Reminder: Convergence of sequencesWhen we think of Convergence of deterministic real numbers the corresponding notions , we say that a sequence of real numbersa1,a2.

2 Converges to a fixed real numberaif, for every positive number , there exists a natural numberN( ) such that for alln N( ),|an a|< . We callathe limit of the sequence and write limn an= focus today will in trying to develop analogues of this notion that apply to sequencesof Random variables. We will first give some definitions and then try to circle back to relatethe definitions and discuss some , we will focus on the setting where we have a sequence of Random variablesX1,..,Xnand another Random variableX, and would like to define what is means for thesequence to converge toX. In each case, to simplify things you should also think about thecase whenXis deterministic, whenX=cwith probability 1 (for some constantc).

3 Importantly, we willnot assume that the RVsX1,..,Xnare Almost sure convergenceWe will not use almost sure Convergence in this course so you should feel free to ignore thissection. A natural analogue of the usual Convergence would be to hope that,limn Xn= X. These are both however Random variables so one has to at least specifyon what event we are hoping for this statement to be correct analogue turns out to be to require:P(limn Xn=X)= are measure theoretic subtleties to be aware of here. In particular, the sample space in-side the probability statement here is set of infinite sequences and it requires some machineryto be precise are other equivalent (this is somewhat difficult to see) ways to define almost sureconvergence.

4 Equivalently, we say thatXnconverges almost surely toXif we let be a setof probability mass 1, ( ) = 1, and for every , and for every >0, we have thatthere is somen N( , ) such that:|Xn( ) X( )| .Roughly, the way to think about this type of Convergence is to imagine that there is someset of exceptional events on which the Random variables can disagree, but these exceptionalevents have probability 0 asn . Barring, these exceptional events the sequence con-verges just like sequences of real numbers do. The exceptional events is where the almost in almost sure Convergence in probabilityA sequence of Random variablesX1,..,Xnconverges in probability to a Random variableXif for every >0 we have that,limn P(|Xn X| ) = writeXnP X.

5 To build intuition it is perhaps useful to consider the case whenXisdeterministic, probability 1. Then Convergence in probability is saying thatasngets large the distribution ofXngets more peaked around the valuec. Convergencein probability can be viewed as a statement about the Convergence of probabilities, whilealmost sure Convergence is a Convergence of the values of a sequence of Random will not prove this statement but Convergence in probability is implied by almost sureconvergence. The Notes contain a counterexample to the reverse implication which we mayor may not cover in the Law of Large NumbersSuppose thatY1,Y2,..are withE[Yi] = andVar(Yi) = 2< . Define,Xn=1nn j= WLLN says that the sequenceX1,X2.

6 Converges in probability to . That isXnP .Proof:The proof is simply an application of Chebyshev s inequality. We note that byChebyshev s inequality:P(|Xn E[X]| ) 2n in turn implies that,limn P(|Xn E[X]| ) = 0,as :1. Strictly speaking the WLLN is true even without the assumption of finite variance, aslong as the first absolute moment is finite. This proof is a bit more There is a statement that says that under similar assumptions the average convergesalmost surely to the expectation. This is known as the strong law of large is actually quite a bit more difficult to : Convergence in probability will frequently recur in this course. Usually wewill construct an estimator nfor some quantity.

7 We will then say that the estimator isconsistentif the sequence of RVs nconverges in probability to .The WLLN/Chebyshev can already be used to prove some rudimentary consistency guaran-tees. For instance, if we consider the sample variance: Sn=1n 1n i=1(Xi n)2,then by Chebyshev s inequality we obtain,P(| Sn 2| ) Var( Sn) 2,so a sufficient condition for consistency is that Var( Sn) 0 asn .3 Convergence in probability does not imply almost sure Convergence :Supposewe have a sample spaceS= [0,1], with the uniform distribution, we draws U[0,1] anddefineX(s) =s. We define the sequence as:X1(s) =s+I[0,1](s), X2(s) =s+I[0,1/2](s), X3(s) =s+I[1/2,1](s)X4(s) =s+I[0,1/3](s), X5(s) =s+I[1/3,2/3](s), X6(s) =s+I[2/3,1](s).

8 Now one can check that this sequence converges in probability but not almost , the 1 + s spike becomes less frequent down the sequence (allowing convergencein probability) but the limit is not well defined. For anys,Xn(s) alternates betweensand1 + Convergence in quadratic meanAn often useful way to show Convergence in probability is to show something stronger knownas Convergence in quadratic mean. We say that a sequence converges toXin quadratic meanif:E(Xn X)2 0,asn . We writeXnqm Convergence in distributionThe other commonly encountered mode of Convergence is Convergence in distribution. Wesay that a sequence converges toXin distribution if:limn FXn(t) =FX(t),for all pointstwhere the CDFFXis continuous.

9 We will see why the exception matters ina little while but for now it is worth noting that Convergence in distribution is the weakestform of Convergence . We writeXn instance, a sequence of (0,1) RVs converge in distribution to an independentN(0,1) RV, even though the values of the Random variables are not close in any meaningfulsense (their distributions are however, identical). A famous result that we will disucss in thenext Lecture is the central limit theorem. The central limit theorem says that an averageof Random variables (appropriately normalized) converges in distribution to aN(0,1) Random picture to keep in mind to understand the relationships is the following one:4We will re-visit this in the next Lecture and perhaps try to prove some of the implications(or disprove some of the non-implications).

10 6 ExamplesExample 1:Suppose we consider a sequenceXn=N(0,1/n).Intuitively, it seems likethis sequence converges to 0. Let us first consider what happens in such thatP(X= 0) = 1. The CDF isFX(x) = 0,forx <0 andFX(x) = 1 forx 0. Note thatXnd=Z/nwhereZ N(0,1). So,FXn(x) =P(Xn x) =P(Z nx),whereZ N(0,1). Ifx >0 this tends to 1, and ifx <0 this tends to 0. Interestingly, atx= 0,FXn(x) = 1/2, and does not converge toFX(0) = 1. Remember, however, that wehad an exception at points of discontinuity. SoXn 2:Let us consider the same example and consider Convergence in (|Xn X| ) =E[X2n] 2=1n 2 0,so the sequence converges to 0 in 3:SupposeX1,.. U[0,1]. Let us defineX(n)= max1 i , we verifytwo (n)converges in probability to 1.