EECS 126: Probability and Random Processes
Problem Set 6
1. The CLT Implies the WLLN
(a) Let {Xn}n∈N be a sequence of random variables. Show that if Xn
d
−→ c, where c is a
constant, then Xn
P
−→ c.
(b) Let {Xn}n∈N be a sequence of i.i.d. random variables, with mean µ and finite variance
σ
2
. Show that the CLT implies the WLLN, i.e. if
1
σ
√
n
Xn
i=1
(Xi − µ)
d−→ N (0, 1),
then
1
n
Xn
i=1
Xi
P
−→ µ.
2. Confidence Intervals: Chebyshev vs. Chernoff vs. CLT
Let X1, . . . , Xn be i.i.d. Bernoulli(q) random variables, with common mean µ = E[X1] = q
and variance σ
2 = var(X1) = q(1 − q). We want to estimate the mean µ, and towards this
goal we use the sample mean estimator
X¯
n
∆=
X1 + · · · + Xn
n
.
Given some confidence level a ∈ (0, 1) we want to construct a confidence interval around X¯
n
such that µ lies in this interval with probability at least 1 − a.
(a) Use Chebyshev’s inequality in order to show that µ lies in the interval
X¯
n −
σ
√
n
1
√
a
, X¯
n +
σ
√
n
1
√
a
with probability at least 1 − a.
(b) A Chernoff bound for this setting can be computed to be:
P(|X¯
n − q| ≥ ) ≤ 2e
−2n2
, for any > 0.
Use this inequality in order to show that µ lies in the interval
X¯
n −
1
√
2
n
r
2 ln 2
a
, X¯
n +
1
√
2
n
r
2 ln 2
a
with probability at least 1 − a.
1
(c) Show that if Z ∼ N (0, 1), then
P(|Z| ≥ ) ≤ 2e
−
2
2 , for any > 0.
(d) Use the Central Limit Theorem, and Part (c) in order to heuristically argue that µ lies
in the interval
X¯
n −
σ
√
n
r
2 ln 2
a
, X¯
n +
σ
√
n
r
2 ln 2
a
with probability at least 1 − a.
(e) Compare the three confidence intervals.
3. Transform Practice
Consider a random variable Z with transform
MZ(s) = a − 3s
s
2 − 6s + 8
, for |s| < 2.
Calculate the following quantities:
(a) The numerical value of the parameter a.
(b) E[Z].
(c) var(Z).
4. Rotationally Invariant Random Variables
Suppose random variables X and Y are i.i.d., with zero mean, such that their joint density is
rotation invariant, i.e. for any orthogonal matrix U with orthonormal rows and orthonormal
columns,
U
X
Y
d=
X
Y
(a) Let ϕ(t) be the characteristic function of X. Show that ϕ(t)
n = ϕ(
√
nt).
(b) Show that ϕ(t) = exp(ct2
) for some constant c, and all t such that t
2 ∈ Q. Hint: Let
t
2 = a/b, where a, b are positive integers.
(c) Conclude that X and Y must be Gaussians.
5. Matrix Sketching
Matrix sketching is an important technique in randomized linear algebra to do large computations efficiently. For example, to compute the multiplication AT × B of two large matrices A
and B, we can use a random sketch matrix S to compute a ”sketch” SA of A and a ”sketch”
SB of B. Such a sketching matrix has the property that S
TS ≈ I so that the approximate
multiplication ATS
TSB is close to AT B.
In this problem, we will discuss two popular sketching schemes and understand how they help
in approximate computation. Let ˆI = S
TS and the dimension of sketch matrix S be d × n
(typically d n).
2
(a) (Gaussian-sketch) Define
S =
1
√
d
S11 . . . . . . S1n
.
.
.
.
.
.
.
.
.
Sd1 . . . . . . Sdn
such that Sij ’s are chosen i.i.d. from N (0, 1) for all i ∈ [1, d] and j ∈ [1, n]. Find the
element-wise mean and variance (as a function of d) of the matrix ˆI = S
TS, that is, find
E[
ˆIij ] and Var[ˆIij ] for all i ∈ [1, n] and j ∈ [1, n].
(b) (Count-sketch) For each column j ∈ [1, n] of S, choose a row i uniformly randomly
from [1, d] such that
Sij =
(
1, with probability 0.5
−1, with probability 0.5
and assign Skj = 0 for all k 6= i. An example of a 3 × 8 count-sketch is
S =
0 −1 1 0 0 −1 0 0
1 0 0 0 −1 0 −1 0
0 0 0 1 0 0 0 −1
Again, find the element-wise mean and variance (as a function of d) of the matrix ˆI = S
TS.
Note that for sufficiently large d, the matrix ˆI is close to the identity matrix for both cases.
We will use this fact in the lab to do an approximate matrix multiplication.
Note: You can use the fact that the fourth moment of a standard Gaussian is 3 without
proof.
3
