Probability theory

Manjunath Krishnapur

D EPARTMENT OF M ATHEMATICS , I NDIAN INSTITUTE OF S CIENCE

 2000 Mathematics Subject Classification. Primary

A BSTRACT. These are lecture notes from the spring 2010 Probability theory class at
IISc. There are so many books on this topic that it is pointless to add any more, so
these are not really a substitute for a good (or even bad) book, but a record of the
lectures for quick reference. I have freely borrowed a lot of material from various
sources, like Durrett, Rogers and Williams, Kallenberg, etc. Thanks to all students
who pointed out many mistakes in the notes/lectures.
 Contents

Chapter 1. Measure theory 1

1.1. Probability space 1
1.2. The ‘standard trick of measure theory’! 4
1.3. Lebesgue measure 6
1.4. Non-measurable sets 8
1.5. Random variables 9
1.6. Borel Probability measures on Euclidean spaces 10
1.7. Examples of probability measures on the line 11
1.8. A metric on the space of probability measures on Rd 12
1.9. Compact subsets of P (Rd ) 13
1.10. Absolute continuity and singularity 14
1.11. Expectation 16
1.12. Limit theorems for Expectation 17
1.13. Lebesgue integral versus Riemann integral 17
1.14. Lebesgue spaces: 18
1.15. Some inequalities for expectations 18
1.16. Change of variables 19
1.17. Distribution of the sum, product etc. 21
1.18. Mean, variance, moments 22

Chapter 2. Independent random variables 25

2.1. Product measures 25
2.2. Independence 26
2.3. Independent sequences of random variables 27
2.4. Some probability estimates 30
2.5. Applications of first and second moment methods 30
2.6. Weak law of large numbers 34
2.7. Applications of weak law of large numbers 35
2.8. Modes of convergence 37
2.9. Uniform integrability 38
2.10. Strong law of large numbers 40
2.11. Kolmogorov’s zero-one law 41
2.12. The law of iterated logarithm 42
2.13. Hoeffding’s inequality 43
2.14. Random series with independent terms 44
2.15. Kolmogorov’s maximal inequality 46
2.16. Central limit theorem - statement, heuristics and discussion 46
2.17. Central limit theorem - Proof using characteristic functions 48
2.18. CLT for triangular arrays 48
v
vi CONTENTS

2.19. Limits of sums of random variables 50

2.20. Poisson convergence for rare events 51

Chapter 3. Brownian motion 53

3.1. Brownian motion and Winer measure 53
3.2. Some continuity properties of Brownian paths - Negative results 54
3.3. Some continuity properties of Brownian paths - Positive results 55
3.4. Lévy’s construction of Brownian motion 56

Appendix A. Characteristic functions as tool for studying weak convergence 59

Defintions and basic properties 59
(A) Transformation rules 59
(B) Inversion formulas 60
(C) Continuity theorem 62
 CHAPTER 1

Measure theory

1.1. Probability space

“Random experiment” was a non-mathematical term used to describe physical
situations with more than one possible outcome, for instance, “toss a fair coin and
observe the outcome”. In probability, although we sometimes use the same language,
it is only as a quick substitute for a mathematically meaningful and precise phrasing.
Consider the following examples.
(1) “Draw a random integer from 1 to 100. What is the probability that you
get a prime number?” Mathematically, we just mean the following. Let
1
Ω = {1, 2 . . . , 100}, and for each ω ∈ Ω, we set p ω = 100 . Subsets A ⊂ Ω are
P
called ’events’ and for each subset we define P( A ) = ω∈ A p ω . In particular,
for A = {2, 3, 5, . . . , 97}, we get P( A ) = 14 .
This is the setting for all of discrete probability. We have a finite or
countable set Ω called sample space, and for each ω ∈ Ω a number p ω ≥ 0 is
specified, so that ω p ω = 1. For any A ⊂ Ω, one defines its probability to be
P
P
P( A ) := ω∈ A p ω . The whole game is to calculate probabilities of interesting
events! The difficulty is of course that the set Ω and probabilities p ω may
be defined by a property which makes it hard to calculate probabilities.

Example 1.1. Fix n ≥ 1 and let Ω be the set of all self-avoiding paths on
length n in Z2 starting from (0, 0). That is,

Ω = {ω = (ω0 , . . . , ωn ) : ω i ∈ Z2 , ω0 = (0, 0), ω i − ω i−1 ∈ {±e1 , ±e2 }}.

Then let p ω = #1Ω . One interesting event is A = {ω : kωn k < n0.6 }. Far from
finding P( A ), it has not been proved to this day whether for large n, the
value P ( A ) is close to zero or one!

(2) “Draw a number at random from the interval [0, 1]. What is the probability
that it is less than 21 ? That it is rational? That its decimal expansion con-
tains no 7?” For the first question it seems that the answer must be 21 , but
the next two questions motivate us to think more deeply about the meaning
of such an assertion.
Like before we may set Ω = [0, 1]. What is p ω ? ’Intutively’ it seems that
the probability of the number falling in an interval [a, b] ⊂ [0, 1] should be
b − a and that forces us to set p ω = 0 for every ω. But then we cannot pos-
P
sibly get P([a, b]) as ω∈[a,b] p ω , even if such an uncountable sum had any
meaning! So what is the basis for asserting that P[a, b] = b − a?! Under-
standing this will be the first task.
A first attempt: Let us define the probability of any set A ⊂ [0, 1] to be the
length of that set. We understand the length of an interval, but what is
1
2 1. MEASURE THEORY

the length of the set of rational numbers? irrational numbers? A seemingly

reasonable idea is to set
( )
X
P∗ ( A ) = inf | I k | : each I k is an interval and { I k } a countable cover for A .
k
Then perhaps, P∗ ( A ) should be the probability of A for every subset A ⊂
[0, 1]. This is at least reasonable in that P∗ [a, b] = b − a for any [a, b] ⊂
[0, 1]. But we face an unexpected problem. One can find1 A such that
P∗ ( A ) = 1 and P∗ ( A c ) = 1 and that violates one of the basic requirements of
probability, that P∗ ( A ∪ A c ) be equal to P∗ ( A ) + P∗ ( A c )! You may object that
our definition of P∗ was arbitrary, may be another definition works? Before
tackling that question, we should make precise what all we properties we
require probabilities to satisfy. This we do next, but let us record here that
there will be two sharp differences from discrete probability.
(a) One cannot hope to define P( A ) for all A ⊂ [0, 1], but only for a rich
enough class of subsets! These will be called events.
(b) One does not start with elementary probabilities p ω and then compute
P( A ), but probabilities of all events are part of the specification of the
probability space! (If all probabilities are specified at the outset, what
does a probabilist do for a living? Hold that thought till the next lec-
ture!).
Now we define the setting of probability in abstract and then return to the sec-
ond situation above.
Definition 1.2. A probability space is a triple (Ω, F , P) where
(1) The sample space Ω is an arbitrary set.
(2) The σ-field or σ-algebra F is a set of subsets of Ω such that (i) φ, Ω ∈ F ,
(ii) if A ∈ F , then A c ∈ F , (iii) if A n ∈ F for n = 1, 2 . . ., then ∪ A n ∈ F .
In words, F is closed under complementation and under countable unions,
and contains the empty set. Elements of F are called measurable sets.
(3) The probability measure is any function P : F → [0, 1] is such that if A n ∈ F
P
and are pairwise disjoint, then P(∪ A n ) = P( A n ) (countable additivity) and
such that P(Ω) = 1. P( A ) is called the probability of A .
Measurable sets are what we call events in probability theory. It is meaningless
to ask for the probability of a subset of Ω that is not measurable. The σ-field is
closed under many set operations and the usual rules of probability also hold. If one
allows P to take values in [0, ∞] and drops the condition P(Ω) = 1, then it is just
called a measure. Measures have the same basic properties as probability measures,
but probabilistically crucial concepts of independence and conditional probabilities
(to come later) don’t carry over to general measures and that is mainly what makes
probability theory much richer than general measure theory.
Exercise 1.3. Let (Ω, F , P) be a probability space.
(1) F is closed under finite and countable unions, intersections, differences,
symmetric differences. Also Ω ∈ F .
(2) If A n ∈ F , then lim sup A n := {ω : ω belongs to infinitely many A n } and
lim inf A n := {ω : ω belongs to all but finitely many A n } are also in F . In
particular, if A n increases or decreases to A , then A ∈ F .
1Not obvious!
 1.1. PROBABILITY SPACE 3

(3) P(φ) = 0, P(Ω) = 1. For any A, B ∈ F we have P( A ∪ B) = P( A ) + P(B) − P( A ∩

B). If A n ∈ F , then P(∪ A n ) ≤ P( A n ).
P

(4) If A n ∈ F and A n increases (decreases) to A , the P( A n ) increases (de-

creases) to P( A ).
Some examples of probability spaces.
Example 1.4. Let Ω be a finite or countable set. Let F be the collection of all
subsets of Ω. Then F is a σ-field. Given any numbers p ω , ω ∈ Ω that add to 1, we
set P( A ) = ω∈ A p ω . Then P is a probability measure. More generally, let Ω be any
P

set and let R ⊂ Ω be a countable set. Let F be the powerset of Ω. Fix nonnegative
P
numbers p x , x ∈ R that add to 1. Then define P( A ) = x∈R ∩ A p x . This is a probability
measure on F .
This means that a discrete measure, say Binomial distribution, can be consid-
ered as a p.m. on {1, 2, . . . , n} or on R. The problem of not being able to define proba-
bility for all subsets does not arise when the p.m. is so simple.
Example 1.5. Let Ω be an arbitrary set. Let F = { A ⊂ Ω : either A or A c is countable}
(where ‘countable’ includes finite and empty sets). Define P( A ) = 0 if A is countable
and P( A ) = 1 if A c is countable. This is just a frivolous example of no particular
importance.
Exercise 1.6. Check that F is a σ-field and that P is a probability measure on F .
In the most interesting cases, one cannot explicitly say what the elements of
F are, but only require that it is rich enough. Here is an exercise to introduce the
important idea of a σ-field generated by a collection of sets.
Exercise 1.7. Let Ω be a set and let S be a collection of subsets of Ω. Show that
there is a smallest sigma filed F containing all elements of S . That is, if G is any
σ-field of subsets of Ω and G ⊃ S , then G ⊃ F . F is called the σ-field generated by S
and often denoted σ(S ).

Now we come to the most interesting probability spaces for Probability theory.
Example 1.8. Let Ω = [0, 1]. Let S be the collection of all intervals, to be precise
let us take all right-closed, left-open intervals (a, b], with 0 ≤ a < b ≤ 1 as well as
intervals [0, b], b ≤ 1. If we are trying to make precise the notion of ‘drawing a
number at random from [0, 1]’, then we would want P(a, b] = b − a and P[0, b] = b.
The precise mathematical questions can now be formulated as follows. (i) Let G be
the σ-field of all subsets of [0, 1]. Is there a p.m. P on G such that P(a, b] = b − a and
P[0, b] = b for all 0 ≤ a < b ≤ 1? If the answer is ‘No’, we ask for the less ambitious
(ii) Is there a smaller σ-field large enough to contain all interval (a, b], say F = σ(S )
such that P(a, b] = b − a?
The answer to the first question is ’No’, which is why we need the notion of σ-
fields, and the answer to the second question is ‘Yes’, which is why probabilists still
have their jobs. Neither answer is obvious, but we shall answer them in coming
lectures.
Example 1.9. Let Ω = {0, 1}N = {ω = (ω1 , ω2 , . . .) : ω i ∈ {0, 1}}. Let S be the collection of
all subsets of Ω that depend on only finitely many co-ordinates (such sets are called
cylinders). More precisely, a cylinder set is of the form A = {ω : ωk1 = ²1 , . . . ωk n = ²n }
for some given n ≥ 1, k 1 < k 2 < . . . < k n and ² i ∈ {0, 1} for i ≤ n.
4 1. MEASURE THEORY

What are we talking about? If we want to make precise the notion of ‘toss a
coin infinitely many times’, then clearly Ω is the sample space to look at. It is also
desirable that elements of S be in the σ-field as we should be able to ask questions
such as ‘what is the chance that the fifth, seventh and thirtieth tosses are head, tail
and head respectively’ which is precisely asking for the probability of a cylinder set.
If we are ‘tossing a coin with probability p of turning up Head’, then for a cylinder
set A = {ω : ωk1 = ²1 , . . . ωk n = ²n }, it is clear that we would like to assign P( A ) =
Qn ² i 1−² i
i =1 p i q where q = 1 − p. So the mathematical questions are: (i) If we take F
to be the σ-field of all subsets of Ω, does there exist a p.m. P on F such that for
cylinder sets P( A ) is as previously specified. (ii) If the answer to (i) is ‘No’, is there
a smaller σ-field, say the one generated by all cylinder sets and a p.m. P on it with
probabilities as previously specified for cylinders?
Again, the answers are ‘No’ and ‘Yes’, respectively.

The σ-fields in these two examples can be captured under a common definition.

Definition 1.10. Let ( X , d ) be a metric space. The σ-field B generated by all open
balls in X is called the Borel sigma-field of X .

First consider [0, 1] or R. Let S = {(a, b]} ∪ {[0, b]} and let T = {(a, b)} ∪ {[0, b)} ∪
{(a, 1]}. We could also simply write S = {(a, b] ∩ [0, 1] : a < b ∈ R} and T = {(a, b) ∩ [0, 1] :
a < b ∈ R}. Let the sigma-fields generated by S and T be denoted F (see example
above) and B (Borel σ-field), respectively. Since
(a, b) = ∪n (a, b − 1/ n], (a, b] = ∩n (a, b + 1/ n], [0, b] = ∩n
it is clear that S ⊂ B and T ⊂ F . Hence F = B .
In the countable product space Ω = {0, 1}N or more generally Ω = X N , the topology
is the one generated by all sets of the form U1 × . . . × Un × X × X × . . . where U i are
open sets in X . Clearly each of these sets is a cylinder set. Conversely, each cylinder
set is an open set. Hence G = B . More generally, if Ω = X N , then cylinders are sets
of the form A = {ω ∈ Ω : ωk i ∈ B i , i ≤ n} for some n ≥ 1 and k i ∈ N and some Borel
subsets B i of X . It is easy to see that the σ-field generated by cylinder sets is exactly
the Borel σ-field.

1.2. The ‘standard trick of measure theory’!

While we care about sigma fields only, there are smaller sub-classes that are
useful in elucidating the proofs. Here we define some of these.

Definition 1.11. Let S be a collection of subsets of Ω. We say that S is a

(1) π-system if A, B ∈ S =⇒ A ∩ B ∈ S .
(2) λ-system if (i) Ω ∈ S . (ii) A, B ∈ S and A ⊆ B =⇒ B\ A ∈ S . (iii) A n ↑ A
and A n ∈ S =⇒ A ∈ S .
(3) Algebra if (i) φ, Ω ∈ S . (ii) A ∈ S =⇒ A c ∈ S . (iii) A, B ∈ S =⇒ A ∪ B ∈ S .
(4) σ-algebra if (i) φ, Ω ∈ S . (ii) A ∈ S =⇒ A c ∈ S . (iii) A n ∈ S =⇒ ∪ A n ∈ S .

We have included the last one again for comparision. Note that the difference be-
tween algebras and σ-algebras is just that the latter is closed under countable unions
while the former is closed only under finite unions. As with σ-algebras, arbitrary in-
tersections of algebras/λ-systems/π-systems are again algebras/λ-systems/π-systems
and hence one can talk of the algebra generated by a collection of subsets etc.
 1.2. THE ‘STANDARD TRICK OF MEASURE THEORY’! 5

Example 1.12. The table below exhibits some examples.

Ω S (π − system) A (S ) (algebra generated by S ) σ( S )

(0, 1] {(a, b] : 0 < a ≤ b ≤ 1} {∪kN=1 (a k , b k ] : 0 < a 1 ≤ b 1 ≤ a 2 ≤ b 2 . . . ≤ b N ≤ 1} B (0, 1]
[0, 1] {(a, b] ∩ [0, 1] : a ≤ b} {∪kN=1 R k : R k ∈ S are pairwise disjoint} B [0, 1]
Rd { di=1 (a i , b i ] : a i ≤ b i } {∪kN=1 R k : R k ∈ S are pairwise disjoint} BR d
Q

{0, 1}N collection of all cylinder sets finite disjoint unions of cylinders B ({0, 1}N )

Often, as in these examples, sets in a π-system and in the algebra generated by the
π-system can be described explicitly, but not so the sets in the generated σ-algebra.

Clearly, a σ-algebra is an algebra is a π-systemas well as a λ-system. The follow-

ing converse will be useful. Plus, the proof exhibits a basic trick of measure theory!

Lemma 1.13 (Sierpinski-Dynkin π − λ theorem). Let Ω be a set and let F be a set of

subsets of Ω.
(1) F is a σ-algebra if and only if it is a π-system as well as a λ-system.
(2) If S is a π-system, then λ(S ) = σ(S ).

P ROOF. (1) One way is clear. For the other way, suppose F is a π-system
as well as a λ-system. Then, φ, Ω ∈ F . If A ∈¡ F , then¢ A c = Ω\ A ∈ F . If
c
A n ∈ F , then the finite unions B n := ∪nk=1 A k = ∩nk=1 A kc belong to F as F
is a π-system. The countable union ∪ A n is the increasing limit of B n and
hence belongs to F by the λ-property.
(2) By part (i), it suffices to show that F := λ(S ) is a π-system, that is, we only
need show that if A, B ∈ F , then A ∩ B ∈ F . This is the tricky part of the
proof!
Fix A ∈ S and let F A := {B ∈ F : B ∩ A ∈ F }. S is a π-system, hence
F A ⊃ S . We claim that F A is a λ-system. Clearly, Ω ∈ F A . If B, C ∈ F A
and B ⊂ C , then (C \B) ∩ A = (C ∩ A )\(B ∩ A ) ∈ F because F is a λ-system
containing C ∩ A and B ∩ A . Thus (C \B) ∈ F A . Lastly, if B n ∈ F A and B n ↑ B,
then B n ∩ A ∈ F A and B n ∩ A ↑ B ∩ A . Thus B ∈ F A . This means that F A is
a λ-system containing S and hence F A ⊃ F . In other words, A ∩ B ∈ F for
all A ∈ S and all B ∈ F .
Now fix any A ∈ F . And again define F A := {B ∈ F : B ∩ A ∈ F }.
Because of what we have already shown, F A ⊃ S . Show by the same argu-
ments that F A is a λ-system and conclude that F A = F for all A ∈ F . This
is another way of saying that F is a π-system. ■

As an application, we prove a certain uniqueness of extension of measures.

Lemma 1.14. Let S be a π-system of subsets of Ω and let F = σ(S ). If P and Q are
two probability measures on F such that P( A ) = Q( A ) for all A ∈ S , then P( A ) = Q( A )
for all A ∈ F .

P ROOF. Let T = { A ∈ F : P( A ) = Q( A )}. By the hypothesis T ⊃ S . We claim that

T is a λ-system. Clearly, Ω ∈ T . If A, B ∈ T and A ⊃ B, then P( A \B) = P( A ) − P(B) =
Q( A ) − Q(B) = Q( A \B) implying that A \B ∈ T . Lastly, if A n ∈ T and A n ↑ A , then
P( A ) = limn→∞ P( A n ) = limn→∞ Q( A n ) = Q( A ). Thus T ⊃ λ(S ) which is equal to σ(S )
by Dynkin’s π − λ theorem. Thus P = Q on F . ■
6 1. MEASURE THEORY

1.3. Lebesgue measure

Theorem 1.15. There exists a unique Borel probability measure m on [0, 1] such that
m( I ) = | I | for any interval I .

[Sketch of the proof] Note that S = {(a, b] ∩ [0, 1]} is a π-system that generate B .
Therefore by Lemma 1.14, uniqueness follows. Existence is all we need to show.
There are two steps.

Step 1 - Construction of the outer measure m∗ Recall that we define m∗ ( A ) for

any subset by
( )
X
m∗ ( A ) = inf | I k | : each I k is an open interval and { I k } a countable cover for A .
k

m∗ has the following properties. (i) m∗ is a [0, 1]-valued function defined on all
subsets A ⊂ Ω. (ii) m∗ ( A ∪ B) ≤ m∗ ( A ) + m∗ (B) for any A, B ⊂ Ω. (iii) m∗ (Ω) = 1.
These properties constitute the definition of an outer measure. In the case at
hand, the last property follows from the following exercise.

Exercise 1.16. Show that m∗ (a, b] = b − a if 0 < a ≤ b ≤ 1.

P
Clearly, we also get countable subadditivity m∗ (∪ A n ) ≤ m∗ ( A n ). The differ-
ence from a measure is that equality might not hold, even if the sets are pairwise
disjoint.

Step-2 - The σ-field on which m∗ is a measure

Let m∗ be an outer measure on a set Ω. Then by restricting m∗ to an appropriate
σ-fields one gets a measure. We would also like this σ-field to be large (not the sigma
algebra {;, Ω} please!).
Cartheodary’s brilliant definition is to set
F := A ⊂ Ω : m∗ (E ) = m∗ ( A ∩ E ) + m∗ ( A c ∩ E ) for any E .
© ª

Note that subadditivity implies m∗ (E ) ≤ m∗ ( A ∩ E ) + m∗ ( A c ∩ E ) for any E for any

A, E . The non-trivial inequality is the other way.

Theorem 1.17. Then, F is a sigma algebra and µ∗ restricted to F is a p.m.

P ROOF. It is clear that ;, Ω ∈ F and A ∈ F implies A c ∈ F . Next, suppose

A, B ∈ F . Then for any E ,
m∗ (E ) = m∗ (E ∩ A )+m∗ (E ∩ A c ) = m∗ (E ∩ A ∩B)+{m∗ (E ∩ A ∩B c )+m∗ (E ∩ A c )} ≥ m∗ (E ∩ A ∩B)+m∗ (E ∩( A ∩B) c ))
where the last inequality holds by subadditivity of m∗ and (E ∩ A ∩ B c ) ∪ (E ∩ A c ) =
E ∩ ( A ∩ B) c . Hence F is a π-system.
As A ∪ B = ( A c ∩ B c ) c , it also follows that F is an algebra. For future use, note
that m∗ ( A ∪ B) = m∗ ( A ) + m∗ (B) if A, B are disjoint sets in F . To see this apply the
definition of A ∈ F with E = A ∪ B.
It suffices to show that F is a λ-system. Suppose A, B ∈ F and A ⊃ B. Then
m∗ (E ) = m∗ (E ∩B c )+m∗ (E ∩B) = m∗ (E ∩B c ∩ A )+m∗ (E ∩B c ∩ A c )+m∗ (E ∩B) ≥ m∗ (E ∩( A \B))+m∗ (E ∩( A \B) c ).
Before showing closure under increasing limits, Next suppose A n ∈ F and A n ↑
A . Then m∗ ( A ) ≥ m∗ ( A n ) = nk=1 m∗ ( A k \ A k−1 ) by finite additivity of m∗ . Hence
P
 1.3. LEBESGUE MEASURE 7

P
m∗ ( A ) ≥ m∗ ( A k \ A k−1 ). The other way inequality follows by subadditivity of m∗
P
and we get m∗ ( A ) = m∗ ( A k \ A k−1 ). Then for any E we get
n
m∗ (E ) = m∗ (E ∩ A n )+m∗ (E ∩ A nc ) ≥ m∗ (E ∩ A n )+m∗ (E ∩ A c ) = m∗ (E ∩( A k \ A k−1 ))+m∗ (E ∩ A c ).
X
k=1
The last equality follows by finite additivity of m∗ on F . Let n → ∞ and use subad-
ditivity to see that
∞
m∗ (E ∩ ( A k \ A k−1 )) + m∗ (E ∩ A c ) ≥ m∗ (E ∩ A ) + m∗ (E ∩ A c ).
X
m∗ (E ) ≥
k=1
Thus, A ∈ F and it follows that F is a λ-system too and hence a σ-algebra.
Lastly, if A n ∈ F are pairwise disjoint with union A , then m∗ ( A ) ≥ m∗ ( A n ) =
Pn P
k=1 ∗
m ( A k ) → k m∗ ( A k ) while the other way inequality follows by subadditivity of
m∗ and we see that m∗ |F is a measure.
Step-3 - F is large enough!
Let A = (a, b]. For any E ⊂ [0, 1], let { I n } be an open cover such that m∗ (E ) ≥
| I n |. Then, note that { I n ∩ (a, b)} and { I n ∩ [a, b] c } are open covers for A ∩ E and
P

A c ∩ E , respectively ( I n ∩ [a, b] c may be a union of two intervals, but that does not
change anything essential). It is also clear that | I n | = | I n ∩ (a, b)|+| I n ∩ (a, b) c |. Hence
we get
m∗ (E ) ≥ | I n ∩ (a, b)| + | I n ∩ (a, b) c | ≥ m∗ ( A ∩ E ) + m∗ ( A c ∩ E ).
X X

The other inequality follows by subadditivity and we see that A ∈ F . Since the
intervals (a, b] generate B , and F is a sigma algebra, we get F ⊃ B . Thus, restricted
to B also, m∗ gives a p.m. ■

Remark 1.18. (1) We got a σ-algebra F that is larger than B . Two natural
questions. Does F or B contain all subsets of [0, 1]? Is F strictly larger
than B ? We show that F does not contain all subsets. One of the homework
problems deals with the relationship between B and F .
(2) m, called the Lebesgue measure on [0, 1], is the only probability space one
ever needs. In fact, all probabilities ever calculated can be seen, in princi-
ple, as calculating the Lebsgue measure of some Borel subset of [0, 1]!

Generalities The construction of Lebesgue measure can be made into a general

procedure for constructing interesting measures, starting from measures of some
rich enough class of sets. The steps are as follows.
(1) Given an algebra A (in this case finite unions of (a, b]), and a countably
additive p.m P on A , define an outer measure P∗ on all subsets by taking
infimum over countable covers by sets in A .
(2) Then define F exactly as above, and prove that F ⊃ A is a σ-algebra and
P∗ is a p.m. on A .
(3) Show that P∗ = P on A .
Proofs are quite the same. Except, in [0, 1] we started with m defined on a π-system
S rather than an algebra. But in this case the generated algebra consists precisely
of disjoint unions of sets in S , and hence we knew how to define m on A (S ). When
can we start with P defined ona π-system? The crucial point in [0, 1] was that for
any A ∈ S , one can write A c as a finite union of sets in S . In such cases (which
8 1. MEASURE THEORY

includes examples from the previous lecture) the generated algebra is precisely the
set of disjoint finite unions of sets in S and we define P on A (S ) and then proceed to
step one above.

Exercise 1.19. Use the general procedure as described here, to construct the follow-
ing measures.
(a) A p.m. on ([0, 1]d , B ) such that P([a 1 , b 1 ] × . . . × [a d , b d ]) = dk=1 ( b k − a k ) for
Q

all cubes contained in [0, 1]d . This is the d-dimensional Lebesgue measure.
(b) A p.m. on {0, 1}N such that for any cylinder set A = {ω : ωk j = ² j , j = 1, . . . , n}
(any n ≥ 1 and k j ∈ N and ² j ∈ {0, 1}) we have (for a fixed p ∈ [0, 1] and q = 1 − p)
n
p² j q1−² j .
Y
P( A ) =
j =1

[Hint: Start with the algebra generated by cylinder sets].

1.4. Non-measurable sets

We have not yet shown the necessity for σ-fields. Restrict attention to ([0, 1], F , m)
where F is either (i) B , the Borel σ-algebra or (ii) B the possibly larger σ-algebra of
Lebesgue measurable sets (as defined by Caratheodary). This consists of two distinct
issues.
(1) Showing that B (hence B ) does not contain all subsets of [0, 1].
(2) Showing that it is not possible at all to define a p.m. P on the σ-field of
all subsets so that P[a, b] = b − a for all 0 ≤ a ≤ b ≤ 1. In other words, one
cannot consistently extend m from B (on which it is uniquely determined
by the condition m[a, b] = b − a) to a p.m. P on the σ-algebra of all subsets.

(1) B does not contain all subsets of [0, 1]: We shall need the following ‘transla-
tion invariance property’ of m on B .
Exercise 1.20. For any A ⊂ [0, 1] and any x ∈ [0, 1], m( A + x) = m( A ), where A + x :=
{ y + x(mod 1) : y ∈ A } (eg: [0.4, 0.9] + 0.2 = [0, 0.1] ∪ [0.6, 1]). Show that for any A ∈ B
and x ∈ [0, 1] that A + x ∈ B and that m( A + x) = m( A ).
Now we construct a subset A ⊂ [0, 1] and countably (infinitely) many xk ∈ [0, 1]
such that the sets A + xk are pairwise disjoint and ∪k ( A + xk ) is the whole of [0, 1].
Then, if A were in B , by the exercise A + xk would have the same probability as A .
But m( A + xk ) must be equal to m[0, 1] = 1, which is impossible! Hence A ∉ B .
P

How to construct such a set A and { xk }? Define an equivalence relation on [0, 1]

by x ∼ y if x − y ∈ Q (check that this is indeed an equivalence relation). Then, [0, 1]
splits into pairwise disjoint equivalence classes whose union is the whole of [0, 1].
Invoke axiom of choice to get a set A that has exactly one point from each equiv-
alence class. Consider A + r , r ∈ Q ∩ [0, 1). If A + r and A + s intersect then we get
an x ∈ [0, 1] such that x = y + r = z + s (mod 1) for some y, z ∈ A . This implies that
y − z = r − s (mod 1) and hence that y ∼ z. So we must have y = z (as A has only
one element from each equivalence class) and that forces r = s (why?). Thus A + r ,
r ∈ Q ∩ [0, 1) are pairwise disjoint. Further given x ∈ [0, 1], there is a y ∈ A belonging
to the [[ x]]. Therefore x ∈ A + r where r = y − x or y − x + 1. Thus we have constructed
the set A whose countably many translates A + r , r ∈ Q ∩ [0, 1) are pairwise disjoint
and exhaustive! This answers question (1).
 1.5. RANDOM VARIABLES 9

Remark 1.21. There is a theorem to the effect that the axiom of choice is necessary
to show the existence of a non-measurable set (as an aside, we should perhaps not
have used the word ‘construct’ given that we invoke the axiom of choice).
(2) m does not extend to all subsets: The proof above shows in fact that m cannot
be extended to a translation invariant p.m. on all subsets. If we do not require trans-
lation invariance for the extended measure, the question becomes more difficult.
Note that there do exist probability measures on the σ-algebra of all subsets of
[0, 1], so one cannot say that there are no measures on all subsets. For example,
define Q( A ) = 1 if 0.4 ∈ A and Q( A ) = 0 otherwise. Then Q is a p.m. on the space
of all subsets of [0, 1]. Q is a discrete p.m. in hiding! If we exclude such measures,
then it is true that some subsets have to be omitted to define a p.m. You may find
the proof for the following general theorem in Billingsley, p. 46 (uses axiom of choice
and continuum hypothesis).
Fact 1.22. There is no p.m. on the σ-algebra of all subsets of [0, 1] that gives zero
probability to singletons.
P
Say that x is an atom of P if P({ x}) > 0 and that P is purely atomic if atoms P({ x}) =
1. The above fact says that if P is defined on the σ-algebra of all subsets of [0, 1], then
P must be have atoms. It is not hard to see that in fact P must be purely atomic.
P
To see this let Q( A ) = P( A ) − x∈ A P({ x}). Then Q is a non-negative measure without
atoms. If Q is not identically zero, then with c = Q([0, 1])−1 , we see that cQ is a p.m.
without atoms, and defined on all subsets of [0, 1], contradicting the stated fact.
Remark 1.23. This last manipulation is often useful and shows that we can write
any probability measure as a convex combination of a purely atomic p.m. and a
completely nonatomic p.m.

(3) Finitely additive measures If we relax countable additivity, strange things

happen. For example, there does exist a translation invariant (µ( A + x) = µ( A ) for all
A ⊂ [0, 1], x ∈ [0, 1], in particular, µ( I ) = | I |) finitely additive (µ( A ∪ B) = µ( A ) + µ(B)
for all A, B disjoint) p.m. defined on all subsets of [0, 1]! In higher dimensions, even
this fails, as shown by the mind-boggling
Banach-Tarski “paradox”: The unit ball in R3 can be divided into finitely many
(five, in fact) disjoint pieces and rearranged (only translating and rotating each piece)
into a ball of twice the original radius!!

1.5. Random variables

Definition 1.24. Let (Ω i , F i , P i ), i = 1, 2, be two probability spaces. A function T :
Ω1 → Ω2 is called an Ω2 -valued random variable if T −1 A ∈ F1 for any A ∈ F2 . Here
T −1 ( A ) := {ω ∈ Ω1 : T (ω) ∈ A } for any A ⊂ Ω2 .
Important cases are when Ω2 = R and F2 = B (R) (we just say “random variable”)
or Ω2 = Rd and F2 = B (Rd ) (“random vector”). When Ω2 = C [0, 1] with F2 its Borel
sigma algebra (under the sup-norm metric), T is called a “stochastic process”. When
Ω2 is itself the space of all locally finite countable subsets of Rd (with Borel sigma
algebra in an appropriate metric) , we call T a “point process”. In genetics or popula-
tion biology one looks at genealogies, and then we have tree-valued random variables
etc. etc.
Remark 1.25. Some remarks.
10 1. MEASURE THEORY

(1) If T : Ω1 → Ω2 is any function, then given a σ-algebra G on Ω2 , the “pull-

back” {T −1 A : A ∈ G } is the smallest σ-algebra on Ω1 w.r.t. which T is
measurable (if we fix G on Ω2 ) . Conversely, given a σ-algebra F on Ω1 ,
the “push-forward” { A ⊂ Ω2 : T −1 A ∈ F } is the largest σ-algebra on Ω2
w.r.t. which T is measurable (if we fix F on Ω1 ). These properties are
simple consequences of the fact that T −1 ( A ) c = T −1 ( A c ) and T −1 (∪ A n ) =
∪n T −1 ( A n ).
(2) If S generates F2 , i.e., σ(S ) = F2 , then it suffices to check that T −1 A ∈ F1
for any A ∈ S .
Example 1.26. Consider ([0, 1], B ). Any continuous function T : [0, 1] → R is a ran-
dom variable. This is because T −1 (open) = open and open sets generate B (R). Exer-
cise: Show that T is measurable if it is any of the following. (a) Lower semicontinu-
ous, (b) Right continuous, (c) Non-decreasing, (d) Linear combination of measurable
functions, (e) lim sup of a countable sequence of measurable functions. (a) supremum
of a countable family of measurable functions.

Push forward of a measure: If T : Ω1 → Ω2 is a random variable, and P is a p.m.

on (Ω1 , F1 ), then defining Q( A ) = P(T −1 A ), we get a p.m Q, on (Ω2 , F2 ). Q, often
denoted PT −1 is called the push-forward of P under T .
The reason why Q is a measure is that if A n are pairwise disjoint, then T −1 A n
are pairwise disjoint. However, note that if B n are pairwise disjoint in Ω1 , then
T (B n ) are in general not disjoint. This is why there is no “pull-back measure” in
general (unless T is one-one, in which case the pull-back is just the push-forward
under T −1 !)
When (Ω2 , F2 ) = (R, B ), the push forward (a Borel p.m on R) is called the dis-
tribution of the r.v. T . If T = (T1 , . . . , T d ) is a random vector, then the pushforward,
a Borel p.m. on Rd is called the distribution of T or as the joint distribution of
T1 , . . . , T d .

1.6. Borel Probability measures on Euclidean spaces

Given a Borel p.m. µ on Rd , we define its cumulative distribution functions
(CDF) to be Fµ ( x1 , . . . , xd ) = µ ((−∞, x1 ] × . . . × (−∞, xd ]). Then, by basic properties of
probability measures, Fµ : Rd → [0, 1] (i) is non-decreasing in each co-ordinate, (ii)
Fµ ( x) → 0 if max i x i → −∞, Fµ ( x) → 1 if min i x i → +∞, (iii) Fµ is right continuous in
each co-ordinate.
Two natural questions. Given an F : Rd → [0, 1] satisfying (i)-(iii), is there neces-
sarily a Borel p.m. with F as its CDF? If yes, is it unique?
If µ and ν both have CDF F , then for any rectangle R = (a 1 , b 1 ] × . . . × (a d , b d ],
µ(R ) = ν(R ) because they are both determined by F . Since these rectangles form a
π-system that generate the Borel σ-algebra, µ = ν on B .
What about existence of a p.m. with CDF equal to F ? For simplicity take d = 1.
One boring way is to define µ(a, b] = F ( b) − F (a) and then go through Caratheodary
construction. But all the hard work has been done in construction of Lebesgue mea-
sure, so no need to repeat it!
Consider the probability space ((0, 1), B , m) and define the function T : (0, 1) → R
by T ( u) := inf{ x : F ( x) ≥ u}. When F is strictly increasing and continuous, T is just
the inverse of F . In general, T is non-decreasing, left continuous. Most importantly,
 1.7. EXAMPLES OF PROBABILITY MEASURES ON THE LINE 11

T ( u) ≤ x if and only if F ( x) ≥ u. Let µ := m T −1 be the push-forward of the Lebesgue

measure under T . Then,
µ(−∞, x] = m { u : T ( u) ≤ x} = m{ u : F ( x) ≥ u} = m(0, F ( x)] = F ( x).
Thus, we have produced a p.m. µ with CDF equal to F . Thus p.m.s on the line are
in bijective correspondence with functions satisfying (i)-(iii). Distribution functions
(CDFs) are a useful but dispensable tool to study measures on the line, because we
have better intuition in working with functions than with measures.
Exercise 1.27. Do the same for Borel probability measures on Rd .

1.7. Examples of probability measures on the line

There are many important probability measures that occur frequently in proba-
bility and in the real world. We give some examples below and expect you to famil-
iarize yourself with each of them.
Rx
Example 1.28. The examples below have CDFs R of the form F ( x) = −∞ f ( t) dt where
f is a non-negative integrable function with f = 1. In such cases f is called the den-
sity or pdf (probability density function). Clearly F is continuous and non-decreasing
and tends to 0 and 1 at ∞ and −∞ respectively. Hence, there do exist probability
measures on R with the corresponding density.
(1) Normal distribution. For fixed a ∈ R and σ2 > 0, N (a, σ2 ) is the p.m. on
2 2
R with density p1 e−( x−a) /2σ du. F is clearly increasing and continuous
σ 2π
and F (−∞) = 0. That F (+∞) = 1 is not so obvious but true!
(2) Gamma distribution with shape parameter α > −1 and scale parameter
α−1
λ > 0 is the p.m. with density f ( x) = λΓ(α) xα−1 e−λ x for x > 0.
(3) Exponential distribution. Exponential(λ) is the p.m. with density f ( x) =
λ e−λ x for x ≥ 0 and f ( x) = 0 if x < 0. This is a special case of Gamma distri-
bution, but important enough to have its own name.
(4) Beta distribution. For parameters a > −1, b > −1, the Beta(a, b) distribution
is the p.m. with density B(a, b)−1 xa−1 (1 − x)b−1 for x ∈ [0, 1]. Here B(a, b) is
the beta function, equal to ΓΓ((aa)+ b)
Γ( b) . (Why does it integrate to 1?).
(5) Uniform distribution on [a, b] is the p.m. with density f ( x) = b−1 a for x ∈
[a, b]. For example, with a = 0, b = 1, this is a special case of the Beta
distribution.
1
(6) Cauchy distribution. This is the p.m. with density π(1+ x2 )
on the whole line.
Unlike all the previous examples, this distribution has “heavy tails”
You may have seen the following discrete probability measures. They are very
important too and will recur often.
P
Example 1.29. The examples below have CDFs of the form F ( x) = u i ≤ x p( x i ) dt,
where { x i } is a fixed countable set, and p( x i ) are non-negative numbers that add to
one. In such cases p is called the pmf (probability density function). and from what
we have shown, there do exist probability measures on R with the corresponding
density or CDF.
¡ ¢ distribution. Binomial( n, p), with n ∈ N and p ∈ [0, 1], has the pmf
(1) Binomial
p( k) = nk p k q n−k for k = 0, 1, . . . , n.
(2) Bernoulli distribution. p(1) = p and p(0) = 1 − p for some p ∈ [0, 1]. Same as
Binomail(1, p).
12 1. MEASURE THEORY

k
(3) Poisson(λ) distribution with parameter λ ≥ 0 has p.m.f p( k) = e−λ λk! for
k = 0, 1, 2, . . ..
(4) Geometric( p) distribution with parameter p ∈ [0, 1] has p.m.f p( k) = q k p for
k = 0, 1, 2, . . ..

1.8. A metric on the space of probability measures on Rd

What kind of space is P (Rd ) (the space of p.m.s on Rd )? It is clearly a convex set
(this is true for p.m.s on any sample space and σ-algebra).
We saw that for every Borel p.m. on Rd there is associated a unique CDF. This
suggests a way of defining a distance function on P (Rd ) using their CDFs. Let
D (µ, ν) = sup x∈Rd |Fµ ( x) − Fν ( x)|. Since CDFs are bounded between 0 and 1, this is
well-defined and one can easily check that it gives a metric on P (Rd ).
Is this the metric we want to live with? For a ∈ Rd , we denote by δa the p.m.
for which δa ( A ) = 1 if A 3 a and 0 otherwise (although this p.m. can be defined on
all subsets, we just look at it as a Borel measure). If a 6= b, it is easy to see that
D (δa , δb ) = 1. Thus, even when a n → a in Rd , we do not get convergence of δa n to δa .
This is an undesirable feature and hence we would like a weaker metric.

Definition 1.30. For µ, ν ∈ P (Rd ), define the Lévy distance between them as (here
1 = (1, 1, . . . , 1))
d (µ, ν) := inf{ u > 0 : Fµ ( x + u1) + u ≥ Fν ( x), Fν ( x + u1) + u ≥ Fµ ( x) ∀ x ∈ Rd }.
d
If d (µn , µ) → 0, we say that µn converges weakly to µ and write µn → µ. [...breathe
slowly and meditate on this definition for a few moments...]

First of all, d (µ, ν) ≤ 1. That d is indeed a metric is an easy exercise. If a n →

a in Rd , does δa n converge to δa ? Indeed d (δa , δb ) = (max i | b i − a i |) ∧ 1 and hence
d (δa n , a) → 0.

Exercise 1.31. Let µn = n1 nk=1 δk/n . Show directly by definition that d (µn , m) → 0.
P

What about D (µn , µ)?

How does convergence in the metric d show in terms of CDFs?

d
Proposition 1.32. µn → µ if and only if Fµn ( x) → Fµ ( x) for all continuity points x of
Fµ .
d
P ROOF. Suppose µn → µ. Let x ∈ Rd and fix u > 0. Then for large enough n, we
have Fµ ( x + u1) + u ≥ Fµn ( x), hence lim sup Fµn ( x) ≤ Fµ ( x + u1) + u for all u > 0. By
right continuity of Fµ , we get lim sup Fµn ( x) ≤ Fµ ( x). Further, Fµn ( x) + u ≥ Fµ ( x − u1)
for large n, hence lim inf Fµn ( x) ≥ Fµ ( x − u) for all u. If x is a continuity point of Fµ ,
we can let u → 0 and get lim inf Fµn ( x) ≥ Fµ ( x). Thus Fµn ( x) → Fµ ( x).
For simplicity let d = 1. Suppose F n → F at all continuity points of F . Fix any
u > 0. Find continuity points (of F ) x1 < x2 < . . . < xm such that x i+1 ≤ x i + u. This can
be done because continuity points are dense. Fix N so that d (µn , µ) < u for n ≥ N .
Henceforth, let n ≥ N .
If x ∈ R, then either x ∈ [ x j−1 , x j ] for some j or else x < x1 or x > x1 . First suppose
x ∈ [ x j−1 , x j ]. Then
F ( x + u) ≥ F ( x j ) ≥ F n ( x j ) − u ≥ F n ( x) − u, F n ( x + u) ≥ F n ( x j ) ≥ F ( x j ) − u ≥ F ( x) − u.
 1.9. COMPACT SUBSETS OF P (Rd ) 13

If x < x1 , then F ( x + u) + u ≥ u ≥ F ( x1 ) ≥ F n ( x1 ) − u. Similarly the other requisite

inequalities, and we finally have
F n ( x + 2 u) + 2 u ≥ F ( x) and F ( x + 2 u) + 2 u ≥ F n ( x).
Thus d (µn , µ) ≤ u. Hence d (µn , µ) → 0. ■

1.9. Compact subsets of P (Rd )

Often we face problems like the following. A functional L : P (Rd ) → R is given,
and we would like to find the p.m. µ that minimizes L(µ). By definition, we can find
nearly optimal p.m.s µn satisfying L(µn ) − n1 ≤ infν L(ν). Then we might expect that
if some subsequence µn k converged to a p.m. µ, then that µ might be the optimal
solution we are searching for. Thus we are faced with the question of characteriz-
ing compact subsets of P (Rd ), so that existence of convergent subsequences can be
asserted.
Looking for a convergent subsequence: Let µn be a sequence in P (Rd ). We
would like to see if a convergent subsequence can be extracted. Write F n for Fµn .
For any fixed x ∈ Rd , F n ( x) is a bounded sequence of reals and hence we can find a
subsequence { n k } such that F n k ( x) converges.
Fix a dense subset S = { x1 , x2 , . . .} of Rd . Then, by the observation above, we can
find a subsequence { n 1,k }k such that F n1,k ( x1 ) converges to some number in [0, 1] that
we shall denote G ( x1 ). Then extract a further subsequence { n 2,k }k ⊂ { n 1,k }k such that
F n2,k ( x2 ) → G ( x2 ), another number in [0, 1]. Of course, we also have F n2,k ( x1 ) → G ( x1 ).
Continuing this way, we get subsequences { n 1,k } ⊃ { n 2,k } ⊃ . . . { n `,k } . . . such that for
each `, as k → ∞, we have F n`, j ( x j ) → G ( x j ) for each j ≤ `.
The diagonal sbsequence { n `,` } is ultimately the subsequence of each of the above
obtained subsequences and therefore, F n`,` ( x j ) → G ( x j ) for all j .
To define the limiting function on the whole line, set F ( x) := inf{G ( x j ) : j for which x j >
x}. F is well defined, takes values in [0, 1] and is non-decreasing. It is also right-
continuous, because if yn ↓ y, then for any j for which x j > y, it is also true that
x j > yn for sufficiently large n. Thus lim infn→∞ G ( yn ) ≤ inf G ( x j ) = F ( y). Lastly,
xj>y
if y is any continuity point of F , then for any δ > 0, we can find i, j such that
y − δ < x i < y < x j < y + δ. Therefore
F ( y−δ) ≤ G ( x i ) = lim F n`,` ( x i ) ≤ lim inf F n`,` ( y) ≤ lim sup F n`,` ( y) ≤ lim F n`,` ( x j ) = G ( x j ) ≤ F ( y+δ).
The equalities are by prperty of the subsequence { n `,` }, the inner two inequalities
are obvious, and the outer two inequalities follow from the definition of F in terms
of G (and the fact that G is nondecreasing). Since F is continuous at y, we get
lim F n`,` ( y) = F ( y).
If only we could show that F (+∞) = 1 and F (−∞) = 0, then F would be the CDF
d
of some p.m. µ and we would immediately get µn → µ. But this is false in general!
Example 1.33. Consider δn . Clearly Fδn ( x) → 0 for all x if n → +∞ and Fδn ( x) → 1
for all x if n → −∞. Even if we pass to subsequences, the limiting function is identi-
cally zero or identically one, and neither of these is a CDF of a p.m. The problem is
that mass escapes to infinity. To get weak convergence to a probability measure, we
need to impose a condition to avoid this sort of situation.
Definition 1.34. A family {µα }α∈ I ⊂ P (Rd ) is said to be tight if for any ² > 0, there is
a compact set K ² ⊂ Rd such that µα (K ² ) ≥ 1 − ² for all α ∈ I .
14 1. MEASURE THEORY

Example 1.35. Suppose the family has only one p.m. µ. Since [− n, n]d increase to
Rd , given ² > 0, for a large enough n, we have µ([− n, n]d ) ≥ 1 − ². Hence {µ} is tight.
If the family is finite, tightness is again clear.
Take d = 1 and let µn be p.m.s with F n ( x) = F ( x − n) (where F is a fixed CDF),
then {µn } is not tight. This is because given any [− M, M ], if n is large enough,
µn ([− M, M ]) can be made arbitrarily small. Similarly {δn } is not tight.

Theorem 1.36 (Helly’s selection principle). (a) A sequence of probability measures on

Rd is tight if and only if every subsequence has a further subsequence that converges
weakly. (b) Equivalently a subset of P (Rd ) is precompact if and only if it is tight.

P ROOF. (a) If µn is a tight sequence in P (Rd ), then any subsequence is also

tight. By the earlier discussion, given any subsequence { n k }, we may extract a
further subsequence n `,k and find a non-decreasing right continuous function F
(taking values in [0, 1]) such that F n`,k ( x) → F ( x) for all continuity points x of F .
Fix A > 0 such that µn [− A, A ] ≥ 1 − ² and such that A is a continuity point of F .
Then F ( A ) = limk→∞ F n`,k ( A ) ≥ 1 − ². Thus F (+∞) = 1. Similarly one can show that
d
F (−∞) = 0. This shows that F = Fµ for some µ ∈ P (Rd ) and thus µn`,k → µ as k → ∞.
Conversely, if the sequence {µn } is not tight, then for any A > 0, we can find an
infinite sequence n k such that µn k (− A, A ) < 1 − ² (why?). Then, either F n k ( A ) < 1 − 2²
for infinitely many k or F n k (− A ) < 2² . Thus, for any A > 0, we have F ( A ) < 1 − 2² or
F (− A ) < 2² . Thus F is not a CDF of a p.m., and we see that the subsequence { n k } has
no further subsequence than can converge to a probability measure.
(b) Standard facts about convergence in metric spaces and part (a).
■

1.10. Absolute continuity and singularity

How wild can the jumps of a CDF be? If µ is a p.m. on R with CD F that has a
jump at x, that means µ x = F ( x) − F ( x−) > 0. Since the total probability is one, there
can be atmost n jumps of size n1 or more. Putting them together, there can be atmost
countably many jumps. In particular F is continuous on a dense set. Let J be the set
P
of all jumps of F . Then, F = Fatom + Fcts where Fatom ( x) := x∈ J (F ( x) − F ( x−)) and
Fcts = F −Fatom . Clearly, Fcts is a continuous non-decreasing function, while Fatom
is a non-decreasing continuous function that increases only in jumps (if J ∩ [a, b] = ;,
then Fatom (a) = Fatom ( b)).
If Fatom is not identically zero, then we can scale it up by c = (Fatom (+∞) −
Fatom (−∞))−1 to make it a CDF of a p.m. on R. Similarly for Fcts . This means,
we can write µ as cµatom + (1 − c)µcts where c ∈ [0, 1] and µatom is a purely atomic
measure (its CDF increases only in jumps) and µcts has a continuous CDF.

Definition 1.37. Two measures µ and ν on the same (Ω, F ) are said to be mutually
singular and write µ ⊥ ν if there is a set A ∈ F such that µ( A ) = 0 and ν( A c ) = 0.
We say that µ is absolutely continuous to ν and write µ ¿ µ if µ( A ) = 0 whenever
ν( A ) = 0.

Remark 1.38. (i) Singularity is reflexive, absolute continuity is not. If µ ¿ ν and

ν ¿ µ, then we say that µ and ν are mutually absolutely continuous. (ii) If µ ⊥ ν,
then we cannot also have µ ¿ ν (unless µ = 0). (iii) Given µ and ν, it is not necessary
that they be singular or absolutely continuous to one another.
 1.10. ABSOLUTE CONTINUITY AND SINGULARITY 15

Example 1.39. Uniform([0, 1]) and Uniform([1, 2]) are singular. Uniform([1, 3]) is
neither absolutely continuous nor singular to Uniform([2, 4]). Uniform([1, 2]) is ab-
solutely continuous to Uniform([0, 4]) but not conversely. All these uniforms are ab-
solutely continuous to Lebesgue measure. Any measure on the line that has an
atom (eg., δ0 ) is singular to Lebesgue measure. A p.m. on the line with density
(eg., N (0, 1)) is absolutely continuous to m. In fact N (0, 1) and m are mutually abso-
lutely continuous. However, the exponential distribution is absolutely continuous to
Lebesgue measure, but not conversely (since (−∞, 0), has zero probability under the
exponential distribution but has positive Lebesgue measure).
As explained above, a p.m on the line with atoms is singular (w.r.t m). This raises
the natural question of whether every p.m. with a continuous CDF is absolutely
continuous to Lebesgue measure? Surprisingly, the answer is No!
Example 1.40 (Cantor measure). Let K be the middle-thirds Cantor set. Con-
sider the canonical probability space ([0, 1], B , m) and the random variable X (ω) =
P∞ 2 X k (ω) X k (ω )
, where X k (ω) is the kth binary digit of ω (i.e., ω = ∞
P
k=1 3k k=1 2k
). Then X is
measurable (why?). Let µ := m X −1 be the pushforward.
Then, µ(K ) = 1, because X takes values in numbers whose ternary expansion
has no ones. Further, for any t ∈ K , X −1 { t} is a set with atmost two points and hence
has zero Lebsgue measure. Thus µ has not atoms and must have a continuous CDF.
Since µ(K ) = 1 but m(K ) = 0, we also see that µ ⊥ m.
Exercise 1.41 (Alternate construction of Cantor measure). Let K 1 = [0, 1/3] ∪
[2/3, 1], K 2 = [0, 1/9] ∪ [2/9, 3/9] ∪ [6/9, 7/9] ∪ [8/9, 1], etc., be the decreasing sequence of
compact sets whose intersection is K . Observe that K n is a union of 2n intervals each
of length 3−n . Let µn be the p.m. which is the “renormalized Lebesgue measure” on
K n . That is, µn ( A ) := 3n 2−n m( A ∩ K n ). Then each µn is a Borel p.m. Show that
d
µn → µ, the Cantor measure.
Example 1.42 (Bernoulli convolutions). We generalize the previous example.
For any λ > 1, define X λ : [0, 1] → R by X (ω) = ∞ λ−k X k (ω). Let µλ = m X λ−1 (did
P
k=1
you check that X λ is measurable?). For λ = 3, this is almost the same as 1/3-Cantor
measure, except that we have left out the irrelevant factor of 2 (so µ3 is a p.m. on
1
2 K := { x/2 : x ∈ K }) and hence is singular.
Exercise 1.43. For any λ > 2, show that µλ is singular w.r.t. Lebesgue measure.
For λ = 2, it is easy to see that µλ is just the Lebesgue measue on [0, 1/2]. Hence,
one might expect that µλ is absolutely continuous to Lebesgue measure for 1 < λ < 2.
This is false! Paul Erdős showed that µλ is singular to Lebesgue measure whenever
λ is a Pisot-Vijayaraghavan number, i.e., if λ is an algebraic number all of whose
conjugates have modulus less than one!! It is an open question as to whether these
are the only exceptions.

Theorem 1.44 (Radon Nikodym theorem). Suppose µ and ν are two measures
on (Ω, F ). Then µ ¿ ν if and only
R if there exists a non-negative measurable function
f : Ω → [0, ∞] such that µ( A ) = A f ( x) d ν( x) for all A ∈ F .
Remark 1.45. Then, f is called the density of µ with respect to ν. Note that the
statement of the theorem does not make sense because we have not defined what
ν
R
A f ( x ) d ( x ) means! That will come next class, and then, one of the two implications
16 1. MEASURE THEORY

of the theorem, namely, “if µ has a density w.r.t. µ, then µ ¿ ν” would become obvious.
The converse statement, called the Radon-Nikodym theorem is non-trivial and will
be proved in the measure theory class.

1.11. Expectation
Let (Ω, F , P) be a probability space. We define Expectation or Lebesgue integra-
tion on measure space in three steps.
(1) If X can be written as X = ni=1 c i 1 A i for some A i ∈ F , we say that X is a
P

simple r.v.. We define its expectation to be E[ X ] := ni=1 c i P( A i ).

P

(2) If X ≥ 0 is a r.v., we define E[ X ] := sup{E[S ] : S ≤ X is a simple, nonegative r.v.}.

Then, 0 ≤ E X ≤ ∞.
(3) If X is any r.v. (real-valued!), let X + := X 1 X ≥0 and X − := − X 1 X <0 so that
X = X + − X − (also observe that X + + X − = | X |). If both E[ X + ] and E[ X − ] are
finite, we say that X is integrable (or that E[ X ] exists) and define E[ X ] :=
E[ X + ] − E[ X − ].

Naturally, there are some arguments needed to complete these steps.

(1) In the first step, one should check that E[ X ] is well-defined, as a simple
r.v. can be represented as ni=1 c i 1 A i in many ways. It helps to note that
P

there is a unique way to write it in this form with A k p.w disjoint. Finite
additivity of P is used here.
(2) In addition, check that the expectation defined in step 1 has the properties
of positivity ( X ≥ 0 implies E[ X ] ≥ 0) and linearity (E[α X + βY ] = αE[ X ] +
βE[Y ]).
(3) In step 2, again we would like to check positivity and linearity. It is clear
that E[α X ] = αE[ X ] if X ≥ 0 is a r.v and α is a non-negative real number
(why?). One can also easily see that E[ X + Y ] ≥ E[ X ] + E[Y ] using the def-
inition. To show that E[ X + Y ] ≥ E[ X ] + E[Y ], one proves using countable
additivity of P -
Monotone convergence theorem (provisional version). If S n are non-negative
simple r.v.s that increase to X , then E[S n ] increases to E[ X ].
From this, linearity follows, since S n ↑ X and T n ↑ Y implies that S n +
T n ↑ X + Y . One point to check is that there do exist simple r.v S n , T n that
P 2n
increase to X , Y . For example, we can take S n (ω) = 2k=0 2kn 1 X (ω)∈[k2−n ,(k+1)2−n ) .
An additional remark: It is convenient to allow a r.v. to take the value
+∞ but adopt the convention that 0 · ∞ = 0 (infinite value on a set of zero
probability does not matter).
(4) In step 3, one assumes that both E[ X + ] and E[ X − ] are finite, which is equiv-
alent to assuming that E[| X |] < ∞. In other words, we deal with “absolutely
integrable r.v.s” (no “conditionally convergent” stuff for us).

Let us say “ X = Y a.s” or “ X < Y a.s” etc., to mean that P( X = Y ) = 1, P ( X < Y ) =

1 etc. We may also use a.e. (almost everywhere) or w.p.1 (with probability one) in
place of a.s (almost surely). To summarize, we end up with an expectation operator
that has the following properties.
(1) Linearity: X , Y integrable imples α X + βY is also integrable and E[α X +
βY ] = αE[ X ] + βE[Y ].
 1.13. LEBESGUE INTEGRAL VERSUS RIEMANN INTEGRAL 17

(2) Positivity: X ≥ 0 implies E[ X ] ≥ 0. Further, if X ≥ 0 and P( X = 0) < 1, then

E[ X ] > 0. As a consequence, whenever X ≤ Y and E[ X ], E[Y ] exist, then
E[ X ] ≤ E[Y ] with equality if and only if X = Y a.s.
(3) If X has expectation, then |E X | ≤ E| X |.
(4) E[1 A ] = P( A ), in particular, E[1] = 1.

1.12. Limit theorems for Expectation

Theorem 1.46 (Monotone convergence theorem (MCT)). Suppose X n , X are non-
negative r.v.s and X n ↑ X a.s. Then E[ X n ] ↑ E[ X ]. (valid even when E[ X ] = +∞).
Theorem 1.47 (Fatou’s lemma). Let X n be non-negative r.v.s. Then E[lim inf X n ] ≤
lim inf E[ X n ].
Theorem 1.48 (Dominated convergence theorem (DCT)). Let | X n | ≤ Y where Y is a
non-negative r.v. with E[Y ] < ∞. If X n → X a.s., then, E[| X − n − X |] → 0 and hence
we also get E[ X n ] → E[ X ].
Assuming MCT, the other two follow easily. For example, to prove Fatou’s lemma,
just define Yn = infn≥k X n and observe that Yk s increase to lim inf X n a.s and hence
by MCT E[Yk ] → E[lim inf X n ]. Since X n ≥ Yn for each n, we get lim inf E[ X n ] ≥
lim inf E[Yn ] = E[lim inf X n ].
To prove DCT, first note that | X n | ≤ Y and | X | ≤ Y a.s. Consider the sequence of
non-negative r.v.s 2Y −| X n − X | that converges to 2Y a.s. Then, apply Fatou’s lemma
to get
E[2Y ] = E[lim inf(2Y −| X n − X |)] ≤ lim inf E[2Y −| X n − X |] = E[2Y ]−lim sup E[| X n − X |].
Thus lim sup E[| X n − X |] = 0. Further, |E[ X n ] − E[ X ]| ≤ E[| X n − X |] → 0.

1.13. Lebesgue integral versus Riemann integral

Consider the probability space ([0, 1], B , m) (note that this is the Lebesgue σ-
algebra, not Borel!) and a function f : [0, 1] → R. Let
n n
1 2X−1 1 2X−1
Un := max f ( x ), U n := min f ( x)
2n k=0 k
≤ x≤ k2+n1 2n k=0 k
≤ x≤ k2+n1
2n 2n

be the upper and lower Riemann sums. Then, L n ≤ Un and Un decrease with n
while L n increase. If lim Un = lim L n , we say that f is Riemann integrable and this
common limit is defined to be the Riemann integral of f . The question of which
functions are indeed Riemann integrable is answered precisely by
Lebesgue’s theorem on Riemann integrals: A bounded function f is Riemann
integrable if and only if the set of discontinuity points has zero Lebesgue outer mea-
sure.
Next consider the Lebesgue integral E[ f ]. For this we need f to be Lebesgue
measurable in the first place. Clearly any bounded and measurable function is inte-
grable (why?). Plus, if f is continuous a.e., then f is measurable (why?). Thus, Rie-
mann integrable functions are also Lebesgue integrable (but not conversely). What
about the values of the two kinds of integrals? Define
n −1 n −1
à ! à !
2X 2X
g n ( x ) := max f ( x) 1 k ≤ x≤ k+1 , h n ( x) := min f ( x) 1 k ≤ x≤ k+1
k
≤ x≤ k2+n1 2n 2n k
≤ x≤ k2+n1 2n 2n
k=0 2n k=0 2n
18 1. MEASURE THEORY

so that E[ g n ] = Un and E[ h n ] = L n . Further, g n ( x) ↓ f ( x) and h n ( x) ↑ f ( x) at all

continuity points of f . By MCT, E[ g n ] and E[ h n ] converge to E[ f ], while by the
R1
assumed Riemann integrability L n and Un converge to 0 f ( x) dx (Riemann integral).
R1
Thus we must have E[ f ] = 0 f ( x) dx.
In short, when a function is Riemann integrable, it is also Lebesgue integrable,
and the integrals agree. But there are functions that are measurable but not a.e.
continuous. For example, consider the indicator function of a totally disconnected
set of positive Lebesgue measure (like a Cantor set where an α middle portion is
deleted at each stage, with α sufficiently small). Then at each point of the set, the
indicator function is discontinuous. Thus, Lebesgue integral is more powerful than
Riemann integral.

1.14. Lebesgue spaces:

1
Fix (Ω, F , P). For p ≥ 1, define k X k p := E[| X | p ] p for those r.v.s for which this
number is finite. Then k tX k p = tk X k p for t > 0, and Minkowski’s inequality gives
k X + Y k p ≤ k X k p + kY k p for any X and Y . However, k X k p = 0 does not imply X = 0
but only that X = 0 a.s. Thus, k · k p is a pseudo norm.
If we introduce the equivalence X ∼ Y if P( X = Y ) = 1, then for p ≥ 1 only k ·
k p becomes a genuine norm on the set of equivalence classes of r.v.s for which this
quantity is finite (the L p norm of an equivalence class is just k X k p for any X in the
equivalence class). It is known as “L p -space”. With this norm (and the corresponding
metric k X − Y k p , the space L p becomes a normed vector space. A non-trivial fact
(proof left to measure theory class) is that L p is a complete under this metric. A
normed vector space which is complete under the induced metric is called a Banach
space and L p spaces are the prime examples.
The most important are the cases p = 1, 2, ∞. In these cases, (we just write X in
place of [ X ])
q
k X −Y k1 := E[| X −Y |] k X −Y k2 := E[| X − Y |2 ] k X −Y k∞ := inf{ t : P(| X −Y | > t) = 0}.

Exercise 1.49. For p = 1, 2, ∞, check that k X − Y k p is a metric on the space L p :=

{[ X ] : k X k p < ∞} (here [ X ] denotes the equivalence class of X under the above equiv-
alence relation).

Especially special is the case p = 2, in which case the norm comes from an inner
product 〈[ X ], [Y ]〉 := E[ X Y ]. L2 is a complete inner product space, also known as a
Hilbert space. For p 6= 2, the L p norm does not come from an inner product as k · k p
does not satisfy the polarization identity k X + Y k2p + k X − Y k2p = 2k X k2p + 2kY k2p .

1.15. Some inequalities for expectations

The following inequalities are very useful. We start with the very general, but
intuitively easy to understand Jensen’s inequality. For this we recall two basic facts
about convex functions on R.
Let φ : (a, b) → R be a convex function. Then, (i) φ is continuous. (ii) Given any
u ∈ R, there is a line in the plane passing through the point ( u, φ( u)) such that the
line lies below the graph of φ. If φ is strictly convex, then the only place where the
 1.16. CHANGE OF VARIABLES 19

line and the graph of φ meet, is at the point ( u, φ( u)). Proofs for these facts may be
found in many books, eg., Rudin’s “Real and Complex Analysis” (ch. 3).
Lemma 1.50 (Jensen’s inequality). Let φ : R → R be a convex function. Let X be a r.v
on some probability space. Assume that X and φ( X ) both have expectations. Then,
φ(E X ) ≤ E[φ( X )]. The same assertion holds if φ is a convex function on some interval
(a, b) and X takes values in (a, b) a.s.
P ROOF. Let E[ X ] = a. Let y = m( x − a) + φ(a) be the ‘supporting line’ through
(a, φ(a)). Since the line lies below the graph of φ, we have m( X − a) + φ(a) ≤ φ( X ), a.s.
Take expectations to get φ(a) ≤ E [φ( X )]. ■
Lemma 1.51. (a) [Cauchy-Schwarz inequality] If X , Y are r.v.s on a probability space,
then E[ X Y ]2 ≤ E[ X 2 ]E[Y 2 ].
(b) [Hölder’s inequality] If X , Y are r.v.s on a probability space, then for any p, q ≥
1 satisfying p−1 + q−1 = 1, we have k X Y k1 ≤ k X k p kY k q .
P ROOF. Cauchy-Schwarz is a special case of Hölder with p = q = 2.
The proof of Hölder inequality follows by applying the inequality a p / p + b q / q ≥ ab
for a, b ≥ 0 to a = | X |/k X k p and b = Y /kY k q and taking expectations. The inequality
a p / p + b q / q ≥ ab is evident by noticing that the rectangle [0, a] × [0, b] (with area ab)
is contained in the union of the region{( x, y) : 0 ≤ x ≤ a, 0 ≤ y ≤ x p−1 } (with area a p / p)
and the region {( x, y) : 0 ≤ y ≤ b, 0 ≤ x ≤ y q−1 } (with area b q / q) simply because the
latter regions are the regions between the x and y axes (resp.) and curve y = x p−1
which is also the curve x = y q−1 since ( p − 1)( q − 1) = 1. ■
Lemma 1.52 (Minkowski’s inequality). For any p ≥ 1, we have k X + Y k p ≤ k X k p +
kY k p .
P ROOF. For the important cases of p = 1, 2, ∞, we know how to check this (for
p = 2, use Cauchy-Schwarz). For general p, one can get it by applying Hölder to an
appropriate pair of functions. We omit details (we might not use them, actually). ■

1.16. Change of variables

Lemma 1.53. ?? Let T : (Ω1 , F1 , P) → (Ω2 , F2 , Q) be measurable and Q = PT −1 . If
X is an integrable r.v. on Ω2 , then X ◦ T is an integrable r.v. on Ω1 and EP [ X ◦ T ] =
EQ [ X ].
P ROOF. For a simple r.v., X = ni=1 c i 1 A i , where A i ∈ F2 , it is easy to see that
P

X ◦ T = i=1 c i 1T −1 A i and by definition EP [ X ◦ T ] = ni=1 c i P{T −1 A i } = ni=1 c i Q{ A i }

Pn P P

which is precisely EQ [ X ]. Use MCT to get to positive r.v.s and then to general inte-
grable r.v.s. ■
Corollary 1.54. Let X i , i ≤ n, be random variables on a common probability space.
Then for any Borel measurable f : Rn → R, the value of E[ f ( X 1 , . . . , X n )] (if it exists)
depends only on the joint distribution of X 1 , . . . X n .
Remark 1.55. The change of variable result shows the irrelevance of the underlying
probability space to much of what we do. That is, in any particular situation, all
our questions may be about a finite or infinite collection of random variables X i .
Then, the answers depend only on the joint distribution of these random variables
and not any other details of the underlying probability space. For instance, we can
unambiguously talk of the expected value of Exp(λ) distribution when we mean the
20 1. MEASURE THEORY

expected value of a r.v having Exp(λ) distribution and defined on some probability
space.

RDensity: Let ν be a measure on (Ω, F ) and X : Ω → [0, ∞] a r.v. Then set µ( A ) :=

A X d ν. Clearly, µ is a measure, as countable additivity follows from MCT. Observe
that µ ¿ ν. If two given measures µ and ν are related in this way by a r.v. X ,
then we say that X is the density or Radon-Nikodym derivative of µ w.r.t ν and
dµ
sometimes write X = d ν . If it exists Radon-Nikodym derivative is unique (up to sets
of ν-measure zero). The Radon-Nikodym theorem asserts that whenever µ, ν are σ-
finite measures with µ ¿ ν, the Radon Nikodym derivative does exist. When µ is a
p.m on Rd and ν = m, we just refer to X as the pdf (probability density function) of µ.
We also abuse language to say that a r.v. has density if its distribution has density
w.r.t Lebesgue measure.

Exercise 1.56. Let X be a non-negative r.v on (Ω, F , P) and let Q( A ) = E 1[ X ] A X d P.

R
P
Then, Q is a p.m and for any non-negative r.v. Y , we have EQ [Y ] = EP [ X Y ]. The
same holds if Y is real valued and assumed to be integrable w.r.t Q (or Y X is as-
sumed to be integrable w.r.t P).

It is useful to know how densities transform under a smooth change of variables.

It is an easy corollary of the change of variable formula and well-known substitution
rules for computing integrals.

Corollary 1.57. Suppose X = ( X 1 , . . . , X n ) has density f (x) on Rn . Let T : Rn → Rn

be injective and continuously differentiable. Write U = T ◦ X . Then, U has density g
which is given by g(u) = f (T −1 u)| det( J [T −1 ](u))|, where [ JT −1 ] is the Jacobian of the
inverse map T −1 .
More generally, if we can write Rn = A 0 ∪ . . . ∪ A n , where A i are pairwise disjoint,
P( X ∈ A 0 ) = 0 and such that T i := T | A i are one-one for i = 1, 2, . . . n, then, g(u) =
f (T −1 u)| det( J [T −1 ](u))| where the i th summand is understood to vanish if u is
Pn
i =1 i i
not in the range of T i .

P ROOF. Step 1 Change of Lebesgue measure under T : For A ∈ B (Rn ), let µ( A ) :=

−1
A | det( J [T ](u))| dm( u). Then, as remarked earlier, µ is a Borel measure. For suf-
R

ficiently nice sets, like rectangles [a 1 , b 1 ] × . . . × [a n , b n ], we know from Calculus class

that µ( A ) = m(T −1 ( A )). Since rectangles generate the Borel sigma-algebra, and µ
and m ◦ T −1 agree on rectangles, by the π − λ theorem we get m ◦ T −1 = µ. Thus,
m ◦ T −1 is a measure with density given by | det( J [T −1 ](·))|.
Step 2 Let B be a Borel set and consider
Z
P(U ∈ B) = P( X ∈ T −1 B) = f ( x)1T −1 B ( x) d m( x)
Z Z
= f (T −1 u)1T −1 B (T −1 u) d µ( u) = f (T −1 u)1B ( u) d µ( u)

where the first equality on the second line is by the change of variable formula of
Lemma ??. Apply exercise 1.56 and recall that µ has density | det( J [T −1 ](u))| dm( u)
to get
Z Z
P(U ∈ B) = f (T −1 u)1B ( u) d µ( u) = f (T −1 u)1B ( u)| det( J [T −1 ](u))| dm( u)

which shows that U has density f (T −1 u)| det( J [T −1 ](u))|.

 1.17. DISTRIBUTION OF THE SUM, PRODUCT ETC. 21

To prove the second part, we do the same, except that in the first step, (using
P( X ∈ A 0 ) = 0, since m( A 0 ) = 0 and X has density) P(U ∈ B) = ∪ni=1 P( X ∈ T i−1 B) =
Pn R
i =1 f ( x)1T −1 B ( x) d m( x). The rest follows as before.
i
■

1.17. Distribution of the sum, product etc.

Suppose we know the joint distribution of X = ( X 1 , . . . , X n ). Then we can find the
distribution of any function of X because P( f ( X ) ∈ A ) = P( X ∈ f −1 ( A )). When X has
a density, one can get simple formulas for the density of the sum, product etc., that
are quite useful.
In the examples that follow, let us assume that the density RRis continuous.
R ¡R This¢ is
only for convenience, and so that we can invoke theorems like f= f ( x, y) d y dx.
Analogous theorems for Lebesgue integral will come later (Fubini’s theorem)...

Example 1.58. Suppose ( X , Y ) has density f ( x, y) on R2 . What is the distribution

R of
X ? Of X + Y ? Of X /Y ? We leave you to see that X has density g( x) = R f ( x, y) d y.
Assume that f is continuous so that the integrals
RR involved
R ¡R are also
¢ Riemann inte-
grals and you may use well known facts like f= f ( x, y) d y dx. The condition
of continuity is unnatural and the result is true if we only assume that f ∈ L1 (w.r.t.
Lebesgue measure on the plane). The right to write Lebesgue integrals in the plane
as iterated integrals will be given to us by Fubini’s theorem later.

Suppose ( X , Y ) has density f ( x, y) on R2 .

R R
(1) X has density f 1 ( x) = R f ( x, y) d y and Y has density f 2 ( y) = R f ( x, y) dx.
This is because, for any a < b, we have
 
Z Z Z
P( X ∈ [a, b]) = P(( X , Y ) ∈ [a, b] × R) = f ( x, y) dxd y =  f ( x, y) d y dx.
[a,b]×R [a,b] R

This shows that the ¡ p density of X is¢ indeed f 1 .

p p
(2) Density of X 2 is f 1 ( x) + f 1 (− x) /2 x for x > 0. Here we notice that T is
one-one on { x > 0} and { x < 0} (and { x = 0} has zero measure under f ), so the
second statement in the propositionR is used.
(3) The density of X + Y is g( t) = R f ( t − v, v) dx. To see this, let U = X + Y and
V = Y . Then the transformation is T ( x, y) = ( x + y, y). Clearly T −1 ( u, v) =
( u − v, v) whose Jacobian determinant is 1. Hence by corollary 1.57, we see
that (U, V ) has the density g( u, R v) = f ( u − v,Rv). Now the density of U can be
obtained like before as h( u) = g( u, v) dv = f ( u − v, v) dv.
(4) To get the density of X Y , we define (U, V ) = ( X Y , Y ) so that for v 6= 0, we
have T −1 ( u, v) = ( u/v, v) which has Jacobian determinant v−1 .
R
We claim that X + Y has the density g( t) = R f ( t − v, v) dx.

Exercise 1.59. (1) Suppose ( X , Y ) has a continuous density f ( x, y). Find the
density of X /Y . Apply to the case when ( X , Y ) has the standard bivariate
x 2 + y2
normal distribution with density f ( x, y) = (2π)−1 exp{− 2 }.
(2) Find the distribution of X + Y if ( X , Y ) has the standard bivariate normal
distribution.
(3) Let U = min{ X , Y } and V = max{ X , Y }. Find the density of (U, V ).
22 1. MEASURE THEORY

1.18. Mean, variance, moments

Given a r.v. or a random vector, expectations of various functions of the r.v give
a lot of information about the distribution of the r.v. For example,
Proposition 1.60. The numbers E[ f ( X )] as f varies over C b (R) determine the dis-
tribution of X .
P ROOF. Given any x ∈ Rn , we can recover F ( x) = E[1 A x ], where A x = (−∞, x1 ] ×
. . . × (−∞, xn ] as follows. For any δ > 0, let f ( y) = min{1, δ−1 d ( y, A xc +δ1 )}, where d is
the L ∞ metric on Rn . Then, f ∈ C b (R), f ( y) = 1 if y ∈ A x , f ( y) = 0 if y 6∈ A x+δ1 and
0 ≤ f ≤ 1. Therefore, F ( x) ≤ E[ f ◦ X ] ≤ F ( x + δ1). Let δ ↓ 0, invoke right continuity of
F to recover F ( x). ■

Much smaller sub-classes of functions are also sufficient to determine the distri-
bution of X .
Exercise 1.61. Show that the values E[ f ◦ X ] as f varies over the class of all smooth
(infinitely differentiable), compactly supported functions determine the distribution
of X .
Expectations of certain functionals of random variables are important enough to
have their own names.
Definition 1.62. Let X be a r.v. £ Then, E[ X ¤ ] (if it exists) is called the mean or
expected value of X . Var( X ) := E ( X − E X )2 is called the variance of X , and its
square root is called the standard deviation of X . The standard deviation measures
the spread in the values of X or one way of measuring the uncertainty in predicting
X . For any p > 0, if it exists, E[ X p ] is called the pth -moment of X . The function ψ
defined as ψ(λ) := E[ eλ X ] is called the moment generating function of X . Note that
the m.g.f of a non-negative r.v. exists for all λ < 0. It may exist for some λ > 0 also. A
similar looking object is the characteristic function of X , define by φ(λ) := E[ e iλ X ] :=
E[cos(λ X )] + i E[sin(λ X )]. This exists for all λ ∈ R.
For two random variables X , Y on the same probability space, we define their
covariance to be Cov( X , Y ) := E[( X − E X )(Y − EY )] = E[ X Y ] − E[ X ]E[Y ]. The corre-
Cov(X,Y)
lation coefficient is measured by p . The correlation coefficient lies in
Var(X)Var(Y)
[−1, 1] and measures the association between X and Y . A correlation of 1 implies
X = Y a.s while a correlation of −1 implies X = −Y a.s. Covariance and correlation
depend only on the joint distribution of X and Y .
Exercise 1.63. (i) Express the mean, variance, moments of aX + b in terms of the
same quantities for X .
(ii) Show that Var( X ) = E[ X 2 ] − E[ X ]2 .
(iii) Compute mean, variance and moments of the Normal, exponential and other
distributions defined in section 1.7.

Example 1.64 (The exponential distribution). Let X ∼ Exp(λ). Then, E[ X k ] =

x d µ( x) where µ is the p.m on R with density λ e−λ x (for x > 0). Thus, E[ X k ] =
R k
R k −λ x
x λe dx = λ−k k!. In particular, the mean is λ, the variance is 2λ2 − (λ)2 = λ2 . In
case of the normal distribution, check that the even moments are given by E[ X 2k ] =
Qk
j =1 (2 j − 1).
 1.18. MEAN, VARIANCE, MOMENTS 23

Remark 1.65 (Moment problem). Given a sequence of numbers (αk )k≥0 , is there
a p.m µ on R whose kth moment is αk ? If so, is it unique?
This is an extremely interesting question and its solution involves a rich in-
terplay of several aspects of classical analysis (orthogonal polynomials, tridiagonal
matrices, functional analysis, spectral theory etc). Note that there are are some
non-trivial conditions for (αk ) to be the moment sequence of a p.m. µ. For example,
α0 = 1, α2 ≥ α21 etc. In the homework you were asked to show that ((α i+ j )) i, j≤n should
be a n.n.d. matrix for every n. The non-trivial answer is that these conditions are
also sufficient!
Note that like proposition 1.60, the uniqueness question is asking whether E[ f ◦
X ], as f varies over the space of polynomials, is sufficient to determine the distribu-
tion of X . However, uniqueness is not true in general. In other words, one can find
two p.m µ and ν on R which have the same sequence of moments!
 CHAPTER 2

Independent random variables

2.1. Product measures

Definition 2.1. Let µ i be measures on (Ω i , F i ), 1 ≤ i ≤ n. Let F = F1 ⊗ . . . ⊗Fn be the
sigma algebra of subsets of Ω := Ω1 ×. . .×Ωn generated by all “rectangles” A 1 ×. . .× A n
with A i ∈ F i . Then, the measure µ on (Ω, F ) such that µ( A 1 × . . . × A n ) = ni=1 µ i ( A i )
Q

whenever A i ∈ F i is called a product measure and denoted µ = µ1 ⊗ . . . ⊗ µn .

The existence of product measures follows along the lines of the Caratheodary
construction starting with the π-system of rectangles. We skip details, but in the
cases that we ever use, we shall show existence by a much neater method in Propo-
sition 2.8. Uniqueness of product measure follows from the π − λ theorem because
rectangles form a π-system that generate the σ-algebra F1 ⊗ . . . ⊗ Fn .

Example 2.2. Let Bd , md denote the Borel sigma algebra and Lebesgue measure
on Rd . Then, Bd = B1 ⊗ . . . ⊗ B1 and md = m1 ⊗ . . . ⊗ m1 . The first statement is clear
(in fact Bd +d 0 = Bd ⊗ Bd 0 ). Regarding md , by definition, it is the unique measure for
which md ( A 1 × . . . × A n ) equals ni=1 m1 ( A i ) for all intervals A i . To show that it is
Q

the d -fold product of m1 , we must show that the same holds for any Borel sets A i .
Fix intervals A 2 , . . . , A n and let S := { A 1 ∈ B1 : md ( A 1 × . . . × A n ) = ni=1 m1 ( A i )}.
Q

Then, S contains all intervals (in particular the π-system of semi-closed intervals)
and by properties of measures, it is easy to check that S is a λ-system. By the π − λ
theorem, we get S = B1 and thus, md ( A 1 × . . . × A n ) = ni=1 m1 ( A i ) for all A 1 ∈ B1 and
Q

any intervals A 2 , . . . , A n . Continuing the same argument, we get that md ( A 1 × . . . ×

A n ) = ni=1 m1 ( A i ) for all A i ∈ B1 .
Q

The product measure property is defined in terms of sets. As always, it may be

written for measurable functions and we then get the following theorem.

Theorem 2.3 (Fubini’s theorem). Let µ = µ1 ⊗ µ2 be a product measure on Ω1 × Ω2

with the product σ-algebra. If f : Ω → R+ is either a non-negative r.v. or integrable
w.r.t µ, then,
(1) For every Rx ∈ Ω1 , the function y → f ( x, y) is F2 -measurable, and the func-
tion x → f ( x, y) d µ2 ( y) is F1 -measurable. The same holds with x and y
interchanged. Ã ! Ã !
(2) f ( z) d µ( z) = f ( x, y) d µ2 ( y) d µ1 ( x) = f ( x, y) d µ1 ( x) d µ2 ( y).
R R R R R
Ω Ω1 Ω2 Ω2 Ω1

P ROOF. Skipped. Attend measure theory class. ■

Needless to day (self: then why am I saying this?) all this goes through for finite
products of σ-finite measures.
25
26 2. INDEPENDENT RANDOM VARIABLES

Infinite product measures: Given (Ω i , F i , µ i ), i = 1, 2, . . ., let Ω := Ω1 × Ω2 × . . . and

let F be the sigma algebra generated by all finite dimensional cylinders A 1 × . . . ×
A n × Ωn+1 × Ωn+2 . . . with A i ∈ F i . Does there exist a “product measure” µ on F ?
For concreteness take all (Ω i , F i , µ i ) = (R, B , ν). What measure should the prod-
uct measure µ give to the set A × R × R × . . .? If ν(R) > 1, it is only reasonable to set
µ( A × R × R × . . .) to infinity, and if ν(R) < 1, it is reasonable to set it to 0. But then
all cylinders will have zero measure or infinite measure!! If ν(R) = 1, at least this
problem does not arise. We shall show that it is indeed possible to make sense of
infinite products of Thus, the only case when we can talk reasonably about infinite
products of measures is for probability measures.

2.2. Independence
Definition 2.4. Let (Ω, F , P) be a probability space. Let G1 , . . . , G k be sub-sigma
algebras of F . We say that G i are independent if for every A 1 ∈ G1 , . . . , A k ∈ G k , we
have P( A 1 ∩ A 2 ∩ . . . ∩ A k ) = P( A 1 ) . . . P( A k ).
Random variables X 1 , . . . , X n on F are said to be independent if σ( X 1 ), . . . , σ( X n )
are independent. This is equivalent to saying that P ( X i ∈ A i i ≤ k) = ki=1 P( X i ∈ A i )
Q

for any A i ∈ B (R).

Events A 1 , . . . , A k are said to be independent if 1 A 1 , . . . , 1 A k are independent.
This is equivalent to saying that P( A j 1 ∩ . . . ∩ A j ` ) = P( A j 1 ) . . . P( A j ` ) for any 1 ≤
j 1 < j 2 < . . . < j ` ≤ k.
In all these cases, an infinite number of objects (sigma algebras or random vari-
ables or events) are said to be independent if every finite number of them are inde-
pendent.

Some remarks are in order.

(1) As usual, to check independence, it would be convenient if we need check
the condition in the definition only for a sufficiently large class of sets. How-
ever, if G i = σ(S i ), and for every A 1 ∈ S 1 , . . . , A k ∈ S k if we have P( A 1 ∩ A 2 ∩
. . . ∩ A k ) = P( A 1 ) . . . P( A k ), we cannot conclude that G i are independent! If
S i are π-systems, this is indeed true (see below).
(2) Checking pairwise independence is insufficient to guarantee independence.
For example, suppose X 1 , X 2 , X 3 are independent and P( X i = +1) = P( X i =
−1) = 1/2. Let Y1 = X 2 X 3 , Y2 = X 1 X 3 and Y3 = X 1 X 2 . Then, Yi are pairwise
independent but not independent.

Lemma 2.5. If S i are π-systems and G i = σ(S i ) and for every A 1 ∈ S 1 , . . . , A k ∈ S k if

we have P( A 1 ∩ A 2 ∩ . . . ∩ A k ) = P( A 1 ) . . . P( A k ), then G i are independent.

P ROOF. Fix A 2 ∈ S 2 , . . . , A k ∈ S k and set F1 := {B ∈ G1 : P(B ∩ A 2 ∩ . . . ∩ A k ) =

P(B)P( A 2 ) . . . P( A k )}. Then F1 ⊃ S 1 by assumption and it is easy to check that F1
is a λ-system. By the π-λ theorem, it follows that F1 = G1 and we get the assump-
tions of the lemma for G1 , S 2 , . . . , S k . Repeating the argument for S 2 , S 3 etc., we get
independence of G1 , . . . , G k . ■

Corollary 2.6. (1) Random variables X 1 , . . . , X k are independent if and only if

P ( X 1 ≤ t 1 , . . . , X k ≤ t k ) = kj=1 P( X j ≤ t j ).
Q

(2) Suppose Gα , α ∈ I are independent. ³ Let I 1 , .´. . , I k be pairwise disjoint subsets

of I . Then, the σ-algebras F j = σ ∪α∈ I j Gα are independent.
 2.3. INDEPENDENT SEQUENCES OF RANDOM VARIABLES 27

(3) If X i, j , i ≤ n, j ≤ n i , are independent, then for any Borel measurable f i :

Rn i → R, the r.v.s f i ( X i,1 , . . . , X i,n i ) are also independent.

P ROOF. (1) The sets (−∞, t] form a π-system that generates B (R). (2) For j ≤ k,
let S j be the collection of finite intersections of sets A i , i ∈ I j . Then S j are π-systems
and σ(S j ) = F j . (3) Follows from (2) by considering G i, j := σ( X i, j ) and observing that
f i ( X i,1 , . . . , X i,k ) ∈ σ(G i,1 ∪ . . . ∪ G i,n i ). ■

So far, we stated conditions for independence in terms of probabilities if events. As

usual, they generalize to conditions in terms of expectations of random variables.

Lemma 2.7. (1) Sigma algebras G1 , . . . , G k are independent if and only if for
every bounded G i -measurable functions X i , 1 ≤ i ≤ k, we have, E[ X 1 . . . X k ] =
Qk
i =1 E[ X i ].
(2) In particular, random variables Z1 , . . . , Z k ( Z i is an n i dimensional random
vector) are independent if and only if E[ ki=1 f i ( Z i )] = ki=1 E[ f i ( Z i )] for any
Q Q

bounded Borel measurable functions f i : Rn i → R.

We say ‘bounded measurable’ just to ensure that expectations exist. The proof
goes inductively by fixing X 2 , . . . , X k and then letting X 1 be a simple r.v., a non-
negative r.v. and a general bounded measurable r.v.

P ROOF. (1) Suppose G i are independent. If X i are G i measurable then

it is clear that X i are independent and hence P( X 1 , . . . , X k )−1 = P X 1−1 ⊗
. . . ⊗ P X k−1 . Denote µ i := P X i−1 and apply Fubini’s theorem (and change of
variables) to get
Z k
c.o.v Y
E[ X 1 . . . X k ] = x i d (µ1 ⊗ . . . ⊗ µk )( x1 , . . . , xk )
Rk i =1
Z k
Z Y
Fub
= ... x i d µ1 ( x1 ) . . . d µk ( xk )
R R i =1
k Z k
Y c.o.v Y
= ud µ i ( u) = E[ X i ].
i =1 R i =1

Conversely, if E[ X 1 . . . X k ] = ki=1 E[ X i ] for all G i -measurable functions X i s,

Q

then applying to indicators of events A i ∈ G i we see the independence of the

σ-algebras G i .
(2) The second claim follows from the first by setting G i := σ( X i ) and observing
that a random variable X i is σ( Z i )-measurable if and only if X = f ◦ Z i for
some Borel measurable f : Rn i → R.
■

2.3. Independent sequences of random variables

First we make the observation that product measures and independence are
closely related concepts. For example,
An observation: The independence of random variables X 1 , . . . , X k is precisely the
same as saying that P ◦ X −1 is the product measure P X 1−1 ⊗ . . . ⊗ P X k−1 , where X =
( X 1 , . . . , X k ).
28 2. INDEPENDENT RANDOM VARIABLES

Consider the following questions. Henceforth, we write R∞ for the countable

product space R × R × . . . and B (R∞ ) for the cylinder σ-algebra generated by all fi-
nite dimensional cylinders A 1 × . . . × A n × R × R × . . . with A i ∈ B (R). This notation is
justified, becaue the cylinder σ-algebra is also the Borel σ-algebra on R∞ with the
product topology.
Question 1: Given µ i ∈ P (R), i ≥ 1, does there exist a probability space with inde-
pendent random variables X i having distributions µ i ?
Question 2: Given µ i ∈ P (R), i ≥ 1, does there exist a p.m µ on (R∞ , B (R∞ )) such
that µ( A 1 × . . . × A n × R × R × . . .) = ni=1 µ i ( A i )?
Q

Observation: The above two questions are equivalent. For, suppose we answer the
first question by finding an (Ω, F , P) with independent random variables X i : Ω → R
such that X i ∼ µ i for all i . Then, X : Ω → R∞ defined by X (ω) = ( X 1 (ω), X 2 (ω), . . .) is
measurable w.r.t the relevant σ-algebras (why?). Then, let µ := P X −1 be the pushfor-
ward p.m on R∞ . Clearly
µ( A 1 × . . . × A n × R × R × . . . ) = P ( X 1 ∈ A1, . . . , X n ∈ A n )
Yn Yn
= P( X i ∈ A i ) = µ i ( A i ).
i =1 i =1
Thus µ is the product measure required by the second question.
Conversely, if we could construct the product measure on (R∞ , B (R∞ )), then we
could take Ω = R∞ , F = B (R∞ ) and X i to be the i th co-ordinate random variable.
Then you may check that they satisfy the requirements of the first question.
The two questions are thus equivalent, but what is the answer?! It is ‘yes’, of
course or we would not make heavy weather about it.
Proposition 2.8 (Daniell). Let µ i ∈ P (R), i ≥ 1, be Borel p.m on R. Then, there exist
a probability space with independent random variables X 1 , X 2 , . . . such that X i ∼ µ i .
P ROOF. We arrive at the construction in three stages.
(1) Independent Bernoullis: Consider ([0, 1], B , m) and the random vari-
ables X k : [0, 1] → R, where X k (ω) is defined to be the kth digit in the binary
expansion of ω. For definiteness, we may always take the infinite binary ex-
pansion. Then by an earlier homework exercise, X 1 , X 2 , . . . are independent
Bernoulli(1/2) random variables.
(2) Independent uniforms: Note that as a consequence, on any probability
−n
space, if Yi are i.i.d. Ber(1/2) variables, then U := ∞
P
n=1 2 Yn has uniform
distribution on [0, 1]. Consider again the canonical probability space and
the r.v. X i , and set U1 := X 1 /2 + X 3 /23 + X 5 /25 + . . ., U2 := X 2 /2 + X 6 /22 + . . .,
etc. Clearly, U i are i.i.d. U[0,1].
(3) Arbitrary distributions: For a p.m. µ, recall the left-continuous inverse
G µ that had the property that G µ (U ) ∼ µ if U ∼ U [0, 1]. Suppose we are
given p.m.s µ1 , µ2 , . . .. On the canonical probability space, let U i be i.i.d
uniforms constructed as before. Define X i := G µ i (U i ). Then, X i are inde-
pendent and X i ∼ µ i . Thus we have constructed an independent sequence
of random variables having the specified distributions. ■

Sometimes in books one finds construction of uncountable product measures too.

It has no use. But a very natural question at this point is to go beyond independence.
We just state the following theorem which generalizes the previous proposition.
 2.3. INDEPENDENT SEQUENCES OF RANDOM VARIABLES 29

Theorem 2.9 (Kolmogorov’s existence theorem). For each n ≥ 1 and each 1 ≤

i 1 < i 2 < . . . < i n , let µ i 1 ,...,i n be a Borel p.m on Rn . Then there exists a unique proba-
bility measure µ on (R∞ , B (R∞ )) such that
µ( A 1 × . . . × A n × R × R × . . .) = µ i 1 ,...,i n ( A 1 × . . . × A n ) for all n ≥ 1 and all A i ∈ B (R),
if and only if the given family of probability measures satisfy the consistency condition
µ i 1 ,...,i n ( A 1 × . . . × A n−1 × R) = µ i 1 ,...,i n−1 ( A 1 × . . . × A n−1 )
for any A k ∈ B (R) and for any 1 ≤ i 1 < i 2 < . . . < i n and any n ≥ 1.
30 2. INDEPENDENT RANDOM VARIABLES

2.4. Some probability estimates

Lemma 2.10 (Borel Cantelli lemmas). Let A n be events on a common probability
space.
P
(1) If n P( A n ) < ∞, then P( A n i.o) = 0.
P
(2) If A n are independent and n P( A n ) = ∞, then P( A n i.o) = 1.

(1) For any N , P ∪∞ A ≤ ∞

¡ ¢ P
P ROOF. n= N n n= N P( A n ) which goes to zero as
N → ∞. Hence P(lim sup A n ) = 0.
(2) For any N < M , P(∪nM= N A n ) = 1 − nM= N P( A nc ). Since n P( A n ) = ∞, it fol-
Q P
QM QM
lows that n= N (1 − P( A n )) ≤ n= N e−P( A n ) → 0, for any fixed N as M → ∞.
Hence P ∪∞
¡ ¢
A = 1 for all N , implying that P( A n i.o) = 1.
n= N n
■

Lemma 2.11 (First and second moment methods). Let X ≥ 0 be a r.v.

(1) (Markov’s inequality a.k.a first moment method) For any t > 0, we
have P( X ≥ t) ≤ t−1 E[ X ].
(2) (Paley-Zygmund inequality a.k.a second moment method) For any
non-negative r.v. X ,

E[ X ]2 E[ X ]2
( i ) P ( X > 0) ≥ . ( ii ) P ( X > αE[ X ]) ≥ (1 − α)2 .
E[ X 2 ] E[ X 2 ]

P ROOF. (1) t1 X ≥ t ≤ X . Positivity of expectations gives the inequality.

(2) E[ X ]2 = E[ X 1 X >0 ]2 ≤ E[ X 2 ]E[1 X >0 ] = E[ X 2 ]P( X > 0). Hence the first in-
equality follows. The second inequality is similar. Let µ = E[ X ]. By Cauchy-
Schwarz, we have E[ X 1 X >αµ ]2 ≤ E[ X 2 ]P( X > αµ). Further, µ = E[ X 1 X <αµ ]+
E[ X 1 X >αµ ] ≤ αµ + E[ X 1 X >αµ ], whence, E[ X 1 X >αµ ] ≥ (1 − α)µ. Thus,

E[ X 1 X >αµ ]2 E[ X ]2
P( X > αµ) ≥ ≥ (1 − α)2 . ■
E[ X 2 ] E[ X 2 ]

Remark 2.12. Applying these inequalities to other functions of X can give more
information. For example, if X has finite variance, P(| X − E[ X ]| ≥ t) = P(| X − E[ X ]|2 ≥
t2 ) ≤ t−2 Var( X ), which is called Chebyshev’s inequality. Higher the moments that
exist, better the asymptotic tail bounds that we get. For example, if E[ eλ X ] < ∞ for
some λ > 0, we get exponential tail bounds by P( X > t) = P( eλ X < eλ t ) ≤ e−λ t E[ eλ X ].

2.5. Applications of first and second moment methods

The first and second moment methods are immensely useful. This is somewhat
surprising, given the very elementary nature of these inequalities, but the following
applications illustrate the ease with which they give interesting results.

Application 1: Borel-Cantelli lemmas: The first Borel Cantelli lemma follows

from Markov’s inequality. In fact, applied to X = ∞
P
1 , Markov’s inequality is
P∞k= N A k
the same as the union bound P( A N ∪ A N +1 ∪ . . .) ≤ k= N P( A k ) which is what gave us
the first Borel-Cantelli lemma.
 2.5. APPLICATIONS OF FIRST AND SECOND MOMENT METHODS 31

The second one is more interesting. Fix n < m and define X = m

P
1 . Then
k= n A k
Pm
E[ X ] = k=n P( A k ). Also,
" #
m X
m m
2
X X X
E[ X ] = E 1 A k 1 A` = P( A k ) + P( A k )P( A ` )
k = n `= n k= n k6=`
à !2
m
X m
X
≤ P( A k ) + P( A k ).
k= n k= n

Apply the second moment method to se that for any fixed n, as m → ∞,

¡Pm ¢2
k= n
P( A k ) 1
P( X ≥ 1) ≥ ¡P ¢2 Pm = ¢−1 → 1,
m
¡P m
k= n
P( A k ) + k=n P( A k ) 1 + k=n P( A k )
P
by assumption that P( A k ) = ∞. This shows that P(∪k≥n A k ) = 1 for any n and
hence P(lim sup A n ) = 1.
Note that this proof used independence only to claim that P( A k ∩ A ` ) = P( A k )P( A ` ).
Therefore the second Borel-Cantelli lemma holds for pairwise independent events
too!

Application 2: Coupon collector problem: A bookshelf has (large number) n

books numbered 1, 2, . . . , n. Every night, before going to bed, you pick one of the
books at random to read. The book is replaced in the shelf in the morning. How
many days pass before you have picked up each of the books at least once?

Theorem 2.13. Let T n denote the number of days till each book is picked at least
once. Then T n is “concentrated around n log n in a window of size n” by which we
mean that for any sequence θn → ∞, we have
P(|T n − n log n| < nθn ) → 1.

Remark 2.14. In the following proof and many other places, we shall have occasion
to make use of the elementary estimate
2 1
(2.1) 1 − x ≤ e− x ∀ x, 1 − x ≥ e − x− x ∀| x| < .
2
The first inequality follows by expanding e− x while the second follows by expanding
log(1 − x) = − x − x2 /2 − x3 /3 − . . . (valid for | x| < 1).

P ROOF. Fix an integer t ≥ 1 and let X t,k be the indicator that the kth book is not
picked up on the first t days. Then, P(T n > t) = P(S t,n ≥ 1) where S t,n = X t,1 +. . .+ X t,n .
As E[ X t,k ] = (1 − 1/ n)k and E[ X t,k X t,` ] = (1 − 2/ n)k for k 6= `, we also compute that
thefirst two moments of S t,n and use (2.1) to get
1 t
µ ¶
−t− t t
(2.2) ne n n2 ≤ E[S t,n ] = n 1 − ≤ ne− n .
n
1 t 2 t
µ ¶ µ ¶
t 2t
(2.3) E[S 2t,n ] = n 1 − + n( n − 1) 1 − ≤ ne− n + n( n − 1) e− n .
n n
The left inequality on the first line is valid only for n ≥ 2 which we assume.
Now set t = n log n + nθn and apply Markov’s inequality to get
n log n+ nθ n
(2.4) P(T n > n log n + nθn ) = P(S t,n ≥ 1) ≤ E[S t,n ] ≤ ne− n ≤ e−θn = o(1).
32 2. INDEPENDENT RANDOM VARIABLES

On the other hand, taking t < n log n − nθn (where we take θn < log n, of course!),
we now apply the second moment method. For any n ≥ 2, by using (2.3) we get
log n−θ n
E[S 2t,n ] ≤ eθn + e2θn . The first inequality in (2.2) gives E[S t,n ] ≥ eθn − n . Thus,
log n−θ n
E[S t,n ]2 2θn −2
e n
(2.5) P(T n > n log n − nθn ) = P(S t,n ≥ 1) ≥ ≥ = 1 − o(1)
E[S 2t,n ] eθn + e2θn
as n → ∞. From (2.4) and (2.5), we get the sharp bounds
P (|T n − n log( n)| > nθn ) → 0 for any θn → ∞. ■

Application 3: Branching processes: Consider a Galton-Watson branching pro-

cess with offsprings that are i.i.d ξ. Let Z n be the number of offsprings in the nth
generation. Take Z0 = 1.
Theorem 2.15. (1) If m < 1, then w.p.1, the branching process dies out. That
is P( Z n = 0 for all large n) = 1.
(2) If m > 1, then with positive probability, the branching process survives. That
is P( Z n ≥ 1 for all n) > 0.
P ROOF. In the proof, we compute E[ Z n ] and Var( Z n ) using elementary condi-
tional probability concepts. By conditioning on what happens in the ( n − 1)st gen-
eration, we write Z n as a sum of Z n−1 independent copies of ξ. From this, one
can compute that E[ Z n | Z n−1 ] = mZ n−1 and if we assume that ξ has variance σ2 we
also get Var( Z n | Z n−1 ) = Z n−1 σ2 . Therefore, E[ Z n ] = E[E[ Z n | Z n−1 ]] = mE[ Z n−1 ] from
which we get E[ Z n ] = m n . Similarly, from the formula Var( Z n ) = E[Var( Z n | Z n−1 )] +
Var(E[ Z n | Z n−1 ]) we can compute that
Var( Z n ) = m n−1 σ2 + m2 Var( Z n−1 )
¡ n−1
+ m n + . . . + m2n−1 σ2
¢
= m (by repeating the argument)
m n+1 − 1
= σ2 m n−1 .
m−1
(1) By Markov’s inequality, P( Z n > 0) ≤ E[ Z n ] = m n → 0. Since the events { Z n >
0} are decreasing, it follows that P(extinction) = 1.
(2) If m = E[ξ] > 1, then as before E[ Z n ] = m n which increases exponentially.
But that is not enough to guarantee survival. Assuming that ξ has finite
variance σ2 , apply the second moment method to write
E[ Z n ]2 1
P( Z n > 0) ≥ ≥
Var( Z n ) + E[ Z n ]2 1 + σ2
m−1
which is a positive number (independent of n). Again, since { Z n > 0} are
decreasing events, we get P(non-extinction) > 0.
The assumption of finite variance of ξ can be removed as follows. Since
E[ξ] = m > 1, we can find A large so that setting η = min{ξ, A }, we still have
E[η] > 1. Clearly, η has finite variance. Therefore, the branching process
with η offspring distribution survives with positive probability. Then, the
original branching process must also survive with positive probability! (A
coupling argument is the best way to deduce the last statement: Run the
original branching process and kill every child after the first A . If inspite
of the violence the population survives, then ...) ■
 2.5. APPLICATIONS OF FIRST AND SECOND MOMENT METHODS 33

Remark 2.16. The fundamental result of branching processes also asserts the a.s
extinction for the critical case m = 1. We omit this for now.

Application 4: How many prime divisors does a number typically have? For
a natural number k, let ν( k) be the number of (distinct) prime divisors of n. What is
the typical size of ν( n) as compared to n? We have to add the word typical, because
if p is a prime number then ν( p) = 1 whereas ν(2 × 3 × . . . × p) = p. Thus there are
arbitrarily large numbers with ν = 1 and also numbers for which ν is as large as we
wish. To give meaning to “typical”, we draw a number at random and look at its
ν-value. As there is no natural way to pick one number at random, the usual way of
making precise what we mean by a “typical number” is as follows.
Formulation: Fix n ≥ 1 and let [ n] := {1, 2, . . . , n}. Let µn be the uniform probability
measure on [ n], i.e., µn { k} = 1/ n for all k ∈ [ n]. Then, the function ν : [ n] → R can be
considered a random variable, and we can ask about the behaviour of these random
variables. Below, we write En to denote expectation w.r.t µn .

Theorem 2.17 (Hardy, Ramanujan). With the above setting, for any δ > 0, as n →
∞ we have
¯ ν( k )
½ ¾
µ n k ∈ [ n] : ¯ − 1 ¯ > δ → 0.
¯
(2.6)
log log n
P ROOF. (Turan). Fix n and for any prime p define X p : [ n] → R by X p ( k) = 1 p|k .
Then, ν( k) = X p ( k). We define ψ( k) := p X p ( k). Then, ψ( k) ≤ ν( k) ≤ ψ( k) + 4
P P
p≤ k 4
k p≤
p4
since there can be at most four primes larger than k that divide k. From this, it is
clearly enough to show (2.6) for ψ in place of ν (why?).
We shall
j k need the first two moments
j k of ψ under µn . For jthis
k we first note that
n n n
p pq 1 1 p 1 1 1
En [ X p ] = n and En [ X p X q ] = n . Observe that p − n ≤ n ≤ p and pq − n ≤
j k
n
pq 1
n ≤ pq .
1 3
By linearity En [ψ] = + O ( n− 4 ). Similarly
P P
p
E[ X p ] = p p
p≤ 4 n p≤ 4 n
X X
Varn [ψ] = Var[ X p ] + Cov( X p , X q )
p
4 p
p≤ n p6= q≤ 4 n
1 1
µ ¶
−1
O ( n−1 )
X X
= − 2 + O(n ) +
p
p≤ 4 n
p p p
p6= q≤ 4 n
X 1 X 1 1
= − 2
+ O ( n− 2 ).
p p p p
p≤ 4 n p≤ 4 n

We make use of the following two facts. Here, a n ∼ b n means that a n / b n → 1.

X 1 X∞ 1
∼ log log n 2
< ∞.
p p
p≤ 4 n p=1 p

The second one is obvious, while the first one is not hard, (see exercise 2.18 be-
3
low)). Thus, we get En [ψ] = log log n + O ( n− 4 ) and Varn [ψ] = log log n + O (1). Thus, by
34 2. INDEPENDENT RANDOM VARIABLES

Chebyshev’s inequality,
¯ ψ( k) − En [ψ] ¯
¯ > δ ≤ Varn (ψ) = O 1
½ ¾ µ ¶
µ n k ∈ [ n] : ¯ .
log log n δ2 (log log n)2 log log n
3
From the asymptotics En [ψ] = log log n + O ( n− 4 ) we also get (for n large enough)
¯ ψ( k) Varn (ψ) 1
½ ¾ µ ¶
µ n k ∈ [ n] : ¯ −1 ¯ > δ ≤ 2
¯
= O . ■
log log n δ (log log n)2 log log n
P 1
Exercise 2.18. p p
∼ log log n
p≤ 4 n

2.6. Weak law of large numbers

If a fair coin is tossed 100 times, we expect that the number of times it turns up
heads is close to 50. What do we mean by that, for after all the number of heads could
be any number between 0 and 100? What we mean of course, is that the number
of heads is unlikely to be far from 50. The weak law of large numbers expresses
precisely this.

Theorem 2.19 (Kolmogorov). Let X 1 , X 2 . . . be i.i.d random variables. If E[| X 1 |] <

∞, then for any δ > 0, as n → ∞, we have
¯ X1 + . . . + X n
µ ¶
− E[ X 1 ] > δ → 0.
¯
P ¯ ¯
n
In language to be introduced later, we shall say that S n / n converges to zero in proba-
Sn P
bility and write n → E[ X 1 ]

P ROOF. Step 1: First assume that X i have finite variance σ2 . Without loss of
generality take E[ X 1 ] = 0 (or else replace X i by X i −E[ X 1 ]. Then, µ = E[ X 1 ]. Then, by
the first moment method (Chebyshev’s inequality), P(| n−1 S n | > δ) ≤ n−2 δ−2 Var(S n ).
2
By the independence of X i s, we see that Var(S n ) = nσ2 . Thus, P(| Snn | > δ) ≤ nσδ2 which
goes to zero as n → ∞, for any fixed δ > 0.
Step 2: Now let X i have finite expectation (which we assume is 0), but not neces-
sarily any higher moments. Fix n and write X k = Yk + Z k , where Yk := X k 1| X k |≤ A n
and Z k := X k 1| X k |> A n for some A n to be chosen later. Then, Yi are i.i.d, with some
mean µn := E[Y1 ] = −E[ Z1 ] that depends on A n and goes to zero as A n → 0. We shall
choose A n going to infinity, so that for large enough n, we do have |µn | < δ (for an
arbitrary fixed δ > 0).
|Y1 | ≤ A n , hence Var(Y1 ) ≤ E[Y12 ] ≤ A n E[| X 1 |]. By the Chebyshev bound that we
used in step 1,
à !
¯ SYn Var(Y1 ) A n E[| X 1 |]
− µn ¯ > δ ≤
¯
(2.7) P ¯ ≤ .
n n δ2 n δ2

Further, if n is large, then |µn | < δ and then

à !
¯ S nZ ³ ´
+ µn ¯ > δ ≤ P S nZ 6= 0 ≤ nP( Z1 6= 0) = nP(| X 1 | > A n ).
¯
(2.8) P ¯
n
 2.7. APPLICATIONS OF WEAK LAW OF LARGE NUMBERS 35

Thus, writing X k = (Yk − µn ) + ( Z k + µn ), we see that

à ! à !
¯ Sn ¯ ¯ SY ¯ S nZ
µ ¶
¯ > 2δ n
− µn ¯ > δ + P ¯ + µn ¯ > δ
¯ ¯
P ¯ ≤ P ¯
n n n
A n E[| X 1 |]
≤ + nP(| X 1 | > A n )
n δ2
A n E[| X 1 |] n
≤ + E[| X 1 | 1| X 1 |> A n ].
n δ2 An
Now, we take A n = α n with α := δ3 E[| X 1 |]−1 . The first term clearly becomes less
than δ. The second term is bounded by α−1 E[| X 1 | 1| X 1 |>αn ], which goes to zero as
n → ∞ (for any fixed choise of α > 0). Thus, we see that
¯ Sn ¯
µ ¶
lim sup P ¯ ¯ > 2δ ≤ δ
n→∞ n
which gives the desired conclusion. ■

2.7. Applications of weak law of large numbers

We give three applications, two “practical” and one theoretical.

Application 1: Bernstein’s proof of Wierstrass’ approximation theorem.

Theorem 2.20. The set of polynomials is dense in the space of continuous functions
(with the sup-norm metric) on an interval of the line.
P ROOF. (Bernstein) ³Let ´ ¡f ¢∈ C [0, 1]. For any n ≥ 1, we define the Bernstein poly-
Pn k n k
nomials Q f ,n ( p) := k=0 f n k p (1 − p)n−k . We show that as n → ∞, kQ f ,n − f k → 0
which is clearly enough. To achieve this, we observe that Q f ,n ( p) = E[ f ( n−1 S n )],
where S n has Binomial(n,p) distribution. Law of large numbers enters, because Bi-
nomial may be thought of as a sum of i.i.d Bernoullis.
For p ∈ [0, 1], consider X 1 , X 2 , . . . i.i.d Ber( p) random variables. For any p ∈ [0, 1],
we have
¯ E p f S n − f ( p) ¯ ≤ E p ¯ f S n − f ( p) ¯
· µ ¶¸ · µ ¶ ¸
¯ ¯ ¯ ¯
n n
¯ Sn ¯ Sn
· µ ¶ ¸ · µ ¶ ¸
¯ ¯
= Ep ¯ f − f ( p) ¯ 1| S n − p|≤δ + E p ¯ f − f ( p) ¯ 1| S n − p|>δ
n n n n

¯ Sn
µ ¶
≤ ω f (δ) + 2k f kP p ¯ −p ¯>δ
¯
(2.9)
n
where k f k is the sup-norm of f and ω f (δ) := sup| x− y|<δ | f ( x) − f ( y)| is the modulus of
continuity of f . Observe that Var p ( X 1 ) = p(1 − p) to write
¯ Sn p(1 − p) 1
µ ¶
−p ¯>δ ≤
¯
Pp ¯ ≤ 2 .
n n δ2 4δ n
h ³ ´i
Plugging this into (2.9) and recalling that Q f ,n ( p) = E p f Snn , we get

kf k
sup ¯ Q f ,n ( p) − f ( p) ¯ ≤ ω f (δ) + 2
¯ ¯
p∈[0,1] 2δ n
Since f is uniformly continuous (which is the same as saying that ω f (δ) ↓ 0 as
δ ↓ 0), given any ² > 0, we can take δ > 0 small enough that ω f (δ) < ². With that
36 2. INDEPENDENT RANDOM VARIABLES

choice of δ, we can choose n large enough so that the second term becomes smaller
than ². With this choice of δ and n, we get kQ f ,n − f k < 2². ■

Remark 2.21. It is possible t write the proof without invoking WLLN. In fact, we did
not use WLLN, but the Chebyshev bound. The main point is that the Binomial(n,p)
probability measure puts almost all its mass between np(1 − δ) and np(1 + δ). Nev-
ertheless, WLLN makes it transparent why this is so.

Application 2: Monte Carlo method for evaluating integrals. Consider a con-

tinuous function f : [a, b] → R whose integral we would like to compute. Quite often,
the form of the function may be sufficiently complicated that we cannot analytically
compute it, but is explicit enough that we can numerically evaluate (on a computer)
f ( x) for any specified x. Here is how one can evaluate the integral by use of random
numbers.
Suppose X 1 , X 2 , . . . are i.i.d uniform([a, b]). Then, Yk := f ( X k ) are also i.i.d with
Rb
E[Y1 ] = a f ( x) dx. Therefore, by WLLN,
à !
¯1 X n Z b
f ( x) dx ¯ > δ → 0.
¯
P ¯ f (X k) −
n k=1 a

Hence if we can sample uniform random numbers from [a, b], then we can evaluate
1 Pn
n k=1 f ( X k ), and present it as an approximate value of the desired integral!
In numerical analysis one uses the same idea, but with deterministic points.
The advantage of random samples is that it works irrespective of the niceness of
the function. The accuracy is not great, as the standard deviation of n1 nk=1 f ( X k )
P

is Cn−1/2 , so to decrease the error by half, one needs to sample four times as many
points.
R1
Exercise 2.22. Since π = 0 1+4x2 dx, by sampling uniform random numbers X k and
evaluating n1 nk=1 4 2 we can estimate the value of π! Carry this out on the com-
P
1+ X k
puter to see how many samples you need to get the right value to three decimal
places.

Application 3: Accuracy in sample surveys Quite often we read about sample

surveys or polls, such as “do you support the war in Iraq?”. The poll may be con-
ducted across continents, and one is sometimes dismayed to see that the pollsters
asked a 1000 people in France and about 1800 people in India (a much much larger
population). Should the sample sizes have been proportional to the size of the popu-
lation?
Behind the survey is the simple hypothesis that each person is a Bernoulli ran-
dom variable (1=‘yes’, 0=‘no’), and that there is a probability p i (or p f ) for an Indian
(or a French person) to have the opinion yes. Are different peoples’ opinions indepen-
dent? Definitely not, but let us make that hypothesis. Then, if we sample n people,
we estimate p by X n where X i are i.i.d
q Ber( p). The accuracy of the estimate is mea-
1
sured by its mean-squared deviation Var( X n ) = p(1 − p) n− 2 . Note that this does
p

not depend on the population size, which means that the estimate is about as accu-
rate in India as in France, with the same sample size! This is all correct, provided
that the sample size is much smaller than the total population. Even if not satisfied
with the assumption of independence, you must concede that the vague feeling of
unease about relative sample sizes has no basis in fact...
 2.8. MODES OF CONVERGENCE 37

2.8. Modes of convergence

P
Definition 2.23. We say that X n → X (“ X n converges to X in probability”) if for
a.s.
any δ > 0, P(| X n − X | > δ) → 0 as n → ∞. Recall that we say that X n → X if
P (ω : lim X n (ω) = X (ω)) = 1.

2.8.1. Almost sure and in probability. Are they really different? Usually
looking at Bernoulli random variables elucidates the matter.

Example 2.24. Suppose A n are events in a probability space. Then one can see that
P a.s.
(a) 1 A n → 0 ⇐⇒ lim P( A n ) = 0. (b) 1 A n → 0 ⇐⇒ P(lim sup A n ) = 0.
n→∞ n→∞

By Fatou’s lemma, P(lim supn→∞ A n ) ≥ lim sup P( A n ), and hence we see that a.s con-
vergence of 1 A n to zero implies convergence in probability. The converse is clearly
false. For instance, if A n are independent events with P( A n ) = n−1 , then by the sec-
ond Borel-Cantelli, P( A n ) goes to zero but P(lim sup A n ) = 1. This example has all
the ingredients for the following two implications.

Lemma 2.25. Suppose X n , X are r.v. on the same probability space. Then,
a.s. P
(1) If X n → X , then X n → X .
P
n P(| X n − X | > δ) < ∞ for every δ > 0, then
P
(2) If X n → X “fast enough” so that
a.s.
Xn → X .

P ROOF. Note that analogous to the example,

P
(a) X n → X ⇐⇒ ∀δ > 0, lim P(| X n − X | > δ) = 0.
n→∞
a.s.
(b) X n → X ⇐⇒ ∀δ > 0, P(lim sup | X n − X | > δ) = 0.
n→∞

Thus, applying Fatou’s we see that a.s convergence implies convergence in proba-
bility. By the first Borel Cantelli lemma, if n P(| X n − X | > δ) < ∞, then P(| X n −
P

X | > δ i.o) = 0 and hence lim sup | X n − X | < δ. Apply this to all rational δ to get
lim sup | X n − X | = 0 and thus we get a.s. convergence. ■
P a.s.
Exercise 2.26. (1) If X n → X , show that X n k → X for some subsequence.
a.s.
(2) Show that X n → X if and only if every subsequence of { X n } has a further
subsequence that converges a.s.
P P
(3) If X n → X and Yn → Y (all r.v.s on the same probability space), show that
P P
aX n + bYn → aX + bY and X n Yn → X Y .
d
2.8.2. In distribution and in probability. We say that X n → X if the dis-
tributions of X n converges to the distribution of X . This is a matter of language,
but note that X n and X need not be on the same probability space for this to make
sense. In comparing it to convergence in probability, however, we must take them to
be defined on a common probability space.

Lemma 2.27. Suppose X n , X are r.v. on the same probability space. Then,
P d
(1) If X n → X , then X n → X .
d P
(2) If X n → X and X is a constant a.s, then X n → X .
38 2. INDEPENDENT RANDOM VARIABLES

P
P ROOF. (1) Suppose X n → X . Since for any δ > 0
P( X n ≤ t) ≤ P( X ≤ t + δ) + P( X − X n > δ), and P( X ≤ t − δ) ≤ P( X n ≤ t) + P( X n − X > δ),
we see that lim sup P( X n ≤ t) ≤ P( X ≤ t + δ) and lim inf P( X n ≤ t) ≥ P( X ≤
t − δ) for any δ > 0. Taking δ ↓ 0 and letting t be a continuity point of the cdf
d
of X , we immediately get lim P( X n ≤ t) = P( X ≤ t). Thus, X n → X .
(2) If X = a a.s (a is a constant), then the cdf of X is F X ( t) = 1 t≥a . Hence,
P( X n ≤ t − δ) → 0 and P( X n ≤ t + δ) → 1 for any δ > 0 as t ± δ are continuity
P
points of F X . Therefore P(| X n − a| > δ) → 0 and we see that X n → a. ■

Exercise 2.28. (1) Give an example to show that convergence in distribution

does not imply convergence in probability.
(2) Suppose that X n is independent of Yn for each n (no assumptions about
d d d
independence across n). If X n → X and Yn → Y , then ( X n , Yn ) → (U, V )
d d d
where U = X , V = Y and U, V are independent. Further, aX n + bYn →
aU + bV .
P d
(3) If X n → X and Yn → Y (all on the same probability space), then show that
d
X n Yn → X Y .
2.8.3. In probability and in L p . How do convergence in L p and convergence
Lp
in probability compare? Suppose X n → X (actually we don’t need p ≥ 1 here, but only
p > 0 and E[| X n − X | p ] → 0). Then, for any δ > 0,
P(| X n − X | > δ) ≤ δ− p E[| X n − X | p ] → 0
P
and thus X n → X . The converse is not true as the following example shows.
P
Example 2.29. Let X n = 2n w.p 1/ n and X n = 0 w.p 1 − 1/ n. Then, X n → 0 but
p
E[ X n ] = n−1 2np for all n, and hence X n does not go to zero in L p (for any p > 0).
As always, the fruitful question is to ask for additional conditions to convergence
in probability that would ensure convergence in L p . Let us stick to p = 1. Is there a
P
reasonR to expect a (weaker) converse? Indeed, suppose X n → X . Then write E[| X n −
∞
X |] = 0 P(| X n − X | > t) dt. For each t the integrand goes to zero. Will the integral go
to zero? Surely, if | X n | ≤ 10 a.s. for all n, (then the same holds for | X |) the integral
reduces to the interval [0, 20] and then by DCT (since the integrand is bounded by 1
which is integrable over the interval [0,20]), we get E[| X n − X |] → 0.
As example 2.29 shows, the converse is not true in full generality either. What
goes wrong in this example is that with a small probability X n can take a very very
large value and hence the expected value stays away from zero. This observation
makes the next definition more palatable. We put the new concept in a separate
section to give it the due respect that it deserves.

2.9. Uniform integrability

Definition 2.30. A family { X i } i∈ I of random variables is said to be uniformly inte-
grable if given any ² > 0, there exists A large enough so that E[| X i |1| X i |> A ] < ² for all
i ∈ I.
Example 2.31. A finite set of integrable r.v.s is uniformly integrable. More inter-
estingly, an L p -bounded family with p > 1 is u.i. For, if E[| X i | p ] ≤ M for all i ∈ I for
 2.9. UNIFORM INTEGRABILITY 39

some M > 0, then E[| X i |1| X i |> t ] ≤ t−( p−1) M which goes to zero as t → ∞. Thus, given
² > 0, one can choose t large so that sup i∈ I E[| X i |1| X i |> t ] < ².
This fails for p = 1 as the example 2.29 shows a family of L1 bounded random
variables that are not u.i. However, a u.i family must be bounded in L1 . To see this
find A > 0 so that E[| X i |1| X i |> A ] < 1 for all i . Then, for any i ∈ I , we get E[| X i |] =
E[| X i |1| X i |< A ] + E[| X i |1| X i |≥ A ] ≤ A + 1.
Exercise 2.32. If { X i } i∈ I and {Y j } j∈ J are both u.i, then { X i + Y j }( i, j)∈ I × J is u.i. What
about the family of products, { X i Y j }( i, j)∈ I × J ?
Lemma 2.33. Suppose X n , X are r.v. on the same probability space. Then, the fol-
lowing are equivalent.
L1
(1) X n → X .
P
(2) X n → X and { X n } is u.i.
L1 L1 P P
P ROOF. If Yn = X n − X , then X n → X iff Yn → 0, while X n → X iff Yn → 0 and by
the first part of exercise 2.32, { X n } is u.i if and only if {Yn } is. Hence we may work
with Yn instead (i.e., we may assume that the limiting r.v. is 0 a.s).
L1 P
First suppose Yn → 0. Then we showed that Yn → 0. To show that {Yn } is u.i,
let ² > 0 and fix N² so that E[|Yn |] < ² for all n ≥ N² . Then, pick A > 1 so large
that E[|Yk |1|Yk |> A ] ≤ ² for all k ≤ N . With the same A and any k ≥ N² , we get
E[|Yk |1|Yk |> A ] ≤ A −1 E[|Yk |] < ² since A > 1 and E[|Yk |] < ². Thus we have found
one A which works for all Yk . Hence {Yk } is u.i.
P
Next suppose Yn → 0 and that {Yn } is u.i. Then, fix ² > 0 and find A > 0 so that
E[|Yk |1|Yk |> A ] ≤ ² for all k. Then,
Z A
E[|Yk |] ≤ E[|Yk |1|Yk |≤ A ] + E[|Yk |1|Yk |> A ] ≤ P(|Yk | > t) dt + ².
0
For all t ∈ [0, A ], by assumption P(|Yk | > t) → 0, while we also have P(|Yk | > t) ≤ 1 for
all k and 1 is integrable on [0, A ]. Hence, by DCT the first term goes to 0 as k → ∞.
L1
Thus lim sup E[|Yk |] ≤ ² for any ² and it follows that Yk → 0. ■
a.s. L1
Corollary 2.34. If X n → X , then X n → X if and only if { X n } is u.i.
To deduce convergence in mean from a.s convergence, we have so far always
invoked DCT. As shown by Lemma 2.33 and corollary 2.34, uniform integrability
is the sharp condition, so it must be weaker than the assumption in DCT. Indeed,
if { X n } are dominated by an integrable Y , then whatever A works for Y in the u.i
condition will work for the whole family { X n }. Thus a dominated family is u.i., while
the converse is false.
Remark 2.35. Like tightness of measures, uniform integrability is also related to
a compactness question. On the space L1 (µ), apart from the usual topology coming
from
R the norm, R there is another one called weak topology (where f n → f if and only
if f n gd µ → f gd µ for all g ∈ L∞ (µ)). The Dunford-Pettis theorem asserts that pre-
compact subsets of L1 (µ) in this weak topology are precisely uniformly integrable
subsets of L1 (µ)! A similar question
R can be asked in L p for p > 1 where weak topology
means that f n → f if and only if f n gd µ → f gd µ for all g ∈ L q (µ) where q−1 + p−1 =
R

1. Another part of Dunford-Pettis theorem asserts that pre-compact subsets of L p (µ)

in this weak topology are precisely those that are bounded in the L p (µ) norm.
40 2. INDEPENDENT RANDOM VARIABLES

2.10. Strong law of large numbers

P
If X n are i.i.d with finite mean, then the weak law asserts that n−1 S n → E[ X 1 ].
The strong law strengthens it to almost sure convergence.
Theorem 2.36 (Kolmogorov’s SLLN). Let X n be i.i.d with E[| X 1 |] < ∞. Then, as
a.s.
n → ∞, we have Snn → E[ X 1 ].
The proof of this theorem is somewhat complicated. First of all, we should
ask
¡ if WLLN implies¢ SLLN? From Lemma 2.27 we see that this can be done if
P | n−1 S n − E[ X 1 ]| > δ is summable, for every δ > 0. Even assuming finite variance
Var( X 1 ) = σ2 , Chebyshev’s inequality only gives a bound of σ2 δ−2 n−1 for this prob-
ability and this is not summable. Since this is at the borderline of summability, if
we assume that pth moment exists for some p > 2, we may expect to carry out this
proof. Suppose we assume that α4 := E[ X 14 ] < ∞ (of course 4 is not the smallest num-
ber bigger than 2, but how do we compute E[|S n | p ] in terms of moments of X 1 unless
p is an even integer?). Then, we may compute that (assume E[ X 1 ] = 0 wlog)
E S 4n = n2 ( n − 1)2 σ4 + nα4 = O ( n2 ).
£ ¤

Thus P | n−1 S n | > δ ≤ n−4 δ−4 E[S 4n ] = O ( n−2 ) which is summable, and by Lemma 2.27
¡ ¢

we get the following weaker form of SLLN.

S n a.s.
Theorem 2.37. Let X n be i.i.d with E[| X 1 |4 ] < ∞. Then, n → E[ X 1 ] as n → ∞.
Now we return to the serious question of proving the strong law under first
moment assumptions. The presentation of the following proof is adapted from a blog
article of Terence Tao.
P ROOF. Step 1: It suffices to prove the theorem for integrable non-negative r.v, be-
cause we may write X = X + − X − and note that S n = S + −
n − S n . (Caution: Don’t also as-
sume zero mean in addition to non-negativity!). Henceforth, we assume that X n ≥ 0
and µ = E[ X 1 ] < ∞. One consequence is that
S N1
S n S N2
(2.10) ≤ ≤ if N1 ≤ n ≤ N2 .
N2 n N1
Step 2: The second step is to prove the following claim. To understand the big
picture of the proof, you may jump to the third step where the strong law is deduced
using this claim, and then return to the proof of the claim.
S n k a.s.
Claim 2.38. Fix any λ > 1 and define n k := bλk c. Then, n k → E[ X 1 ] as k → ∞.
Proof of the claim Fix j and for 1 ≤ k ≤ n j write X k = Yk + Z k where Yk = X k 1 X k ≤n j
and Z k = X k 1 X k >n j (why we chose the truncation at n j is not clear at this point).
Pn j
Then, let Jδ be large enough so that for j ≥ Jδ , we have E[ Z1 ] ≤ δ. Let S Y n j = k=1 Yk
Pn j
and S nZ j = k=1 Z k . Since S n j = S Y Z
n j + S n j and E[ X 1 ] = E[Y1 ] + E[ Z1 ], we get
à Y Z !
¯ Sn j ¯ Sn j ¯ ¯ Sn j
µ ¶
− E[ X 1 ] > 2δ − E[ Z1 ] > 2δ
¯ ¯
P ¯ ¯ ≤ P ¯ − E[Y1 ] +
¯ ¯ ¯
nj nj nj
à Y ! à Z !
¯ Sn j ¯ Sn j
− E[Y1 ] > δ + P − E[ Z1 ] > δ
¯ ¯
≤ P ¯ ¯ ¯ ¯
nj nj
à Y ! à Z !
¯ Sn j Sn j
− E[Y1 ] ¯ > δ + P
¯
(2.11) ≤ P ¯ 6= 0 .
nj nj
 2.11. KOLMOGOROV’S ZERO-ONE LAW 41

We shall show that both terms in (2.11) are summable over j . The first term can be
bounded by Chebyshev’s inequality
à Y !
¯ Sn j 1 1
− E[Y1 ] ¯ > δ ≤ 2 E[Y12 ] = 2 E[ X 12 1 X 1 ≤n j ].
¯
(2.12) P ¯
nj δ nj δ nj
while the second term is bounded by the union bound
à Z !
Sn j
(2.13) P 6= 0 ≤ n j P( X 1 > n j ).
nj
The right hand sides of (2.12) and (2.13) are both summable. To see this, observe
that for any positive x, there is a unique k such that n k < x ≤ n k+1 , and then
∞ 1 ∞ 1 ∞ k
x 2 1 x≤ n j ≤ x 2 λ j ≤ C λ x.
X X X X
(2.14) ( a) ≤ C λ x. ( b) n j 1 x> n j ≤
j = k+1 λ
n j
j =1 j j =1 j =1
λ
Here, we may take C λ = λ− 1 , but what matters is that it is some constant depending
on λ (but not on x). We have glossed over the difference between bλ j c and λ j but
you may check that it does not matter (perhaps by replacing C λ with a larger value).
Setting x = X 1 in the above inequalities (a) and (b) and taking expectations, we get
∞ 1 ∞
E[ X 12 1 X 1 ≤n j ] ≤ C λ E[ X 1 ].
X X
n j P( X 1 > n j ) ≤ C λ E[ X 1 ].
j =1 n j j =1

As E[ X 1 ] < ∞, the probabilities on the left µhand side of (2.12) ¶and (2.13) are sum-
¯ Sn
mable in j , and hence it also follows that P ¯ n j − E[ X 1 ] ¯ > 2δ is summable. This
¯
j
Sn a.s.
happens for every δ > 0 and hence Lemma 2.27 implies that n j → E[ X 1 ] a.s. This
j
proves the claim.
Step 3: Fix λ > 1. Then, for any n, find k such that λk < n ≤ λk+1 , and then, from
(2.10) we get
1 Sn Sn
E[ X 1 ] ≤ lim inf ≤ lim sup ≤ λE[ X 1 ], almost surely.
λ n→∞ n n→∞ n
1 Sn
Take intersection of the above event over all λ = 1 + m, m ≥ 1 to get limn→∞ n =
E[ X 1 ] a.s. ■

2.11. Kolmogorov’s zero-one law

We saw that in strong law the limit of n−1 S n turned out to be constant, while
a priori, it could well have been random. This is a reflection of the following more
general and surprising fact.
Definition 2.39. Let Fn be sub-sigma algebras of F . Then the tail σ-algebra of the
sequence Fn is defined to be T := ∩n σ (∪k≥n Fk ). For a sequence of random variables
X 1 , X 2 , . . ., the tail sigma algebra is the tail of the sequence σ( X n ).
We also say that a σ-algebra is trivial (w.r.t a probability measure) if P( A ) equals
0 or 1 for every A in the si g-algebra.
Theorem 2.40 (Kolmogorov’s zero-one law). Let (Ω, F , P) be a probability space.
(1) If Fn is a sequence of independent sub-sigma algebras of F , then the tail
si g-algebra is trivial.
42 2. INDEPENDENT RANDOM VARIABLES

(2) If X n are independent random variables, and A is a tail event, then P( A ) is

0 or 1 for every A ∈ T .
P ROOF. The second statement follows immediately from the first. To prove
the first, define Tn := σ (∪k>n Fk ). Then, F1 , . . . , Fn , Tn are independent. Hence,
F1 , . . . , Fn , T are independent. Since this is true for every n, we see that T , F1 , F2 , . . .
are independent. Hence, T and σ (∪n Fn ) are independent. But T ⊆ σ (∪n Fn ),
hence, T is independent of itself. This implies that for any A ∈ T , we must have
P( A )2 = P( A ∩ A ) = P( A ) which forces P( A ) to be 0 or 1. ■

Exercise 2.41. Let X i be independent random variables. Which of the following

random variables must necessarily be constant almost surely? lim sup X n , lim inf X n ,
lim sup n−1 S n , lim inf S n .
An application: This application is really an excuse to introduce a beautiful object
of probability. Consider the lattice Z2 , points of which we call vertices. By an edge
of this lattice we mean a pair of adjacent vertices {( x, y), ( p, q)} where x = p, | y − q| = 1
or y = q, | x − p| = 1. Let E denote the set of all edges. X e , e ∈ E be i.i.d Ber(p) random
variables indexed by E . Consider the subset of all edges e for which X e = 1. This
gives a random subgraph of Z2 called the bond percolation at level p. We denote the
subgraph by G ω .t
Question: What is the probability that in the percolation subgraph, there is an
infinite connected component?
Let A = {ω : G ω has an infinite connected component}. If there is an infinite
component, changing X e for finitely many e cannot destroy it. Conversely, if there
was no infinite cluster to start with, changing X e for finitely many e cannot cre-
ate one. In other words, A is a tail event for the collection X e , e ∈ E ! Hence, by
Kolmogorov’s 0-1 law, P p ( A ) is equal to 0 or 1. Is it 0 or is it 1?
In pathbreaking work, it was proved by 1980s that P p ( A ) = 0 if p ≤ 21 and
P p ( A ) = 1 if p > 21 .
The same problem can be considered on Z3 , keeping each edge with probability
p and deleting it with probability 1 − p, independently of all other edges. It is again
known (and not too difficult to show) that there is some number p c ∈ (0, 1) such that
P p ( A ) = 0 if p < p c and P p ( A ) = 1 if p > p c . The value of p c is not known, and more
importantly, it is not known whether P p c ( A ) is 0 or 1!

2.12. The law of iterated logarithm

If a n ↑ ∞, then the reasoning in the previous section applies and lim sup a−n 1 S n
is constant a.s. This motivates the following natural question.
Question: Let X i be i.i.d random variables taking values ±1 with equal probability.
Find a n so that lim sup Sa nn = 1 a.s.
The question is about the growth rate of sums of random independent ±1s. We
a.s.
know that n−1 S n → 0 by the SLLN, hence, a n = n is “too much”. What about nα . Ap-
plying Hoeffding’s inequality (proved in the next section), we see that P( n−α S n > t) ≤
exp{− 12 t2 n2α−1 }. If α > 21 , this is a summable sequence for any t > 0, and therefore
a.s.
P( n−α S n > t i.o.) = 0. That is lim sup n−α S n → 0 for α > 12 . What about α = 21 ? One
1 p
can show that lim sup n− 2 S n = +∞ a.s, which means that n is too slow compared
p 1
to S n . So the right answer is larger than n but smaller than n 2 +² for any ² > 0.
The sharp answer, due to Khinchine is a crown jewel of probability theory!
 2.13. HOEFFDING’S INEQUALITY 43

Result 2.42 (Khinchine’s law of iterated logarithm). Let X i be i.i.d with zero
mean and finite variance σ2 = 1 (without loss of generality). Then,
Sn
lim sup p = +1 a.s.
n→∞ 2 n log log n
½ ¾
Sn
In fact the set of all limit points of the sequence p is almost surely equal
2 n log log n
to the interval [−1, 1].

We skip the proof of LIL, because it is a bit involved, and there are cleaner ways
to deduce it using Brownian motion (in this or a later course).

Exercise 2.43. Let X i be i.i.d random variables taking values ±1 with equal proba-
bility. Show that lim sup p S n ≤ 1, almost surely.
n→∞ 2 n log log n

2.13. Hoeffding’s inequality

If X n are i.i.d with finite mean, then we know that the probability for S n / n to be
more than δ away from its mean, goes to zero. How fast? Assuming finite variance,
we saw that this probability decays at least as fast as n−1 . If we assume higher
moments, we can get better bounds, but always polynomial decay in n. Here we
assume that X n are bounded a.s, and show that the decay is like a Gaussian.

Lemma 2.44. (Hoeffding’s inequality). Let X 1 , . . . , X n be independent, and as-

sume that | X k | ≤ d k w.p.1. For simplicity assume that E[ X k ] = 0. Then, for any n ≥ 1
and any t > 0,
( )
t2
P (|S n | ≥ t) ≤ 2 exp − Pn .
2 i=1 d 2i

Remark 2.45. The boundedness assumption on X k s is essential. That E[ X k ] = 0 is

for convenience. If we remove that assumption, note that Yk = X k − E[ X k ] satisfy the
assumptions of the theorem, except that we can only say that |Yk | ≤ 2 d k (because
| X k | ≤ d k implies that |E[ X k ]| ≤ d k and hence | X k − E[ X k ]| ≤ 2 d k ). Thus, applying
the result to Yk s, we get
( )
t2
P (|S n − E[S n ]| ≥ t) ≤ 2 exp − Pn .
8 i=1 d 2i

P ROOF. Without loss of generality, take E[ X k ] = 0. Now, if | X | ≤ d w.p.1, and

E[ X ] = 0, by convexity of exponential on [−1, 1], we write for any λ > 0
1 X −λd X λd
µµ ¶ µ ¶ ¶
λX
e ≤ 1+ e + 1− e .
2 d d
Therefore, taking expectations we get E[exp{λ X }] ≤ cosh(λ d ). Take X = X k , d = d k
and multiply the resulting inequalities and use independence to get E[exp{λS n }] ≤
Qn
k=1
cosh(λ d k ). Apply the elementary inequality cosh( x) ≤ exp( x2 /2) to get
( )
n
1 2X 2
E[exp{λS n }] ≤ exp λ d .
2 k=1 k
44 2. INDEPENDENT RANDOM VARIABLES

From Markov’s inequality we thus get P(S n > t) ≤ e−λ t E[ eλS n ] ≤ exp −λ t + 21 λ2 nk=1 d 2k .
© P ª

Optimizing this over λ gives the choice λ = Pn t 2 and the inequality

d
k=1 k
( )
t2
P (S n ≥ t) ≤ exp − Pn .
2 i=1 d 2i
Working with − X k gives a similar inequality for P(−S n > t) and adding the two we
get the statement in the lemma. ■
The power of Hoeffding’s inequality is that it is not an asymptotic statement
but valid for every finite n and finite t. Here are two consequences. Let X i be i.i.d
bounded random variables with P(| X 1 | ≤ d ) = 1.
(1) (Large deviation regime) Take t = nδ to get
1 u2
µ ¶ ½ ¾
P | S n − E[ X 1 ]| ≥ u = P (|S n − E[S n ]| ≥ u) ≤ 2 exp − 2 n .
n 8d
This shows that for bounded random variables, the probability for the sam-
ple sum S n to deviate by an order n amount from its mean decays exponen-
tially in n. This is called the large deviation regime because the order of the
deviation is the same as the typical order of the quantity we are measuring.
p
(2) (Moderate deviation regime) Take t = u n to get
u2
½ ¾
P (|S n − E[S n ]| ≥ δ) ≤ 2 exp − 2 .
8d
p
This shows that S n is within a window of size n centered at E[S n ]. In
this case the probability is not decaying with n, but the window we are
p
looking at is of a smaller order namely, n, as compared to S n itself, which
is of order n. Therefore this is known as moderate deviation regime. The
p
inequality also shows that the tail probability of (S n − E[S n ])/ n is bounded
by that of a Gaussian with variance d . More generally, if we take t = unα
u2
n2α−1
with α ∈ [1/2, 1), we get P (|S n − E[S n ]| ≥ unα ) ≤ 2 e− 2

As Hoeffding’s inequality is very general, and holds for all finite n and t, it is not
surprising that it is not asymptotically sharp. For example, CLT will show us that
p d
(S n − E[S n ])/ n → N (0, σ2 ) where σ2 = Var( X 1 ). Since σ2 < d , and the N (0, σ2 ) has
2 2
tails like e−u /2σ , Hoeffding’s is asymptotically (as u → ∞) not sharp in the moderate
regime. In the large deviation regime, there is well studied theory. A basic result
there says that P(|S n − E[S n ]| > nu) ≈ e−nI (u) , where the function I ( u) can be written
in terms of the moment generating function of X 1 . It turns out that if | X i | ≤ d ,
then I ( u) is larger than u2 /2 d which is what Hoeffding’s inequality gave us. Thus
Hoeffding’s is asymptotically (as n → ∞) not sharp in the large deviation regime.

2.14. Random series with independent terms

In law of large numbers, we considered a sum of n terms scaled by n. A natural
question is to ask about convergence of infinite series with terms that are indepen-
P
dent random variables. Of course X n will not converge if X i are i.i.d (unless X i = 0
a.s!). Consider an example.
Example 2.46. Let a n be i.i.d with finite mean. Important examples are a n ∼ N (0, 1)
or a n = ±1 with equal probability. Then, define f ( z) = n a n z n . What is the ra-
P

dius of convergence of this series? From the formula for radius of convergence
 2.14. RANDOM SERIES WITH INDEPENDENT TERMS 45

1 −1
³ ´
R = lim supn→∞ |a n | n , it is easy to find that the radius of convergence is exactly
1 (a.s.) [Exercise]. Thus we get a random analytic function on the unit disk.
Now we want to consider a general series with independent terms. For this to
happen, the individual terms must become smaller and smaller. The following result
shows that if that happens in an appropriate sense, then the series converges a.s.
Theorem 2.47 (Khinchine). Let X n be independent random variables with finite
P
second moment. Assume that E[ X n ] = 0 for all n and that n Var( X n ) < ∞.
P ROOF. A series converges if and only if it satisfies Cauchy criterion. To check
the latter, consider N and consider
(2.15)
P (|S n − S N | > δ for some n ≥ N ) = lim P (|S n − S N | > δ for some N ≤ n ≤ N + m) .
m→∞
Thus, for fixed N, m we must estimate the probability of the event δ < max1≤k≤m |S N +k −
S N |. For a fixed k we can use Chebyshev’s to get P(δ < max1≤k≤m |S N +k − S N |) ≤
δ−2 Var( X N + X N +1 + . . . + X N +m ). However, we don’t have a technique for controlling
the maximum of |S N +k − S N | over k = 1, 2, . . . , m. This needs a new idea, provided by
Kolmogorov’s maximal inequality below.
Invoking 2.50, we get
NX
+m ∞
P (|S n − S N | > δ for some N ≤ n ≤ N + m) ≤ δ−2 Var( X k ) ≤ δ−2
X
Var( X k ).
k= N k= N
The right hand side goes to zero as N → ∞. Thus, from (2.15), we conclude that for
any δ > 0,
lim P (|S n − S N | > δ for some n ≥ N ) = 0.
N →∞
This implies that lim sup S n − lim inf S n ≤ δ a.s. Take intersection over δ = 1/ k, k =
1, 2 . . . to get that S n converges a.s. ■
Remark 2.48. What to do if the assumptions are not exactly satisfied? First, sup-
P P
pose that n Var( X n ) < ∞ but E[ X n ] may not be zero. Then, we can write X n =
P P
( X n − E[ X n ]) + E[ X n ]. The first series on the right satisfies the assumptions of
P
Theorem thm:convergenceofrandomseries and hence converges a.s. Therefore, X n
P
will then converge a.s if the deterministic series n E[ X n ] converges and conversely,
P P
if n E[ X n ] does not converge, then X n diverges a.s.
Next, suppose we drop the finite variance condition too. Now X n are arbi-
trary independent random variables. We reduce to the previous case by truncation.
Suppose we could find some A > 0 such that P(| X n | > A ) is summable. Then set
Yn = X n 1| X n |> A . By Borel-Cantelli, almost surely, X n = Yn for all but finitely many n
P P
and hence X n converges if and only if Yn converges. Note that Yn has finite vari-
P P
ance. If n E[Yn ] converges and n Var(Yn ) < ∞, then it follows from the argument
P
in the previous paragraph and Theorem 2.47 that Yn converges a.s. Thus we have
proved
Lemma 2.49 (Kolmogorov’s three series theorem - part 1). Suppose X n are
independent random variables. Suppose for some A > 0, the following hold with
Yn := X n 1| X n |≤ A .
X X X
( a) P(| X n | > A ) < ∞. ( b) E[Yn ] converges. ( c) Var(Yn ) < ∞.
n n n
P
Then, n X n converges, almost surely.
46 2. INDEPENDENT RANDOM VARIABLES

P
Kolmogorov showed that if n X n converges a.s., then for any A > 0, the three
series (a), (b) and (c) must converge. Together with the above stated result, this
forms a very satisfactory answer as the question of convergence of a random series
(with independent entries) is reduced to that of checking the convergence of three
non-random series! We skip the proof of this converse implication.

2.15. Kolmogorov’s maximal inequality

It remains to prove the inequality invoked earlier about the maximum of partial
sums of X i s. Note that the maximum of n random variables can be much larger than
any individual one. For example, if Yn are independent Exponential(1), then P(Yk >
t) = e− t , whereas P(maxk≤n Yk > t) = 1 − (1 − e− t )n which is much larger. However,
when we consider partial sums S 1 , S 2 , . . . , S n , the variables are not independent and
a miracle occurs.
Lemma 2.50 (Kolmogorov’s maximal inequality). Let X n be independent ran-
dom variables with finite variance and E[ X n ] = 0 for all n. Then, P (maxk≤n |S k | > t) ≤
t−2 nk=1 Var( X k ).
P

P ROOF. The second inequality follows from the first by considering X k s and
their negatives. Hence it suffices to prove the first inequality.
Fix n and let τ = inf{ k ≤ n : |S k | > t} where it is understood that τ = n if |S k | ≤ t
for all k ≤ n. Then, by Chebyshev’s inequality,
P(max |S k | > t) = P(|S τ | > t) ≤ t−2 E[S τ2 ].
k≤ n
We control the second moment of S τ by that of S n as follows.
E[S 2n ] = E (S τ + (S n − S τ ))2
£ ¤

= E[S τ2 ] + E (S n − S τ )2 − 2E[S τ (S n − S τ )]
£ ¤

(2.16) ≥ E[S τ2 ] − 2E[S τ (S n − S τ )].

We evaluate the second term by splitting according to the value of τ. Note that
S n − S τ = 0 when τ = n. Hence,
nX
−1
E[S τ (S n − S τ )] = E[1τ=k S k (S n − S k )]
k=1
nX
−1
= E [1τ=k S k ] E[S n − S k ] (because of independence)
k=1
= 0 (because E[S n − S k ] = 0).
In the second line we used the fact that S k 1τ=k depends on X 1 , . . . , X k only, while
S n − S k depends only on X k+1 , . . . , X n . Putting this result into (2.16), we get the
E[S 2n ] ≥ E[S τ2 ] which together with Chebyshev’s gives us
P(max S k > t) ≤ t−2 E[S 2n ]. ■
k≤ n

2.16. Central limit theorem - statement, heuristics and discussion

If X i are i.i.d with zero mean and finite variance σ2 , then we know that E[S 2n ] =
2 p
nσ , which can roughly be interpreted as saying that S n ≈ n (That the sum of n
p
random zero-mean quantities grows like n rather than n is sometimes called the
fundamental law of statistics). The central limit theorem makes this precise, and
 2.16. CENTRAL LIMIT THEOREM - STATEMENT, HEURISTICS AND DISCUSSION 47

p
shows that on the order of n, the fluctuations (or randomness) of S n are indepen-
dent of the original distribution of X 1 ! We give the precise statement and some
heuristics as to why such a result may be expected.
S n − nµ
Theorem 2.51. Let X n be i.i.d with mean µ and finite variance σ2 .Then, p
σ n
converges in distribution to N (0, 1).
Informally, letting χ denote a standard Normal variable, we may write S n ≈ nµ +
p
σ nχ. This means, the distribution of S n is hardly dependent on the distribution of
X 1 that we started with, except for the two parameter of mean and variance. This is
a statement about a remarkable symmetry!

Heuristics: Why should one expect such a statement

·³ ´ ¸ to be true? Without losing
2 Sn 2
generality, let us take µ = 0 and σ = 1. As E p n
= 1 is bounded, we see that
1
n− 2 S n is tight, and hence has weakly convergent subsequences. Let us make a leap
Sn
of faith and suppose that p n
converges in distribution. To what? Let Y be a random
1 d
variable with the limiting distribution. Then, (2 n)− 2 S 2n → Y and further,
X 1 + X 3 + . . . + X 2n−1 d X 2 + X 4 + . . . + X 2n d
p →Y, p →Y.
n n
But ( X 1 , X 3 , . . .) is independent of ( X 2 , X 4 , . . .). Therefore, by an earlier exercise, we
also get
X 1 + X 3 + . . . + X 2n−1 X 2 + X 4 + . . . + X 2n d
µ ¶
p , p → (Y1 , Y2 )
n n
where Y1 , Y2 are i.i.d copies of Y . But then, by yet another exercise, we get
S 2n 1 X 1 + X 3 + . . . + X 2n−1 X 2 + X 4 + . . . + X 2n d Y1 + Y2
µ ¶
p = p p + p → p
2n 2 n n 2
d p
Thus we must have Y1 + Y2 = 2Y . Therefore, if ψ( t) denotes the characteristic
function of Y , then
p i2 t 2
h i h µ ¶
itY itY / 2
ψ( t) = E e =E e =ψ p .
2
d p
Similarly, for any k ≥ 1, we can prove that Y1 + . . . Yk = kY , where Yi are i.i.d copies
of Y and hence ψ( t) = ψ( tk−1/2 )k . From this, by standard methods, one can deduce
2
that ψ( t) = e−at for some a > 0 (exercise). By uniqueness of characteristic functions,
Y ∼ N (0, 2a). Since we expect E[Y 2 ] = 1, we must get N (0, 1).

It is an instructive exercise to prove the CLT by hand for specific distributions.

For example, suppose X i are i.i.d exp(1) so that E[ X 1 ] = 1 and Var( X 1 ) = 1. Then
S n ∼ Γ( n, 1) and hence Sp
n −n
n
has density
1 − n− xp n p p
f n ( x) = e ( n + x n)n−1 n
Γ( n)
1
e − n n n− 2 − xp n x n−1
µ ¶
= e 1+ p
Γ( n) n
1 − x2
→ p e
2π
48 2. INDEPENDENT RANDOM VARIABLES

by elementary calculations. By an earlier exercise convergence of densities implies

convergence in distribution and thus we get CLT for sums of exponential random
variables.
Exercise 2.52. Prove the CLT for X 1 ∼ Ber( p). Note that this also implies CLT for
X 1 ∼ Bin( k, p).

2.17. Central limit theorem - Proof using characteristic functions

We shall use characteristic functions to prove the CLT. To make the main idea of
the proof transparent, we first prove a restricted version assuming third moments.
Once the idea is clear, we prove a much more general version later which will also
give Theorem 2.51. We shall need the following fact.
Exercise 2.53. Let z n be complex numbers such that nz n → z. Then, (1 + z n )n → e z .
Theorem 2.54. Let X n be i.i.d with finite third moment, and having zero mean and
Sn
unit variance. Then, p n
converges in distribution to N (0, 1).

P ROOF. By Lévy’s continuity theorem, it suffices to show that the characteristic

1
functions of n− 2 S n converge to the of N (0, 1). Note that
p i t n
h µ ¶
ψn ( t) := E e itS n / n = ψ p
n
where ψ is the c.f of X 1 . Use Taylor expansion
1 i ∗
e itx = 1 + itx − t2 x2 − t3 e itx x3 for some x∗ ∈ [0, x] or [ x, 0].
2 6
Apply this with X 1 in place of x, tn−1/2 in place of t, take expectations and recall that
E[ X 1 ] = 0 and E[ X 12 ] = 1 to get
t t2 i
µ ¶ h i
∗
ψ p = 1− + R n ( t), where R n ( t) = − t3 E e itX 1 X 13 .
n 2n 6
Clearly, |R n ( t)| ≤ Cn−3/2 for a constant C (that depends on t but not n). Hence
nR n ( t) → 0 and by Exercise 2.53 we conclude that for each fixed t ∈ R,
¶n
t2
µ
t2
ψ n ( t) = 1 − + R n ( t) → e − 2
2n
which is the c.f of N (0, 1). ■

2.18. CLT for triangular arrays

The CLT does not really require the third moment assumption, and we can mod-
ify the above proof to eliminate that requirement. Instead, we shall prove an even
more general theorem, where we don’t have one infinite sequence, but the random
variables that we add to get S n depend on n themselves.
Theorem 2.55 (Lindeberg Feller CLT). Suppose X n,k , k ≤ n, n ≥ 1, are random
variables. We assume that
(1) For each n, the random variables X n,1 , . . . , X n,n are defined on the same prob-
ability space, are independent and have finite second moments.
(2) E[ X n,k ] = 0 and nk=1 E[ X n,k
2
] → σ2 , as n → ∞.
P
Pn 2
(3) For any δ > 0, we have k=1 E[ X n,k 1| X n,k |>δ ] → 0 as n → ∞.
 2.18. CLT FOR TRIANGULAR ARRAYS 49

S
Corollary 2.56. Let X n be i.i.d, having zero mean and unit variance. Then, pn
n
converges in distribution to N (0, 1).
1
P ROOF. Let X n,k = n− 2 X k fo r k = 1, 2, . . . , n. Then, E[ X n,k ] = 0 while nk=1 E[ X n,k 2
P
]=
1 PN 2 2 Pn 2 2
n k=1 E[ X 1 ] = σ , for each n . Further, k=1
E[ X 1
n,k | X n,k |>δ
] = E[ X 1 p ] which
1 | X 1 |>δ n
goes to zero as n → ∞ by DCT, since E[ X 12 ] < ∞. Hence the conditions of Lindeberg
S
Feller theorem are satisfied and we conclude that pn converges in distribution to
n
N (0, 1). ■

Now we prove the Lindeberg-Feller CLT. As in the previous section, we need a

fact comparing a product to an exponential.

Exercise
¯ Q 2.57. Q If z k , wk¯ are complex numbers with absolute value bounded by θ ,
then ¯ nk=1 z k − nk=1 wk ¯ ≤ θ n−1 nk=1 | z k − wk |.
P

P ROOF. (Lindeberg-Feller CLT). The characteristic function of S n = X n,1 +. . .+

n
X n,n is given by ψn ( t) = E e itX n,k . Again, we shall use the Taylor expansion of
Q £ ¤
k=1
e itx , but we shall need both the second and first order expansions.
( ∗
itx 1 + itx − 12 t2 x2 − 6i t3 e itx x3 for some x∗ ∈ [0, x] or [ x, 0].
e = +
1 + itx − 21 t2 e itx x2 for some x+ ∈ [0, x] or [ x, 0].
Fix δ > 0 and use the first equation for | x| ≤ δ and the second one for | x| > δ to write
1 1| x|>δ 2 2 + i 1| x|≤δ 3 3 itx∗
e itx = 1 + itx − t2 x2 + t x (1 − e itx ) − t x e .
2 2 6
Apply this with x = X n,k , take expectations and write σ2n,k := E[ X n,k
2
] to get

1
E[ e itX n,k ] = 1 − σ2n,k t2 + R n,k ( t)
2
+ ´i
itX ∗
h ³ h i
t2 itX 3
2
where, R n,k ( t) := 2 E 1| X n,k |>δ X n,k 1 − e n,k − it6 E 1| X n,k |≤δ X n,k
3
e n,k . We can
bound R n,k ( t) from above by using | X n,k |3 1| X n,k |≤δ ≤ δ X n,k
2
and |1 − e itx | ≤ 2, to get
h i | t |3 δ h i
(2.17) |R n,k ( t)| ≤ t2 E 1| X n,k |>δ X n,k
2
+ 2
E X n,k .
6
We want to apply Exercise 2.57 to z k = E e itX n,k and wk = 1 − 21 σ2n,k t2 . Clearly
£ ¤

| z k | ≤ 1 by properties of c.f. If we prove that max σ2n,k → 0, then it will follow that
k≤ n
|wk | ≤ 1 and hence with θ = 1 in Exercise 2.57, we get
n h i Y n µ 1
¶ n
E e itX n,k − 1 − σ2n,k t2 ¯ ≤
¯Y ¯ X
lim sup ¯ lim sup |R n,k ( t)|
n→∞ k=1 k=1 2 n→∞ k=1
1 3 2
≤ | t| σ δ (by 2.17)
6
h i
To see that max σ2n,k → 0, fix any δ > 0 note that σ2n,k ≤ δ2 + E X n,k
2
1| X n,k |>δ from
k≤ n
which we get
n h i
max σ2n,k ≤ δ2 + 2
1| X n,k |>δ → δ2 .
X
E X n,k
k≤ n k=1
50 2. INDEPENDENT RANDOM VARIABLES

As δ is arbitrary, it follows that max σ2n,k → 0 as n → ∞. As δ > 0 is arbitrary, we get

k≤ n
n h
i n µ 1
¶
E e itX n,k = lim 1 − σ2n,k t2 .
Y Y
(2.18) lim
n→∞
k=1
n→∞
k=1 2
1
For n large enough, max σ2n,k ≤ 2 and then
k≤ n

1
− 12 σ2n,k t2 − 41 σ4n,k t4 − 1 σ2 t 2
e ≤ 1 − σ2n,k t2 ≤ e 2 n,k .
2
Pn
Take product over k ≤ n, and observe that k=1 σ4n,k → 0 (why?). Hence,
n µ 1
¶
σ2 t 2
1 − σ2n,k t2 → e− 2 .
Y
k=1 2
Pn d
From 2.18 and Lévy’s continuity theorem, we get k=1
X n,k → N (0, σ2 ). ■

2.19. Limits of sums of random variables

Let X i be an i.i.d sequence of real-valued r.v.s. If the second moment is finite,
we have see that the sums S n converge to Gaussian distribution after location (by
p
nE[ X 1 ]) and scaling (by n). What if we drop the assumption of second moments?
Let us first consider the case of Cauchy random variables to see that such results
may be expected in general.
1
Example 2.58. Let X i be i.i.d Cauchy(1), with density π(1+ x2 )
. Then, one can check
Sn
that n has exactly the same Cauchy distribution! Thus, to get distributional con-
Sn d a
vergence, we just write n → C1 . If X i were i.i.d with density π(a2 +( x− b)2 )
(which can
X i −b
be denoted C a,b with a > 0, b ∈ R), then a are i.i.d C 1 , and hence, we get
S n − nb d
→ C1 .
an
This is the analogue of CLT, except that the location change is nb instead of nE[ X 1 ],
p
scaling is by n instead of n and the limit is Cauchy instead of Normal.

This raises the following questions.

(1) For general i.i.d sequences, how are the location and scaling parameter
1
determined, so that b−n (S n − a n ) converges in distribution to a non-trivial
measure on the line?
(2) What are the possible limiting distributions?
(3) What are the domains of attraction for each possible limiting distribution,
1 d
e.g., for what distributions on X 1 do we get b−
n (S n − a n ) → C 1 ?
It turns out that for each α ≤ 2, there is a unique (up to scaling) distribution µα such
d 1
that X + Y = 2 α X if X , Y ∼ µ are independent. This is known as the symmetric α-
α
stable distribution and has characteristic function ψα ( t) = e− c| t| . For example, the
normal distribution corresponds to α = 2 and the Cauchy to α = 1. If X i are i.i.d µα ,
d
then is is easy to see that n−1/α S n → µα . The fact is that there is a certain domain of
attraction for each stable distribution, and for i.i.d random variables from any such
d
distribution n−1/α S n → µα .
 2.20. POISSON CONVERGENCE FOR RARE EVENTS 51

2.20. Poisson convergence for rare events

Theorem 2.59. Let A n,k be events in a probability space. Assume that
(1) For each n, the events A n,1 , . . . , A n,n are independent.
n
P( A n,k ) → λ ∈ (0, ∞) as n → ∞.
P
(2)
k=1
(3) max P( A n,k ) → 0 as n → ∞.
k≤ n
Pn d
Then k=1
1 A n,k → Pois(λ).
Pn
P ROOF. Let p n,k = P( A n,k ) and X n = k=1
1 A n,k . By assumption (3), for large
enough n, we have p n,k ≤ 1/2 and hence
− p n,k − p2n,k
(2.19) e ≤ 1 − p n,k ≤ e− p n,k .
Thus, for any fixed ` ≥ 0,
à !
A cj
X
P( X n = `)
\ \
= P Aj
S ⊆[ n]:|S |=` j ∈S j 6∈S
X Y Y
= (1 − p n, j ) p n, j
S ⊆[ n]:|S |=` j 6∈S j ∈S
n
Y X Y p n, j
(2.20) = (1 − p n, j ) .
j =1 S ⊆[ n]:|S |=` j ∈S 1 − p n, j

By assumption k p n,k → λ. Together with the third assumption, this implies that
P
P 2
k p n,k → 0. Thus, using 2.19 we see that
n
(1 − p n, j ) −→ e−λ .
Y
(2.21)
j =1

Let q n, j = p n, j /(1 − p n, j ). The second factor in 2.20 is

X Y 1 X Ỳ
q n, j = q n, j i
S ⊆[ n]:|S |=` j ∈S k! j1 ,... j` i=1
distinct
à !`
1 X 1 X Ỳ
= q n, j − q n, j i .
`! j `! j 1 ,... j ` i =1
not distinct

The first term converges to λ` /`!. To show that the second term goes to zero, divide
it into cases where j a = j b with a, b ≤ ` being chosen in one of `2 ways. Thus we get
¡ ¢

à !à !`−1
X Ỳ ` X n
q n, j i ≤ qj max q n, j → 0
j 1 ,... j ` i =1 2 j=1 j
not distinct

q n, j → λ and max j q n, j → 0. Put this together with

P
because like p n, j we also have j
2.20 and 2.21 to conclude that
λ`
P( X n = `) → e−λ .
`!
d
Thus X n → Pois(λ). ■

Exercise 2.60. Use characteristic functions to give an alternate proof of Theorem 2.59.
52 2. INDEPENDENT RANDOM VARIABLES

As a corollary, Bin( n, p n ) → Pois(λ) if n → ∞ and p n → 0 in such a way that

np n → λ. Contrast this with the Binomial convergence to Normal (after location and
scale change) if n → ∞ but p is held fixed.
 CHAPTER 3

Brownian motion

In this chapter we introduce a very important probability measure, called Wiener

measure on the space C [0, ∞) of continuous functions on [0, ∞). We shall barely
touch the surface of this very deep subject. A C [0, ∞)-valued random variable whose
distribution is the Wiener measure, is called Brownian motion. First we recall a few
basic facts about the space of continuous functions.

3.1. Brownian motion and Winer measure

Let C [0, 1] and C [0, ∞) be the space of real-valued continuous functions on [0, 1]
and [0, ∞, respectively. On C [0, 1] the sup-norm k f − gksup defines a metric. On
C [0, ∞) a metric may be defined by setting
X∞ 1 k f − gksup[0,n]
d ( f , g) = n 1 + k f − gk
.
n=1 2 sup[0,n]

It is easy to see that f n → f in this metric if and only if f n converges to f uniformly

on compact subsets of R. The metric itself does not matter to us, but the induced
topology does, and so does the fact that this topology can be induced by a metric
that makes the space complete and separable. In this section, we denote the corre-
sponding Borel σ-algebras by B1 and B∞ . Recall that a cylinder set is a set of the
form
(3.1) C = { f : f ( t1 ) ∈ A 1 , . . . , f ( t k ) ∈ A k }
for some t 1 < t 2 < . . . < t k , A j ∈ B (R) and some k ≥ 1. Here is a simple exercise.
Exercise 3.1. Show that B1 and B∞ are generated by finite dimensional cylinder
sets (where we restrict t k ≤ 1 in case of C [0, 1]).
As a consequence of the exercise, if two Borel probability measures agree on
all cylinder sets, then they are equal. We define Wiener measure by specifying its
probabilities on cylinder sets. Let φσ2 denote the density function of N (0, σ2 ).
Definition 3.2. Wiener measure µ is a probability measure on (C [0, ∞), B∞ ) such
that Z Z
µ(C ) = . . . φ t1 ( x1 )φ t2 − t1 ( x2 ) . . . φ t k − t k−1 ( xk ) dx1 . . . dxk
A1 Ak
for every cylinder set C = { f : f ( t 1 ) ∈ A 1 , . . . , f ( t k ) ∈ A k }. Clearly, if Wiener measure
exists, it is unique.
We now define Brownian motion. Let us introduce the term Stochastic process
to indicate a collection of random variables indexed by an arbitrary set - usually, the
indexing set is an interval of the real line or of integers, and the indexing variable
may have the interpretation of ‘time’.
53
54 3. BROWNIAN MOTION

Definition 3.3. Let (Ω, F , P) be any probability space. A stochastic process (B t ) t≥0
indexed by t ≥ 0 is called Brownian motion if
(1) B0 = 0 w.p.1.
(2) (Finite dimensional distributions). For any k ≥ 1 and any 0 ≤ t 1 < t 2 <
. . . < t k , the random variables B t1 , B t2 − B t1 , . . . , B t k − B t k−1 are independent,
and for any s < t we have B t − B s ∼ N (0, t − s).
(3) (Continuity of sample paths). For a.e. ω ∈ Ω, the function t → Bω t is a
continuous.

In both definitions, we may restrict to t ∈ [0, 1], and the corresponding measure
on C [0, 1] is also called Wiener measure and the corresponding stochastic process
(B t )0≤ t≤1 is also called Brownian motion.
The following exercise shows that Brownian motion and Wiener measure are
two faces of the same coin (just like a normal random variable and the normal dis-
tribution).

Exercise 3.4. (1) Suppose (B t ) t≥0 is a Brownian motion on some probability

space (Ω, F , P). Define a map B : Ω → C [0, ∞) by setting B(ω) to be the
function whose value at t is given by B t (ω). Show that B is a measurable
function, and the induced measure PB−1 on (C [0, ∞), B∞ ) is the Wiener
measure.
(2) Conversely, suppose the Wiener measure µ exists. Let Ω = C [0, ∞), F = B∞
and P = µ. For each t ≥ 0, define the r.v B t : Ω → C [0, ∞) by Bω t = ω( t) for
ω ∈ C [0, ∞). Then, show that the collection (B t ) t≥0 is a Brownian motion.

The exercise shows that if the Wiener measure exists, then Brownian motion
exists, and conversely. But it is not at all clear that either Brownian motion or
Wiener measure exists.

3.2. Some continuity properties of Brownian paths - Negative results

We construct Brownian motion in the next section. Now, assuming the exis-
tence, we shall see some very basic properties of Brownian paths. We can ask many
questions about the sample paths. We just address some basic questions about the
continuity of the sample paths.
Brownian paths are quite different from the ‘nice functions’ that we encounter
regularly. For example, almost surely, there is no interval on which Brownian motion
is increasing (or decreasing)! To see this, fix an interval [a, b] and points a = t 0 < t 1 <
. . . < t k = b. If W was increasing on [a, b], we must have W ( t i ) − W ( t i−1 ) ≥ 0 for
i = 1, 2 . . . , k. These are independent events that have probability 1/2 each, whence
the probability for W to be increasing on [a, b] is at most 2−k . As k is arbitrary, the
probability is 0. Take intersection over all rational a < b to see that almost surely,
there is no interval on which Brownian motion is increasing.

Warm up question: Fix t 0 ∈ [0, 1]. What is the probability that W is differentiable
at t 0 ?
Answer: Let I n = [ t 0 +2−n , t 0 +2−n+1 ]. If W 0 ( t 0 ) exists, then limn→∞ 2n k>n ∆W ( I k ) =
P

W 0 ( t 0 ). Whether the limit on the left exists, is a tail event of the random variables
∆W ( I n ) which are independent, by properties of W . By Kolmogorov’s law, the event
that this limit exists has probability 0 or 1. If the probability was 1, we would have
 3.3. SOME CONTINUITY PROPERTIES OF BROWNIAN PATHS - POSITIVE RESULTS 55

a.s.
2n (W ( t 0 + 2−n ) − W ( t 0 )) → W 0 ( t 0 ), and hence also in distribution. But for each n, ob-
serve that 2n (W ( t 0 + 2−n ) − W ( t 0 )) ∼ N (0, 2n ) which cannot converge in distribution.
Hence the probability that W is differentiable at t 0 is zero!
Remark 3.5. Is the event A t0 := {W is differentiable at t 0 } measurable? We haven’t
shown this! Instead what we showed was that it is contained in a measurable set of
Wiener measure zero. In other words, if we complete the Borel σ-algebra on C [0, 1]
w.r.t Wiener measure (or complete whichever probability space we are working in),
then under the completion A t0 is measurable and has zero measure. This will be the
case for the other events that we consider.

For any t ∈ [0, 1], we have shown that W is a.s. not differentiable at t. Can we
claim that W is nowhere differentiable a.s? No! P( A t ) = 0 and hence P( t∈Q A t ) = 0
S

but we cannot say anything about uncountable unions. For example,P(Wt = 1) = 0

for any t. But P(Wt = 1 for some t) > 0 because {Wt = 1 for some t} ⊃ {W1 > 1} and
P(W1 > 1) > 0.
Notation: For f ∈ C [0, 1] and an interval I = [a, b] ⊆ [0, 1], let ∆ f ( I ) := | f ( b) − f (a)|.
Theorem 3.6 (Paley, Wiener and Zygmund). Almost surely, W is nowhere differ-
entiable.
P ROOF. (Dvoretsky, Erdös and Kakutani). Fix M < ∞. For any n ≥ 1, consider
the event A (nM ) := ∃0 ≤ j ≤ 2n − 3 : |∆W ( I n,p )| ≤ M 2−n for p = j, j + 1, j + 2 . ∆W ( I n,p )
© ª

has N (0, 2−n ) distribution, hence P(|∆W ( I n,p )| ≤ M 2−n ) = P(|χ| ≤ 2−n/2 ) ≤ 2−n/2 . By
independence of ∆W ( I n, j ) fo rdistinct j , we get
³ ´3
P( A (nM ) ) ≤ (2n − 2) 2−n/2 ≤ 2−n/2 .

Therefore P( A (nM ) i.o.) = 0.

Let f ∈ C [0, 1]. Suppose f is differentiable at some point t 0 with | f 0 ( t 0 )| ≤ M /2.
Then, for some δ > 0, we have ∆ f ([a, b]) ≤ | f ( b) − f ( t)| + | f ( t) − f (a)| ≤ M | b − a| for all
a, b ∈ [ t 0 − δ, t 0 + δ]. In particular, for large n so that 2−n+2 < δ, there will be three
consecutive dyadic intervals I n, j , I n, j+1 , I n, j+2 that are contained in [ t 0 − δ, t 0 + δ]. and
for each of p = j, j + 1, j + 2 we have ∆ f ( I n,p )| ≤ M 2−n .
Thus the event that W is differentiable somewhere with a derivative less than
M (in absolute value), is contained in { A (nM ) i.o.} which has probability zero. Since
this is true for every M , taking union over integer M ≥ 1, we get the statement of the
theorem. ■

Exercise 3.7. For f ∈ C [0, 1], we say that t 0 is an α-Hölder continuity point of f if
| f ( s )− f ( t )
lim sups→ t |s− t|α < ∞. Show that almost surely, Brownian motion has no α-Hölder
continuity point for any α > 12 .
We next show that Brownian motion is everywhere α-Hölder continuous for any
α < 21 . Hence together with the above exercie, we have made almost the best possible
statement. Except, these statements do not answer what happens for α = 12 .

3.3. Some continuity properties of Brownian paths - Positive results

To investigate Hölder continuity for α < 1/2, we shall need the following lemma
which is very similar to Kolmogorov’s maximal inequality (the difference is that
56 3. BROWNIAN MOTION

there we only assumed second moments, but here we assume that the X i are normal
and hence we get a stronger conclusion).
µ ¶ 2
− x
Lemma 3.8. Let X 1 , . . . , X n be i.i.d N (0, σ2 ). Then, P max S k ≥ x ≤ e 2σ2 n .
k≤ n

P ROOF. Let τ = min{ k : S k ≥ x£} and¤ set τ = n if there is no such £k. Then,
P(maxk≤n S k ≥ x) = P(S τ ≥ x) ≤ e−θ x E eθ Sτ for any θ > 0. Recall that for E eθ N (0,b) =
¤
2 b2 /2
eθ . Thus, as in the proof of Kolmogorov’s inequality
1 2 2
h i X n h i Xn h i h i
e 2 θ σ n = E eθ S n = E 1τ=k eθ S k eθ(S n −S k ) = E 1τ=k eθ S k E eθ(S n −S k )
k=1 k=1
n h i 1 2 2
n h i h i
E 1τ=k eθ S k e 2 θ ( n − k )σ E 1τ=k eθ S k = E eθ Sτ .
X X
= ≥
k=1 k=1
1 2 2
Thus, P(S τ > x) ≤ e−θ x e 2θ σ n
x
. Set θ = n σ2
to get the desired inequality. ■

Corollary 3.9. Let W be Brownian motion. Then, for any a < b, we have
x2
µ ¶
P max |Wt − Ws | > x ≤ 2 e− 8(b−a)
s,t∈[a,b]

P ROOF. Fix n ≥ 1 and divide [a, b] into n intervals of equal length. Let X i =
W (a + k/ n) − W (a + ( k − 1)/ n) for k = 1, 2, . . . , n. Then X i are i.i.d N (0, ( b − a)/ n). By the
lemma, P( A n ) ≤ exp{− x2 /2( b − a)} where A n := {maxk≤n |W (a + nk )−W (a)| > x}. Observe
2
that A n are increasing and therefore P( A n ) = lim P( A n ) ≤ exp{− 2(bx−a) }.
S
© ª S ¡ ¢
Evidently max t∈[a,b] Wt − Wa > x ⊆ n A n and hence P max t∈[a,b] Wt − Wa > x ≤
2
exp{− 2(bx−a) }. Putting absolute values on Wt − Ws increases the probability by a factor
of 2. Further, if |Wt − Ws | > x for some s, t, then |Wt − Wa | ≥ 2x or |Ws − Wa | ≥ 2x . Hence,
we get the inequality in the statement of the corollary. ■

Theorem 3.10 (Paley, Wiener and Zygmund). For any α < 21 , almost surely, W is
α-Hölder continuous on [0, 1].

P ROOF. Let ∆∗ f ( I ) = max{| f ( t) − f ( s) : t, s ∈ I }. By the corollary, P(∆∗ W ( I ) > x) ≤

2 exp{− x2 | I |−1 /8}. Fix n ≥ 1 and apply this to I n, j , j ≤ 2n − 1 to get
µ ¶ n o
− nα
P max n
∆∗
( I n, j ) ≥ 2 ≤ 2n exp − c2n(1−2α)
j ≤2 −1

which is summable. By Borel-Cantelli lemma, we conclude that there is some (almost

surely finite) random constant A such that ∆∗ ( I n, j ) ≤ A 2−nα for all dyadic intervals
I n, j .
Now consider any s < t. Pick the unique n such that 2−n−2 < t − s ≤ 2−n−1 .
Then, for some j , the dyadic interval I n, j contains both s and t. Hence |Wt − Ws | ≤
∆∗ ( I n−1, j ) ≤ A 2−nα ≤ A 0 | s − t|α whre A 0 := A 22α . Thus, W is a.s α-Hölder continu-
ous. ■

3.4. Lévy’s construction of Brownian motion

Let (Ω, F , P) be any probability space with i.i.d N (0, 1) random variables χ1 , χ2 , . . .
defined on it. The idea is to construct a sequence of random functions on [0, 1] whose
finite dimensional distributions agree with that of Brownian motion at more and
more points.
 3.4. LÉVY’S CONSTRUCTION OF BROWNIAN MOTION 57

Step 1: A sequence of piecewise linear random functions: Let W1 ( t) := tχ1

for t ∈ [0, 1]. Clearly W0 (1) − W0 (0) ∼ N (0, 1) as required for BM, but for any other t,
W0 ( t) ∼ N (0, t2 ) whereas we want it to be N (0, t) distribution..
Next, define

1 1 0 if t = 0.
 2 χ2 if t = 2 .



  1 χ + 1 χ if t = 1 .

1 2 2
F0 ( t) := 0 if t = 0 or 1. and W1 := W0 + F0 = 2 2
 χ1 if t = 1.

linear in between.
 

linear in between.


W1 (1) − W1 (1/2) = 21 χ1 − 12 χ2 and W1 (1/2) − W1 (0) = 12 χ1 + 12 χ2 are clearly i.i.d N (0, 21 ).

Proceeding inductively, suppose after n steps we have defined functions W0 ,W1 , . . . ,Wn
such that for any k ≤ n,
(1) Wk is linear on each dyadic interval [ j 2−k , ( j + 1)2−k ] for j = 0, 1, . . . , 2k − 1.
(2) The 2k r.v.s Wk (( j + 1)2−k ) − Wk ( j 2−k ) for j = 0, 1, . . . , 2k − 1 are i.i.d N (0, 2−k ).
(3) If t = j 2−k , then W` ( t) = Wk ( t) for any ` > k (and ` ≤ n).
(4) Wk is defined using only χ j , j ≤ 2k − 1.
Then define (for some c n to be chosen shortly)
2 j +1 n
 c n χ j+2n if t = 2n+1 , 0 ≤ j ≤ 2 − 1.


F n ( t) = 0 if t = 22n+j 1 , 0 ≤ j ≤ 2n . and Wn+1 := Wn + F n .

linear in between.


Does Wn+1 satisfy the four properties listed above? The property (1) is evident by
definition. To see (3), since F n vanishes on dyadics of the form j 2−n , it is clear
that Wn+1 = Wn on these points. Equally easy is (4), since we use 2n fresh normal
variables (and we had used 2n − 1 previously).
This leaves us to check (2). For ease of notation, for a function f and an interval
I = [a, b] denote the increment of f over I by let ∆ f ( I ) := f ( b) − f (a).
Let 0 ≤ j ≤ 2n −1 and consider the dyadic interval I j = [ j 2−n , ( j +1)2−n ] which gets
broken into two intervals, L j = [(2 j )2−n−1 , (2 j + 1)2−n−1 ] and R j = [(2 j + 1)2−n−1 , (2 j +
2)2−n−1 ] at level n + 1. Wn is linear on I j and hence, ∆Wn (L j ) = ∆Wn (R j ) = 12 ∆Wn ( I j ).
On the other hand, ∆F n (L j ) = c n χ j+2n = −∆F n (R j ). Thus, the increments of Wn+1 on
L j and R j are given by
1 1
∆Wn+1 (L j ) = ∆Wn ( I j ) + c n χ j+2n and ∆Wn+1 (R j ) = ∆Wn ( I j ) − c n χ j+2n .
2 2
Inductively, we know that ∆Wn ( I j ), j ≤ 2n − 1 are i.i.d N (0, 2−n ) and independent of
χ j+2n , j ≥ 0. Therefore, ∆Wn+1 (L j ), ∆Wn (R j ), j ≤ 2n − 1 are jointly normal (being
linear combinations of independent normals). The means are clearly zero. To find
the covariance, observe that for distinct j , these random variables are independent.
Further,
1
Cov(∆Wn+1 (L j ), ∆Wn+1 (R j )) = Var(∆Wn ( I j )) − c2n = 2−n−2 − c2n .
4
Thus, if we choose c n := 2−(n+2)/2 , then the covariance is zero, and hence ∆Wn+1 (L j ),
∆Wn+1 (R j ), j ≤ 2n − 1 are independent. Also,
1 1
Var(∆Wn+1 (L j )) = Var(∆Wn ( I j )) + c2n = 2−n + 2−n−2 = 2−n−1 .
4 4
Thus, Wn+1 satisfies (2).
58 3. BROWNIAN MOTION

Step 2: The limiting random function: We found an infinite sequence of functions

W1 ,W2 , . . . satisfying (1)-(4) above. We want to show that almost surely, the sequence
of functions Wn is uniformly convergent. For this, we need the fact that P(|χ1 | > t) ≤
2
e− t /2 for any t > 0.
Let k · k denote the sup-norm on [0, 1]. Clearly kF m k = c m sup{|χ j+2m | : 0 ≤ j ≤
2m − 1}. Hence
1
µ ¶
p ¢ 2
n m−1 o
P kF m k > c m ≤ 2m P |χ| > p ≤ 2m e− c m /2 = 2m exp −2 2
¡
cm
which is clearly summable in m. Thus, by the Borel-Cantelli lemma, we deduce
p
that almost surely, kF m k ≤ c m for all but finitely many m. Then, we can write
p
kF m k ≤ A c m for all m, where A is a random constant (finite a.s.).
P mP
−1
Thus, m kF m k < ∞ a.s. Since kWn − Wm k ≤ kF k k, it follows that Wn is almost
k= n
surely a Cauchy sequence in C [0, 1], and hence converges uniformly to a (random)
continuous function W .

Step 3: Properties of W : We claim that W has all the properties required of Brow-
nian motion. Since Wn (0) = 0 for all n, we also have W (0) = 0. We have already shown
that t → W ( t) is a continuous function a.s. (since W is the uniform limit of continuous
functions). It remains to check the finite dimensional dstributions. If s < t are dyadic
rationals, say, s = k2−n and t = `2−n , then denoting I n, j = [ j 2−n , ( j + 1)2−n ], we get
that W ( s) = Wn ( s) = kj=−01 ∆Wn ( I n, j ) and W ( t) − W ( s) = `j=−k1 ∆Wn ( I n, j ). As ∆Wn ( I n, j )
P P

are i.i.d N (0, 2−n ) we get that W ( s) and W ( t) − W ( s) are independent N (0, s) and
N (0, t − s) respectively.
Now, suppose s < t are not necessarily dyadics. We can pick s n , t n that are
dyadics and converge to s, t respectively. Since W ( s n ) ∼ N (0, s n ) and W ( t) − W ( s) ∼
N (0, t n − s n ) are independent, by general facts about a.s convergence and weak con-
vergence, we see that W ( s) ∼ N (0, s) and W ( t) − W ( s) ∼ N (0, t − s) and the two are
independent. The case of more than two intervals is dealt similarly. Thus we have
proved the existence of Brownian motion on the time interval [0, 1].

Step 4: Extending to [0, ∞): From a countable collection of N (0, 1) variables, we

were able to construct a BM W on [0, 1]. By subdividing the collection of Gaussians
into a disjoint countable collection of countable subsets, we can construct i.i.d Brow-
nian motions B1 , B2 , . . .. Then, define for any t ≥ 0,
b tX
c−1
B ( t) = B j (1) + Bb tc ( t − b tc).
j =1

B is just a concatenation of B1 , B2 , . . .. It is not difficult to check that B is a Brownian

motion on [0, ∞).
Theorem 3.11 (Wiener). Brownian motion exists. Equivalenty Wiener measure ex-
ists.
 APPENDIX A

Characteristic functions as tool for studying weak

convergence

Defintions and basic properties

Definition A.1. Let µ be a probability measure on R. The function ψµ : Rd → R define
by ψµ ( t) := R e itx d µ( x) is called the characteristic function or the Fourier transform of
R

µ. If X is a random variable on a probability space, we sometimes say “characteristic

function of X ” to mean the c.f of its distribution. We also write µ̂ instead of ψµ .

There are various other “integral transforms” of a measure that are closely re-
lated to the c.f. For example, if we take ψµ ( it) is the moment generating function
of µ (if it exists). For µ supported on N, its so called generating function Fµ ( t) =
k
k≥0 µ{ k} t (which exists for | t| < 1 since µ is a probability measure) can be written
P

as ψµ (− i log t) (at least for t > 0!) etc. The characteristic function has the advantage
that it exists for all t ∈ R and for all finite measures µ.
The following lemma gives some basic properties of a c.f.

Lemma A.2. Let µ ∈ P (R). Then, µ̂ is a uniformly continuous function on R with

|µ̂( t)| ≤ 1 for all t with µ̂(0) = 1. (equality may be attained elsewhere too).

P ROOF. Clearly µ̂(0) = 1 and |µ̂( t)| ≤ 1. U ■

The importance of c.f comes from the following facts.

(A) It transforms well under certain operations of measures, such as shifting a
scaling and under convolutions.
(B) The c.f. determines the measure.
d
(C) µ̂n ( t) → µ̂( t) pointwise, if and only if µn → µ.
(D) There exist necessary and sufficient conditions for a function ψ : R → C to
be the c.f o f a measure. Because of this and part (B), sometimes one defines
a measure by its characteristic function.

(A) Transformation rules

Theorem A.3. Let X , Y be random variables.
(1) For any a, b ∈ R, we have ψaX +b ( t) = e ibt ψ X (at).
(2) If X , Y are independent, then ψ X +Y ( t) = ψ X ( t)ψY ( t).

P ROOF. (1) ψaX +b ( t) = E[ e it(aX +b) ] = E[ e itaX ] e ibt = e ibt ψ X (at).

(2) ψ X +Y ( t) = E[ e it( X +Y ) ] = E[ e itX e itY ] = E[ e itX ]E[ e itY ] = ψ X ( t)ψY ( t).
■
59
60 A. CHARACTERISTIC FUNCTIONS AS TOOL FOR STUDYING WEAK CONVERGENCE

Examples.
(1) If X ∼ Ber( p), then ψ X ( t) = pe it + q where q = 1 − p. If Y ∼ Binomial( n, p),
d it n
then, Y = X 1 + . . . + X n where X k are i.i.d Ber( p). Hence, ψY ( t) = ( pe + q) .
(2) If X ∼ Exp(λ), then ψ X ( t) = 0 λ e−λ x e itx dx = λ−1it . If Y ∼ Gamma(ν, λ),
R∞
d
then if ν is an integer, then Y = X 1 + . . . + X n where X k are i.i.d Exp(λ).
Therefore, ψY ( t) = (λ−1it)ν .
(3) Y ∼ Normal(µ, σ2 ). Then, Y = µ + σ X , where X ∼ N (0, 1) and by the tran-
sofrmatin rules, ψY ( t) = e iµ t ψ X (σ t). Thus it suffices to find the c.f of N (0, 1).
x2 2
1 1
Z 2 2
µ Z ¶
itx − 2σ2 − σ 2t − ( x− it2)
ψ X ( t) = p e e dx = e p e 2 σ dx .
σ 2π R σ 2π R
It appears that the stuff inside the brackets is equal to 1, since it looks
like the integral of a normal density with mean it and variance σ2 . But if
the mean is complex, what does it mean?! I gave a rigorous proof that the
stuff inside brackets is indeed equal to 1, in class using contour integration,
which will not be repeated here. The final concusion is that N (µ, σ2 ) has c.f
σ2 t 2
e itµ− 2 .

(B) Inversion formulas

Theorem A.4. If µ̂ = ν̂, then µ = ν.
2 2
P ROOF. Let θσ denote the N(0, σ2 ) distribution and let φσ ( x) = p1 e− x /2σ and
σ 2π
2 2
Φσ ( x) = −∞ φσ ( u) du and θ̂σ ( t) = e−σ t /2 denote the density and cdf and characteris-
Rx

tic functions, respectively. Then, by Parseval’s identity, we have for any α,

Z Z
e− iα t µ̂( t) d θσ ( t) = θ̂σ ( x − α) d µ( x)
p Z
2π
= φ 1 (α − x) d µ( x)
σ σ

where the last line comes by the explicit Gaussian form of θ̂σ . Let f σ (α) := pσ
R − iα t
e µ̂( t) d θσ ( t)
2π
and integrate the above equation to get that for any finite a < b,
Z b Z bZ
f σ (α) d α = φ 1 (α − x ) d µ ( x ) d µ ( x )
a a R σ
Z Z b
= φ 1 (α − x ) d α d µ ( x ) (by Fubini)
σ
ZR ³ a ´
= Φ 1 (α − a) − Φ 1 (α − b) d µ( x).
R σ σ

Now, we let σ → ∞, and note that


0
 if u < 0.
Φ 1 ( u) → 1 if u > 0.
σ 
1
2 if u = 0.
Further, Φσ−1 is bounded by 1. Hence, by DCT, we get
Z b
1 1
Z · ¸
lim f σ (α) d α = 1(a,b) ( x) + 1{a,b} ( x) d µ( x) = µ(a, b) + µ{a, b}.
σ→∞ a 2 2
 (B) INVERSION FORMULAS 61

Now we make two observations: (a) that f σ is determined by µ̂, and (b) that the
measure µ is determined by the values of µ(a, b) + 21 µ{a, b} for all finite a < b. Thus,
µ̂ determines the measure µ. ■
Corollary A.5 (Fourier inversion formula). Let µ ∈ P (R).
(1) For all finite a < b, we have
1 1 1 e− iat − e− ibt 2
Z
− t
(A.1) µ(a, b) + µ{a} + µ{ b} = lim µ̂( t) e 2σ2 dt
2 2 σ→∞ 2π R it
R |µ̂( t)| dt < ∞, then µ has a continuous density given by
R
(2) If
1
Z
f ( x) := µ̂( t) e− ixt dt.
2π R
Rb
P ROOF. (1) Recall that the left hand side of (A.1) is equal to limσ→∞ a f σ
where f σ (α) := pσ e− iα t µ̂( t) d θσ ( t). Writing out the density of θσ we see
R
2π
that
Z b
1 b 2
Z Z
− t
f σ (α) d α = e− iα t µ̂( t) e 2σ2 dtd α
a 2π a R
Z Z b 2
1 − t
= e− iα t µ̂( t) e 2σ2 d α dt (by Fubini)
2π R a
Z − iat
1 e − e− ibt − t
2
= µ̂( t) e 2σ2 dt.
2π R it
Thus, we get the first statement of the corollary.
2
− t
(2) With f σ as before, we have f σ (α) := 21π e− iα t µ̂( t) e 2σ2 dt. Note that the in-
R

tegrand converges to e− iα t µ̂( t) as σ → ∞. Further, this integrand is bounded

by |µ̂( t)| which is assumed to be integrable. Therefore, by DCT, for any α ∈ R,
we conclude that f σ (α) → f (α) where f (α) := 21π e− iα t µ̂( t) dt.
R

Next, note that for any σ > 0, we have | f σ (α)| ≤ C for all α where C =
Rb Rb
|µ̂. Thus, for finite a < b, using DCT again, we get a f σ → a f as σ → ∞.
R

But the proof of Theorem A.4 tells us that

Z b
1 1
lim f σ (α) d α = µ(a, b) + µ{a} + µ{ b}.
σ→∞ a 2 2
1 1
Rb
Therefore, µ(a, b)+ 2 µ{a}+ 2 µ{ b} = a f (α) d α. Fixing a and letting b ↓ a, this
Rb
shows that µ{a} = 0 and hence µ(a, b) = a f (α) d α. Thus f is the density of
µ.
The proof that a c.f. is continuous carries over verbatim to show that
f is continuous (since f is the Furier trnasform of µ̂, except for a change of
sign in the exponent). ■
An application of Fourier inversion formula Recall the Cauchy distribution µ
1
with with density π(1+ x2 )
whose c.f is not easy to find by direct integration (Residue
theorem in complex analysis is a way to compute this integral).
Consider the seemingly unrelated p.m ν with density 12 e−| x| (a symmetrized ex-
ponential, this is also known as Laplace’s distribution). Its c.f is easy to compute and
we get
1 ∞ itx− x 1 0 itx+ x 1 1 1 1
Z Z µ ¶
ˆ ( t) =
nu e dx + e dx = + = .
2 0 2 −∞ 2 1 − it 1 + it 1 + t2
62 A. CHARACTERISTIC FUNCTIONS AS TOOL FOR STUDYING WEAK CONVERGENCE

By the Fourier inversion formula (part (b) of the corollary), we therefore get

1 −| x| 1 1 1
Z Z
e = ν̂( t) e itx dt = e itx dt.
2 2π 2π 1 + t2

This immediately shows that the Cauchy distribution has c.f. e−| t| without having to
compute the integral!!

(C) Continuity theorem

Theorem A.6. Let µn , µ ∈ P (R).
d
(1) If µn → µ then µ̂n ( t) → µ̂( t) pointwise for all t.
d
(2) If µ̂n ( t) → ψ( t) pointwise for all t, then ψ = µ̂ for some µ ∈ P (R) and µn → µ.
d
(1) If µn → mu, then f d µn → f d µ for any f ∈ C b (R) (bounded
R R
P ROOF.
continuous function). Since x → e itx is a bounded continuous function for
any t ∈ R, it follows that µ̂n ( t) → µ̂( t) pointwise for all t.
(2) Now suppose µ̂n ( t) → µ̂( t) pointwise for all t. We first claim that the se-
quence {µn } is tight. Assuming this, the proof can be completed as follows.
Let µn k be any subsequence that converges in distribution, say to ν.
By tightness, nu ∈ P (R). Therefore, by part (a), µ̂n k → ν̂ pointwise. But
obviously, µ̂n k → µ̂ since µ̂n → µ̂. Thus, ν̂ = µ̂ which implies that ν = µ. That
is, any convergent subsequence of {µn } converges in distribution to µ. This
d
shows that µn → µ (because, if not, then there is some subsequence { n k }
and some ² > 0 such that the Lévy distance between µn k and µ is at least
². By tightness, µnk must have a subsequence that converges to some p.m
ν which cannot be equal to µ contradicting what we have shown!).
It remains to show tightness. From Lemma A.7 below, as n → ∞,

Zδ Zδ
c 1 1
µn [−2/δ, 2/δ] (1 − µ̂n ( t)) dt −→ (1 − µ̂( t)) dt
¡ ¢
≤
δ δ
−δ −δ

where the last implication follows by DCT (since 1 − µ̂n ( t) → 1 − µ̂( t) for each
Rδ
t and also |1 − µ̂n ( t)| ≤ 2 for all t. Further, as δ ↓ 0, we get δ1 (1 − µ̂( t)) dt → 0
−δ
(because, 1 − µ̂(0) = 0 and µ̂ is continuous at 0).
Thus, given ² > 0, we can find δ > 0 such that lim supn→∞ µn ([−2/δ, 2/δ] c ) <
². This means that for some finite N , we have µn ([−2/δ, 2/δ] c ) < ² for all
n ≥ N . Now, find A > 2/δ such that for any n ≤ N , we get µn ([−2/δ, 2/δ] c ) < ².
Thus, for any ² > 0, we have produced an A > 0 so that µn ([− A, A ] c ) < ² for
all n. This is the definition of tightness. ■

Lemma A.7. Let µ ∈ P (R). Then, for any δ > 0, we have

Zδ
¢ 1
µ [−2/δ, 2/δ] c ≤ (1 − µ̂( t)) dt.
¡
δ
−δ
 (C) CONTINUITY THEOREM 63

P ROOF. We write
Z δ Z δ Z
(1 − µ̂( t)) dt = (1 − e itx ) d µ( x) dt
−δ −δ R
Z Z δ
= (1 − e itx ) dtd µ( x)
R −δ
sin( xδ)
Z µ ¶
= 2δ − d µ( x )
R x
sin( xδ)
Z µ ¶
= 2δ 1− d µ( x).
R 2 xδ
x δ)
When | x|δ > 2, we have sin( 1
2 xδ ≤ 2 (since sin( xδ) ≤ 1). Therefore, the integrand is at
least 21 when | x| > δ2 and the integrand is always non-negative since | sin( x)| ≤ | x|.
Therefore we get
Z δ
1 ¡
(1 − µ̂( t)) dt ≥ µ [−2/δ, 2/δ] c .
¢
■
−δ 2