1.1. A review of probability theory 17
to strengthen the property of having a uniformly bounded moment, to that
of obtaining a uniformly quantitative control on the decay in (1.24) for a
family of random variables; we will see examples of this in later lectures.
However, this technicality does not arise in the important model case of
identically distributed random variables, since in this case we trivially have
uniformity in the decay rate of (1.24).
We observe some consequences of (1.23) and the preceding definitions:
Lemma 1.1.10. Let X = Xn be a scalar random variable depending on a
parameter n.
(i) If |Xn| has uniformly bounded expectation, then for any ε 0 in-
dependent of n, we have |Xn| =
O(nε)
with high probability.
(ii) If Xn has uniformly bounded
kth
moment, then for any A 0, we
have |Xn| =
O(nA/k)
with probability 1
O(n−A).
(iii) If Xn has uniform sub-exponential tails, then we have
|Xn| =
O(logO(1)
n) with overwhelming probability.
Exercise 1.1.4. Show that a real-valued random variable X is sub-Gaussian
if and only if there exists C 0 such that
EetX
C
exp(Ct2)
for all real
t, and if and only if there exists C 0 such that
E|X|k

(Ck)k/2
for all
k 1.
Exercise 1.1.5. Show that a real-valued random variable X has sub-expo-
nential tails if and only if there exists C 0 such that
E|X|k

exp(CkC)
for all positive integers k.
Once the second moment of a scalar random variable is finite, one can
define the variance
(1.25) Var(X) := E|X
E(X)|2.
From Markov’s inequality we thus have Chebyshev’s inequality
(1.26) P(|X E(X)| λ)
Var(X)
λ2
.
Upper bounds on P(|X E(X)| λ) for λ large are known as large de-
viation inequalities. Chebyshev’s inequality (1.26) gives a simple but still
useful large deviation inequality, which becomes useful once λ exceeds the
standard deviation
Var(X)1/2
of the random variable. The use of Cheby-
shev’s inequality, combined with a computation of variances, is known as
the second moment method.
Exercise 1.1.6 (Scaling of mean and variance). If X is a scalar random
variable of finite mean and variance, and a, b are scalars, show that E(a +
bX) = a + bE(X) and Var(a + bX) =
|b|2Var(X).
In particular, if X has
Previous Page Next Page