Description

Department of Electrical Engineering and Computer Sciences
EECS 126: Probability and Random Processes
Discussion 5
1. Curse of Dimensionality
In this problem, we will use the law of large numbers to illustrate a statistical phenomenon. In particular, consider the hypercube [−1,1]n in Rn, and let X1,…,Xn be iid Uniform([−1,1]). (a) For > 0 consider the set
,
which is the -boundary of a ball with radius pn/3 centered at the origin. For low dimensions n = 1,2 and 10, compute the fraction of volume of [−1,1]n which comes from .
(b) Show that as n gets large, most of the volume of the hypercube comes from . Comment on why this contradicts the intuition developed in part (a).
2. Product of Rolls of a Die
A fair die with labels (1 to 6) is rolled until the product of the last two rolls is 12. What is the expected number of rolls?
3. Concentration for Binomials & Gaussians
For sums of bounded zero-mean i.i.d. random variables Sn = X1 + … + Xn, a Chernoff-type inequality tells us that

|Sn| ≥ t√n) ≤ C exp(−ct2), P(
for some constants C,c > 0.
(a) (Optional) Prove the inequality above.
(b) Let Z ∼ N(0,1). Show that
P(|Z| ≥ t) ≤ C exp(−ct2).
1