Probability and Stochastic Processes with Applications - Oliver Knill
Contents
Preface 3
1 Introduction 7
1.1 What is probability theory? . . . . . . . . . . . . . . . . . . 7
1.2 Some paradoxes in probability theory . . . . . . . . . . . . 14
1.3 Some applications of probability theory . . . . . . . . . . . 18
2 Limit theorems 25
2.1 Probability spaces, random variables, independence . . . . . 25
2.2 Kolmogorov’s 0 − 1 law, Borel-Cantelli lemma . . . . . . . . 38
2.3 Integration, Expectation, Variance . . . . . . . . . . . . . . 43
2.4 Results from real analysis . . . . . . . . . . . . . . . . . . . 46
2.5 Some inequalities . . . . . . . . . . . . . . . . . . . . . . . . 48
2.6 The weak law of large numbers . . . . . . . . . . . . . . . . 55
2.7 The probability distribution function . . . . . . . . . . . . . 61
2.8 Convergence of random variables . . . . . . . . . . . . . . . 63
2.9 The strong law of large numbers . . . . . . . . . . . . . . . 68
2.10 The Birkhoff ergodic theorem . . . . . . . . . . . . . . . . . 72
2.11 More convergence results . . . . . . . . . . . . . . . . . . . . 77
2.12 Classes of random variables . . . . . . . . . . . . . . . . . . 83
2.13 Weak convergence . . . . . . . . . . . . . . . . . . . . . . . 95
2.14 The central limit theorem . . . . . . . . . . . . . . . . . . . 97
2.15 Entropy of distributions . . . . . . . . . . . . . . . . . . . . 103
2.16 Markov operators . . . . . . . . . . . . . . . . . . . . . . . . 113
2.17 Characteristic functions . . . . . . . . . . . . . . . . . . . . 116
2.18 The law of the iterated logarithm . . . . . . . . . . . . . . . 123
3 Discrete Stochastic Processes 129
3.1 Conditional Expectation . . . . . . . . . . . . . . . . . . . . 129
3.2 Martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.3 Doob’s convergence theorem . . . . . . . . . . . . . . . . . . 149
3.4 L´evy’s upward and downward theorems . . . . . . . . . . . 157
3.5 Doob’s decomposition of a stochastic process . . . . . . . . 159
3.6 Doob’s submartingale inequality . . . . . . . . . . . . . . . 163
3.7 Doob’s Lp inequality . . . . . . . . . . . . . . . . . . . . . . 166
3.8 Random walks . . . . . . . . . . . . . . . . . . . . . . . . . 169
1
2 Contents
3.9 The arc-sin law for the 1D random walk . . . . . . . . . . . 174
3.10 The random walk on the free group . . . . . . . . . . . . . . 178
3.11 The free Laplacian on a discrete group . . . . . . . . . . . . 182
3.12 A discrete Feynman-Kac formula . . . . . . . . . . . . . . . 186
3.13 Discrete Dirichlet problem . . . . . . . . . . . . . . . . . . . 188
3.14 Markov processes . . . . . . . . . . . . . . . . . . . . . . . . 193
4 Continuous Stochastic Processes 197
4.1 Brownian motion . . . . . . . . . . . . . . . . . . . . . . . . 197
4.2 Some properties of Brownian motion . . . . . . . . . . . . . 204
4.3 The Wiener measure . . . . . . . . . . . . . . . . . . . . . . 211
4.4 L´evy’s modulus of continuity . . . . . . . . . . . . . . . . . 213
4.5 Stopping times . . . . . . . . . . . . . . . . . . . . . . . . . 215
4.6 Continuous time martingales . . . . . . . . . . . . . . . . . 221
4.7 Doob inequalities . . . . . . . . . . . . . . . . . . . . . . . . 223
4.8 Khintchine’s law of the iterated logarithm . . . . . . . . . . 225
4.9 The theorem of Dynkin-Hunt . . . . . . . . . . . . . . . . . 228
4.10 Self-intersection of Brownian motion . . . . . . . . . . . . . 229
4.11 Recurrence of Brownian motion . . . . . . . . . . . . . . . . 234
4.12 Feynman-Kac formula . . . . . . . . . . . . . . . . . . . . . 236
4.13 The quantum mechanical oscillator . . . . . . . . . . . . . . 241
4.14 Feynman-Kac for the oscillator . . . . . . . . . . . . . . . . 244
4.15 Neighborhood of Brownian motion . . . . . . . . . . . . . . 247
4.16 The Ito integral for Brownian motion . . . . . . . . . . . . . 251
4.17 Processes of bounded quadratic variation . . . . . . . . . . 261
4.18 The Ito integral for martingales . . . . . . . . . . . . . . . . 266
4.19 Stochastic differential equations . . . . . . . . . . . . . . . . 270
5 Selected Topics 281
5.1 Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
5.2 Random Jacobi matrices . . . . . . . . . . . . . . . . . . . . 292
5.3 Estimation theory . . . . . . . . . . . . . . . . . . . . . . . 298
5.4 Vlasov dynamics . . . . . . . . . . . . . . . . . . . . . . . . 304
5.5 Multidimensional distributions . . . . . . . . . . . . . . . . 312
5.6 Poisson processes . . . . . . . . . . . . . . . . . . . . . . . . 317
5.7 Random maps . . . . . . . . . . . . . . . . . . . . . . . . . . 322
5.8 Circular random variables . . . . . . . . . . . . . . . . . . . 325
5.9 Lattice points near Brownian paths . . . . . . . . . . . . . . 333
5.10 Arithmetic random variables . . . . . . . . . . . . . . . . . 339
5.11 Symmetric Diophantine Equations . . . . . . . . . . . . . . 349
5.12 Continuity of random variables . . . . . . . . . . . . . . . . 355
Preface
These notes grew from an introduction to probability theory taught during
the first and second term of 1994 at Caltech. There was a mixed audience of
undergraduates and graduate students in the first half of the course which
covered Chapters 2 and 3, and mostly graduate students in the second part
which covered Chapter 4 and two sections of Chapter 5.
Having been online for many years on my personal web sites, the text got
reviewed, corrected and indexed in the summer of 2006. It obtained some
enhancements which benefited from some other teaching notes and research,
I wrote while teaching probability theory at the University of Arizona in
Tucson or when incorporating probability in calculus courses at Caltech
and Harvard University.
Most of Chapter 2 is standard material and subject of virtually any course
on probability theory. Also Chapters 3 and 4 is well covered by the literature
but not in this combination.
The last chapter “selected topics” got considerably extended in the summer
of 2006.While in the original course, only localization and percolation problems
were included, I added other topics like estimation theory, Vlasov dynamics,
multi-dimensional moment problems, random maps, circle-valued
random variables, the geometry of numbers, Diophantine equations and
harmonic analysis. Some of this material is related to research I got interested
in over time.
While the text assumes no prerequisites in probability, a basic exposure to
calculus and linear algebra is necessary. Some real analysis as well as some
background in topology and functional analysis can be helpful.
I would like to get feedback from readers. I plan to keep this text alive and
update it in the future. You can email this to knill@math.harvard.edu and
also indicate on the email if you don’t want your feedback to be acknowledged
in an eventual future edition of these notes.
3
4 Contents
To get a more detailed and analytic exposure to probability, the students
of the original course have consulted the book [108] which contains much
more material than covered in class. Since my course had been taught,
many other books have appeared. Examples are [21, 34].
For a less analytic approach, see [40, 94, 100] or the still excellent classic
[26]. For an introduction to martingales, we recommend [112] and [47] from
both of which these notes have benefited a lot and to which the students
of the original course had access too.
For Brownian motion, we refer to [74, 67], for stochastic processes to [17],
for stochastic differential equation to [2, 55, 77, 67, 46], for random walks
to [103], for Markov chains to [27, 90], for entropy and Markov operators
[62]. For applications in physics and chemistry, see [110].
For the selected topics, we followed [32] in the percolation section. The
books [104, 30] contain introductions to Vlasov dynamics. The book of [1]
gives an introduction for the moment problem, [76, 65] for circle-valued
random variables, for Poisson processes, see [49, 9]. For the geometry of
numbers for Fourier series on fractals [45].
The book [113] contains examples which challenge the theory with counter
examples. [33, 95, 71] are sources for problems with solutions.
Probability theory can be developed using nonstandard analysis on finite
probability spaces [75]. The book [42] breaks some of the material of the
first chapter into attractive stories. Also texts like [92, 79] are not only for
mathematical tourists.
We live in a time, in which more and more content is available online.
Knowledge diffuses from papers and books to online websites and databases
which also ease the digging for knowledge in the fascinating field of probability
theory.
Oliver Knill, March 20, 2008
Acknowledgements and thanks:
• Csaba Szepesvari contributed a clarification in Theorem 2.16.1.
• Victor Moll mentioned a connection of the graph on page 337 with a
paper in Journal of Number Theory 128 (2008) 1807-1846.
• March and April, 2011: numerous valuable corrections and suggestions
to the first and second chapter were submitted by Shiqing Yao.
More corrections about the third chapter were contributed in May,
2011. Some of them are hard to spot proof clarifications are implemented
in the current document. Thanks!
Contents 5
Updates:
• June 2, 2011: Foshee’s variant of Martin Gardner’s boy-girl problem.
• June 2, 2011: page rank in the section on Markov processes.