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 Xα 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