9 Convergence in probability - University of California, Davis

1 9 Convergence IN PROBABILITY1119 Convergence in probabilityThe idea is to extricate a simple deterministic component out of a random situation. This istypically possible when a large number of random effects cancel each other out, so some limitis involved. The general situation, then, is the following:given a sequence of random variables,Y1, Y2, .., we want to show that, whennis large,Ynis approximatelyf(n) for some simpledeterministic functionf(n). The meaning of approximately is what we now make sequence,Y1, Y2, .., of random variables converges to a numberain probabilityif, asn ,P(|Yn a| ) converges to 1, for any fixed >0. This is equivalent toP(|Yn a|> ) 0 asn , again for any fixed > a fair coinntimes, independently.

2 LetRnbe the longest run of heads, , the longest sequence of consecutive tosses of Heads. For example, ifn= 15 and the tossescome 3. We will show that, asn ,Rnlog2n 1,in probability . This means that, to a first approximation, one should expect about 20 consecutiveheads somewhere in a million solve a problem such as this, we need to find upper bounds on probabilities thatRnislarge and that it is small, , onP(Rn k) andP(Rn k), for appropriately chosenk. Now,for arbitraryk,P(Rn k) =P(kconsecutive Heads start at somei, 0 i n k+ 1)=P(n k+1 i=1{iis the first Heads in a succession of at leastkHeads}) n 12kFor the lower bound, divide the string of sizeninto disjoint blocks of sizek.

3 There is nk such blocks (ifnis not divisible byk, simply throw away the leftover smaller block at the end).ThenRn kas soon as one of the blocks consists of Heads only, and different blocks areindependendent. Therefore,P(Rn< k) (1 12k) nk exp( 12k nk ),9 Convergence IN PROBABILITY112using the famous inequality 1 x e x, valid for , we will use these trivial inequalities, valid for anyreal numberx 2: x x 1, x x+ 1,x 1 x2, andx+ 1 demonstrate thatRnlog2n 1,in probability , we need to show that, for any >0,P(Rn (1 + ) log2n) 0,(1)P(Rn (1 ) log2n) 0,(2)asP( Rnlog2n 1 )=P(Rnlog2n 1 + orRnlog2n 1 )=P(Rnlog2n 1 + )+P(Rnlog2n 1 )=P(Rn (1 + ) log2n) +P(Rn (1 ) log2n).

4 A little bit of fussing in the proof comes from the fact that (1 e) log2nare not integers. Thiscommon in problems such as this. To prove (1), we plugk= (1 + ) log2n into the upperbound to getP(Rn (1 + ) log2n) n 12(1+ ) log2n 1=n 2n1+ =2n 0asn . One the other hand, to prove (2) we need to plugk= (1 ) log2n + 1 into thelower bound,P(Rn (1 ) log2n) P(Rn< k) exp( 12k nk ) exp( 12k(nk 1)) exp( 132 1n1 n(1 ) log2n)= exp( 132n (1 ) log2n) 0,asn , asn is much larger than Convergence IN PROBABILITY113 The most basic tool in proving Convergence in probability isChebyshev s inequality: ifXisa random variable withEX= and Var(X) = 2, thenP(|X | k) 2k2,for anyk >0.

5 We proved this inequality in the previous chapter, and we will use it to prove thenext between variance and Convergence in thatYnare random variables andais a constant such thatEYn a,Var(Yn) 0,asn . ThenYn a,asn , in an >0. Ifnis so large that|EYn a|< /2,thenP(|Yn a|> ) P(|Yn EYn|> /2) 4 Var(Yn) 2 0,asn . Note that the second inequality in the computation is Chebyshev s is most often applied to sums of random variables. LetSn=X1+..+Xn,whereXiare random variables with finite expectation and variance. Then,without any inde-pendence assumption,ESn=EX1+..+EXnandE(S2n) =n i=1EX2i+ i6=jE(XiXj),Var(Sn) =n i=1 Var(Xi) + i6=jCov(Xi, Xj).9 Convergence IN PROBABILITY114 You should recall thatCov(X1, Xj) =E(XiXj) EXiEXjandVar(aX) =a2 Var(X).

6 Moreover, ifXiare independent,Var(X1+..+Xn) = Var(X1) +..+ Var(Xn).Continuing with the review, let s reformulate and reprove the most famous Convergence in prob-ability theorem. We will use the common abbreviation i. i. independent identically dis-tributed random law of large numbers. LetX, X1, X2, ..be i. i. d. random variables withwithEX1= andVar(X1) = 2< . LetSn=X1+..+Xn. Then, asn ,Snn in We haveEYn= , andVar(Yn) =1n2 Var(Sn) =1n2n 2= we can simply apply the previous analyze a typical investment (the accepted euphemism for gambling onfinancial markets) problem. Assume you have two investment choices at the beginning of eachyear: a risk-free bond which returns 6% per year; and a risky stock which increases your investment by 50% with probability and wipes itaway with probability an amountsin the bond, then, gives you a year.

7 The same amount in thestock gives you probability and 0 with probabiliy ; note that theexpected valueis > We will assume year-to-year independence of the stock s will try to maximize the return to our investment by hedging. That is, we invest, atthe beginning of each year, a fixed proportionxof our current capital into the stock and theremaining proportion 1 xinto the bond. We collect the resulting capital at the end of theyear, which is simultaneously the beginning of next year, and reinvest with the same proportionx. Assume that our initial capital Convergence IN PROBABILITY115It is important to note that theexpected valueof the capital at the end of the year ismaximized whenx= 1, but using this strategy you will eventuallylose everything.

8 LetXnbeyour capital at the end of yearn. Define theaverage growth rateof your investment as = limn 1nlogXnx0,so thatXn x0e will express in terms ofx; in particular, we will show it is a nonrandom {stock goes up in yeari}. These are independent indicators withEIi= 1(1 x) +Xn 1 x In=Xn 1( (1 x) + In)and so we can unroll the recurrence to getXn=x0( (1 x) + )Sn((1 x) )n Sn,whereSn=I1+..+ ,1nlogXnx0=Snnlog( + ) +(1 Snn)log( (1 x)) log( +.44x) + log( (1 x)),in probability , asn . The last expression defines as a function ofx. To maximize this,we setd dx= 0 to + solution isx=722, which gives independently at random intonboxes. LetNnbe the numberof empty boxes.

9 Show that1nNnconverges in probability and identify the thatNn=I1+..+In,whereIi=I{i th box is empty}, but you cannot use the weak law of large numbers asIiare notindependent. Nevertheless,EIi=(n 1n)n=(1 1n)n,and soENn=n (1 1n) Convergence IN PROBABILITY116 Moreover,E(N2n) =ENn+ i6=jE(IiIj)withE(IiIj) =P(boxiandjare both empty) =(n 2n)n,so thatVar(Nn) =E(N2n) (ENn)2=n(1 1n)n+n(n 1)(1 2n)n n2(1 1n) letYn=1nNn. We haveEYn e 1asn , andVar(Yn) =1n(1 1n)n+n 1n(1 2n)n (1 1n)2n 0 +e 2 e 2= 0,asn . ThereforeYn=Nnn e 1,asn , in Assume thatnmarried couples (amounting to 2npeople) are seated at random on 2nseatsaround a table. LetTbe the number of couples that sit together.

10 DetermineETand Var(T).2. There arenbirds that sit in a row on a wire. Each bird looks left or right with equalprobability. LetNbe the number of birds not seen by any neighboring bird. Determine, withproof, the constantcso that, asn ,1nN cin Recall the coupon collector problem: sample fromncards, with replacement, indefinitely,and letNbe the number of cards you need to get each ofndifferent cards are represented. Finda sequenceanso that, asn ,N/anconverges to 1 in Kings and Lakers are playing a best of seven playoff series, which means they play untilone team wins four games. Assume Kings win every game independently with Convergence IN PROBABILITY117(There is no difference between home and away games.)