Theoretical HW 8

STOR 565 Homework
Show all work.
1. Let X ≥ 0 be a random variable with EX = 10 and EX 2 = 140.
a. Find an upper bound on P(X > 14) involving EX.
b. Find an upper bound on P(X > 14) involving EX 2 .
2. Let X be a random variable with Var(X) = 3. Use Chebyshev’s inequality to find upper
bounds on P(|X − EX| > 1) and P(|X − EX| > 2). Comment on the potential usefulness
of these bounds.
3. Let X be a random variable with mean µ and variance σ 2 .
a. Use Chebyshev’s inequality to bound P(|X − µ| ≥ kσ) for k = 1, 2, 3.
b. Compare the bounds in part (a) with standard estimates for the same probabilities
when X ∼ N (µ, σ 2 ), i.e., what you find by using normal tables.
4. Let X1 , . . . , Xn be independent Bernoulli(p) random variables, and let Sn = X1 +· · ·+Xn .
a. What is the distribution of Sn ?
b. Find ESn and Var(Sn ).
c. Use Chebyshev’s inequality to bound on P(|Sn − ESn | ≥ t).
d. Use Hoeffding’s inequality to bound on P(|Sn − ESn | ≥ t).
e. Suppose now that n = 20 and p = 1/2. Apply the bounds in (c) and (d) with t = 5
and 7, and compare the results.
1
5. Let X1 , X2 , . . . X ∈ X be independent, and let f1 , f2 , . . . be functions defined on X with
values in the interval [−1, 1].
a. Fix j for the moment and consider the random variable fj (X), which takes values in
[−1, 1]. In the first homework you found a bound on Var(fj (X)). Use this result and
Chebyshev’s inequality to bound the probability
n
1 X
P fj (Xi ) − Efj (X) ≥ t
n
(1)
i−1
for t ≥ 0.
b. Use Hoeffding’s inequality to bound the probability in (1).
c. Fix m ≥ 1. Argue that the two events
(
)
(
)
n
n
m
1 X
1 X
[
max fj (Xi ) − Efj (X) ≥ t
and
fj (Xi ) − Efj (X) ≥ t
1≤j≤m n
n
i−1
j=1
i−1
are the same.
d. Combine (a), (c), and the union bound to find an upper bound for
n
1 X
fj (Xi ) − Efj (X) ≥ t
P max 1≤j≤m n
i−1
Then do the same using the Hoeffding bound you found in part (b). What happens
to these bounds as n tends to infinity (with t fixed)? You can think of this bound as
saying that the ordinary weak law of large numbers holds uniformly for the random
sequences {fj (X1 ), fj (X2 ), . . .} with j = 1, . . . , m.
e. The bound you found in part (d) holds for each value of n. We can also consider a
bound involving more functions as m gets larger. Suppose that m depends on n, in
particular that mn = nd grows like a polynomial in d for some d ≥ 1. Apply the
bounds in part (d) to the probability
P
n
1 X
max fj (Xi ) − Efj (X) ≥ t .
1≤j≤nd n
i−1
How do these bounds behave as n tends to infinity (with t fixed)?
2

Download Report