### Homework 2 - Solutions

```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
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
```