Homework 2 - Solutions Intermediate Statistics - 36-705 September 21, 2014 Problem 1. For convenience, let Yi = Xi − µi . We proceed as in the proof of Hoeffding’s inequality. For all c > 0: ! n Pn X P Yi ≥ nt = P e i=1 Yi ≥ ent = i=1 c =P e | Pn = e−cnt i=1 Yi cnt ≥e ≤e {z −cnt Markov’s inequality n Y h Pn i E ec i=1 Yi = } Pn 2 2 E ecYi ≤ e−cnt+c ( i=1 (bi −ai ) )/8 i=1 | {z } Lemma 4, Lecture notes 2 We want to find the tightest possible bound. To do this, we canP choose c > 0 such that 1 the bound is minimized. The minimum is achieved at c = 4nt/ ni=1 (bi − ai )2 , and we finally get: ! n Pn 2 1X 2 2 P Yi ≥ t ≤ e−2n t / i=1 (bi −ai ) n i=1 Problem 2. (We need additonal condition t ≥ 0) t = 0 case is trivial. For t, c > 0 V [X] + c2 P (X − µ ≥ t) = P (X − µ + c ≥ t + c) ≤ E (X − µ + c)2 / (t + c)2 = (t + c)2 by Markov’s inequality. The bound is minimized at c = V [X] /t and plugging this in the previous inequality gives us the desired result. Remark. This inequality is a sharpened version of Chebyshev’s inequality for one-sided case, and it is called Cantelli’s inequality. The following is a case when the equality is achieved:( 1 µ + σt , with prob 1+t 2 X= σ t2 µ − t , with prob 1+t2 Then EX = µ, E[(X − µ)2 ] = σ 2 and P (X − µ ≥ t) = 1 σ2 t2 +σ 2 We set the first derivative of the bound with respect to c equal to zero, and also check that the second derivative is positive. Problem 3. Following the hint we write both sides of the inequality in terms of their Taylor expansion: ∞ ∞ X X tn c2n t2n n E [X ] ≤ n! 2n n! n=0 n=0 This gives us that: t2 c2 t2 ≤ + o t2 E [X] t + E X 2 2! 2 2 where o(t ) represents the extra terms of both sides that go to zero faster than t2 when t → 0. For t > 0, dividing by t and letting t → 0+ we get that E [X] ≥ 0. For t < 0, diving by t flips the inequality and letting t → 0− we get E [X] ≤ 0. This shows that E [X] = 0. Now, by plugging in E [X] = 0, the previous inequality becomes: V [X] c2 t2 t2 ≤ + o t2 2! 2 Dividing by t2 /2 and letting t → 0 we get V [X] ≤ c2 . Problem 4. We have that: E etX = Z 1 0 et − 1 e dx = t tx So for X − 1/2: ∞ (X−1/2)t et/2 − e−t/2 X t2n E e = = t 22n (2n + 1)! n=1 Now since: ec 2 t2 /2 = ∞ X c2n t2n n=1 2n n! Choosing c = 1/2 and noting that 2n n! ≤ (2n + 1)! we obtain the desired result. Problem 5. In the previous problem we found that Wi = Xi − 1/2 is sub-Gaussian with c = 1/2. By Theorem 18 of Lecture Notes 2, we obtain: E [max1≤i≤n Wi ] ≤ 1p 2logn 2 which easily leads to 1 1p + 2logn 2 2 To compute the exact expectation of max1≤i≤n Xi : E [max1≤i≤n Xi ] ≤ P (max1≤i≤n Xi ≤ t) = n Y i=1 P (Xi ≤ t) = tn such that the density function is fX (x) = nxn−1 for 0 ≤ x ≤ 1 and 0 otherwise. Then: Z 1 n nxn dx = E [max1≤i≤n Xi ] = n+1 0 R1 Alternatively, we can get it as E [max1≤i≤n Xi ] = 0 P (max1≤i≤n Xi > t) dt. We can easily √ n ≤ 12 + 12 2logn, ∀n ≥ 1. Yet, notice that this bound tends to infinity as n check that n+1 grows and already for n = 2 it’s above 1. Therefore, this bound is clearly not useful since 0 ≤ Xi ≤ 1 and E [max1≤i≤n Xi ] ≤ 1. From this exercise we should learn that not all the possible bounds are useful. It is always important to try to find the tightest possible bound, by using the information that we may have about the distribution of the random variables we are analysing. Problem 6. For b > 0: P (X > t) = P (bX > bt) = P ebX > ebt ≤ E ebX e−bt {z } | Markov’s inequality 2 2 We know that X is sub-Gaussian. Thus, let c be a constant such that E esX ≤ ec s /2 , ∀s ∈ R. This implies that 2 2 P (X > t) ≤ ec b /2 e−bt By minimizing the bound with respect to b > 0 we obtain: 2 /2c2 P (X > t) ≤ e−t 2 2 We can obtain an identical inequality for P (X < −t), since E e−sX ≤ ec s /2 , ∀s ∈ R. Therefore: 2 2 P (|X| > t) = P (X > t) + P (X < −t) ≤ 2e−t /2c So setting a = 1/2c2 proves the claim. Problem 7. (i) If there exists a, b such that a ≤ Xi ≤ b then this implies that we can set c = max (|a|, |b|) so that c ≥ |Xi |. Note that now the statement that we want to prove is equivalent to: nt2 nt2 > ⇐⇒ c2 > σ 2 + ct/3 2 2 2σ + 2ct/3 2c p Thus, this last inequality is true when for t < 3c and σ < σ 2 − ct/3 (ii) By Hoeffding’s inequality we have that: ! X 2 ¯ √ − µ n ¯ n − µ| > t/ n ≤ 2e− 2tc2 P 1 > t = P |X √n By inverting the bound, we can say that for any δ > 0 we can choose t ≥ ! X ¯ − µ n P 1 >t ≤δ √n q c2 2 log 2 δ s.t. Now using Bernstein’s inequality and setting σ = 1/n ¯ Xn − µ ¯ n − µ > t/n ≤ 2exp − P 1 > t = P X n where ∀t > 3 c t2 /n 2/n2 + 2ct/3n t2 /n t2 t2 t2 3t = ≥ ≥ = 2 2/n + 2ct/3n 2/n + 2ct/3 2 + 2ct/3 2ct/3 + 2ct/3 4c (where c > 0 since σ = 1/n > 0), such that ∀n > 0 ¯ Xn − µ 3t P 1 > t ≤ 2e− 4c n By inverting the bound, we can say that for any δ > 0 we can choose t ≥ 4c log 2δ so that 3 the desired probability is smaller than δ. ¯ n − µ = OP (1/n) by using Hoeffding’s inequality. The bound we Note that we can’t get X would obtain is: ¯ Xn − µ 2t2 ¯ n − µ| > t/n ≤ 2e− nc 2 P 1 > t = P |X n that would require t ≥ q c2 n 2 log 2 δ → ∞ as n → ∞. Problem 8. (i) Since Xn /an = OP (1) and Yn /bn = OP (1), then there exists constants CX , CY such that ∀δ > 0, P (|Xn /an | > CX ) < δ and P (|Yn /bn | > CY ) < δ. Now |Xn Yn |/|an bn | > CX CY ⇒ |Xn /an | > CX or |Yn /bn | > CY So by the union bound P (|Xn Yn |/|an bn | > CX CY ) ≤ P (|Xn /an | > CX ) + P (|Yn /bn | > CY ) < 2δ Since δ was arbitrary Xn Yn = OP (an bn ). (ii) Let δ > 0 and CX , CY as in the previous part, for large n we have that: P (|Xn + Yn | /max {an , bn } > CX + CY ) ≤ ≤ P (|Xn /max {an , bn } | > CX ) + P (|Yn /max {an , bn } | > CY ) ≤ ≤ P (|Xn /an | > CX ) + P (|Yn /bn | > CY ) < 2δ where we used the union bound and the fact that max {an , bn } ≥ an , bn . Since δ was arbitrary this proves the claim. (iii) The claim is false. Let Xn = an = 1 and Yn = n, bn = n2 . Then we have that Xn Yn = n 6= oP (1) = oP (an ). For your interest: we also provide the proof of statement Xn = OP (an ), Yn = oP (bn ) =⇒ Xn Yn = op (an bn ): We need to show ∀ > 0, lim P XannbYnn > = 0, i.e. ∀δ > 0, ∃N ∈ N s.t. ∀n ≥ N , n→∞ Xn Yn P an bn > < δ Let , δ > 0 be given. Since Xn = OP (an ), ∃C > 0 such that ∀n ∈ N, P Xann > C < Yn Also from Yn = oP (bn ), ∃N s.t. ∀n ≥ N , P bn > C < 2δ n o o n o n From XannbYnn > ⊂ Xann > C ∪ Ybnn > C , we have ∀n ≥ N , δ 2 Xn Yn Xn Yn > >C ∪ > P ≤ P a b C an b n n n Yn Xn ≤ P >C +P > an bn C δ δ < + =δ 2 2 Xn Yn ∴∀ > 0, lim P an bn > = 0, i.e. Xn Yn = oP (an bn ). n→∞ (iv) Xn = oP (an ), Yn = oP (bn ), that is ∀, δ > 0 there exists n∗X , n∗Y such that if n > n∗X , n∗Y then P (|Xn /an | > ) < δ and P (|Yn /bn | > ) < δ So for all , δ > 0 and large n: P (| (Xn + Yn ) / (an + bn ) | > 2) = P (|Xn / (an + bn ) + Yn / (an + bn ) | > 2) ≤ ≤ P (|Xn |/ (an + bn ) + |Yn |/ (an + bn ) > 2) ≤ P (|Xn |/an + |Yn |/bn > 2) ≤ ≤ P (|Xn /an | > ) + P (|Yn /bn | > ) < 2δ and the claim is proved. (v) This proposition is false. We provide two possible counterexamples. • Take Xn = 1/n2 , Yn = 1/n4 , an = 1/n and bn = 1/n2 . Then Yn = oP (bn ) =⇒ Yn = OP (bn ) Now note that X n bn Y n an = n Which goes to infinity with probability 1. • Take Yn = Xn2 and bn = a2n . Then Yn = oP (bn ) =⇒ Yn = OP (bn ) Now note that Xn /Yn = 1/Xn 6= oP (1/an ) since for > 0 P (|an /Xn | > ) = P (1/ > |Xn /an |) → 1