Probability Theory

S.R.S.Varadhan
Courant Institute of Mathematical Sciences
New York University

August 31, 2000

2
Contents

1 Measure Theory 7
1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Construction of Measures . . . . . . . . . . . . . . . . . . . . 11
1.3 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Product Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6 Distributions and Expectations . . . . . . . . . . . . . . . . . 28

2 Weak Convergence 31
2.1 Characteristic Functions . . . . . . . . . . . . . . . . . . . . . 31
2.2 Moment Generating Functions . . . . . . . . . . . . . . . . . . 36
2.3 Weak Convergence . . . . . . . . . . . . . . . . . . . . . . . . 38

3 Independent Sums 51
3.1 Independence and Convolution . . . . . . . . . . . . . . . . . . 51
3.2 Weak Law of Large Numbers . . . . . . . . . . . . . . . . . . . 54
3.3 Strong Limit Theorems . . . . . . . . . . . . . . . . . . . . . . 58
3.4 Series of Independent Random variables . . . . . . . . . . . . 61
3.5 Strong Law of Large Numbers . . . . . . . . . . . . . . . . . . 68
3.6 Central Limit Theorem. . . . . . . . . . . . . . . . . . . . . . 70
3.7 Accompanying Laws. . . . . . . . . . . . . . . . . . . . . . . . 76
3.8 Infinitely Divisible Distributions. . . . . . . . . . . . . . . . . 83
3.9 Laws of the iterated logarithm. . . . . . . . . . . . . . . . . . 92

4 Dependent Random Variables 101

4.1 Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.2 Conditional Expectation . . . . . . . . . . . . . . . . . . . . . 108
4.3 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . 112

3
4 CONTENTS

4.4 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . 116

4.5 Stopping Times and Renewal Times . . . . . . . . . . . . . . . 122
4.6 Countable State Space . . . . . . . . . . . . . . . . . . . . . . 123

5 Martingales. 149
5.1 Definitions and properties . . . . . . . . . . . . . . . . . . . . 149
5.2 Martingale Convergence Theorems. . . . . . . . . . . . . . . . 154
5.3 Doob Decomposition Theorem. . . . . . . . . . . . . . . . . . 157
5.4 Stopping Times. . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.5 Upcrossing Inequality. . . . . . . . . . . . . . . . . . . . . . . 164
5.6 Martingale Transforms, Option Pricing. . . . . . . . . . . . . . 165
5.7 Martingales and Markov Chains. . . . . . . . . . . . . . . . . 169

6 Stationary Stochastic Processes. 179

6.1 Ergodic Theorems. . . . . . . . . . . . . . . . . . . . . . . . . 179
6.2 Structure of Stationary Measures. . . . . . . . . . . . . . . . . 184
6.3 Stationary Markov Processes. . . . . . . . . . . . . . . . . . . 187
6.4 Mixing properties of Markov Processes. . . . . . . . . . . . . . 192
6.5 Central Limit Theorem for Martingales. . . . . . . . . . . . . 195
6.6 Stationary Gaussian Processes. . . . . . . . . . . . . . . . . . 199

7 Dynamic Programming and Filtering. 213

7.1 Optimal Control. . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.2 Optimal Stopping. . . . . . . . . . . . . . . . . . . . . . . . . 215
7.3 Filtering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Preface

These notes are based on a first year graduate course on Probability and Limit
theorems given at Courant Institute of Mathematical Sciences. Originally
written during 1997-98, they have been revised during academic year 1998-
99 as well as in the Fall of 1999. I want to express my appreciation to those
who pointed out to me several typos as well as suggestions for improvement.
I want to mention in particular the detailed comments from Professor Charles
Newman and Mr Enrique Loubet. Chuck used it while teaching the course
in 98-99 and Enrique helped me as TA when I taught out of these notes
again in the Fall of 99. These notes cover about three fourths of the course,
essentially discrete time processes. Hopefully there will appear a companion
volume some time in the near future that will cover continuos time processes.
A small amount measure theory that is included. While it is not meant to
be complete, it is my hope that it will be useful.

5
6 CONTENTS