Probability: Theory And Examples Rick Durrett Version 5 .
iProbability: Theory and ExamplesRick DurrettVersion 5 January 11, 2019Copyright 2019, All rights reserved.
ii
PrefaceSome times the lights are shining on me. Other times I canbarely see.Lately it occurs to me what a long strange trip its been.Grateful DeadIn 1989 when the first edition of the book was completed, my sonsDavid and Greg were 3 and 1, and the cover picture showed the DowJones at 2650. The last twenty-nine years have brought many changesbut the song remains the same. “The title of the book indicates that as wedevelop the theory, we will focus our attention on examples. Hoping thatthe book would be a useful reference for people who apply probabilityin their work, we have tried to emphasize the results that are importantfor applications, and illustrated their use with roughly 200 examples.Probability is not a spectator sport, so the book contains almost 450exercises to challenge the reader and to deepen their understanding.”The fifth edition has a number of changes: The exercises have been moved to the end of the section. The Examples, Theorems, and Lemmas are now numbered in one sequenceto make it easier to find things. There is a new chapter on multidimensional Brownian motion andits relationship to PDEs. To make this possible a proof of Itô’sformula has been added to Chapter 7. The lengthy Brownian motion chapter has been split into two, withthe second focusing on Donsker’s theorem, etc. The material onthe central limit theorem for martingales and stationary sequencesdeleted from the fourth edition has been reinstated. The four sections of the random walk chapter have been relocated.Stopping times have been moved to the martingale chapter; recurrence of random walks and the arcsine laws to the Markov chainchapter; renewal theory has been moved to Chapter 2. Some of the exercises that were simply proofs left to the reader, havebeen put into the text as lemmas. There are a few new exercisesiii
ivTypos. The fourth edition contains a list of the people who madecorrections to the first three editions. With apologies to those whosecontributions I lost track of, this time I need to thank: Richard Arratia, Benson Au, Swee Hong Chan, Conrado Costa, Nate Eldredge, SteveEvans, Jason Farnon, Christina Goldschmidt, Eduardo Horta, MartinHildebrand, Shlomo Leventhal, Jan Lieke, Kyle MacDonald, Ron Peled,Jonathan Peterson, Erfan Salavati, Byron Schmuland, Timo Seppalainen,Antonio Carlos de Azevedo Sodre, Shouda Wang, and Ruth Williams. Imust confess that Christophe Leuridan pointed one out that I have notcorrected. Lemma 3.4.19 incorrectly asserts that the distributions in itsstatement have mean 0, but their means do not exist. The conclusionremains valid since they are differentiable at 0. A sixth edition is extremely unlikely, but you can email me about typos and I will post themon my web page.Family update. As the fourth edition was being completed, Davidhad recently graduated from Ithaca College and Greg was in his lastsemester at MIT applying to graduate school in computer science. Now,eight years later, Greg has graduated from Berkeley, and is an AssistantProfessor in the Computer Science department at U of Texas in Austin.Greg works in the field of machine learning, specifically natural languageprocessing. No, I don’t know what that means but it seems to pay well.David got his degree in journalism. After an extensive job search processand some free lance work, David has settled into a steady job working fora company that produces newsletters for athletic directors and trainers.In the summer of 2010, Susan and I moved to Durham. Since manypeople think that the move was about the weather, I will mention thatduring our first summer it was 104 degrees (and humid!) three days in arow. Yes, it almost never snows here, but when it does, three inches ofsnow (typically mixed with ice) will shut down the whole town for fourdays. It took some time for us to adjust to the Durham/Chapel area,which has about 10 times as many people as Ithaca and is criss-crossedby freeways, but we live in a nice quiet neighborhood near the campus.Susan enjoys volunteering at the Sarah P. Duke gardens and listening totheir talks about the plants of North Carolina and future plans for thegardens.I doubt there will be a sixth edition, but it is inevitable there will betypos. Email me at rtd@math.duke.edu and I will put a list on the webpage.Rick Durrett, January 2019
Contents1 Measure Theory1.1 Probability Spaces . . . . . . . . . .1.2 Distributions . . . . . . . . . . . . .1.3 Random Variables . . . . . . . . . . .1.4 Integration . . . . . . . . . . . . . . .1.5 Properties of the Integral . . . . . . .1.6 Expected Value . . . . . . . . . . . .1.6.1 Inequalities . . . . . . . . . .1.6.2 Integration to the Limit . . .1.6.3 Computing Expected Values .1.7 Product Measures, Fubini’s Theorem.111015182428293032372 Laws of Large Numbers2.1 Independence . . . . . . . . . . . . . . . . . . . . . .2.1.1 Sufficient Conditions for Independence . . . .2.1.2 Independence, Distribution, and Expectation .2.1.3 Sums of Independent Random Variables . . .2.1.4 Constructing Independent Random Variables .2.2 Weak Laws of Large Numbers . . . . . . . . . . . . .2.2.1 L2 Weak Laws . . . . . . . . . . . . . . . . . .2.2.2 Triangular Arrays . . . . . . . . . . . . . . . .2.2.3 Truncation . . . . . . . . . . . . . . . . . . . .2.3 Borel-Cantelli Lemmas . . . . . . . . . . . . . . . . .2.4 Strong Law of Large Numbers . . . . . . . . . . . . .2.5 Convergence of Random Series* . . . . . . . . . . . .2.5.1 Rates of Convergence . . . . . . . . . . . . . .2.5.2 Infinite Mean . . . . . . . . . . . . . . . . . .2.6 Renewal Theory* . . . . . . . . . . . . . . . . . . . .2.7 Large Deviations* . . . . . . . . . . . . . . . . . . . .43434548495256565962677681878891105.3 Central Limit Theorems3.1 The De Moivre-Laplace Theorem . . . . . . . . . . . . .3.2 Weak Convergence . . . . . . . . . . . . . . . . . . . . .3.2.1 Examples . . . . . . . . . . . . . . . . . . . . . .v113. 113. 116. 116
viCONTENTS3.2.2 Theory . . . . . . . . . . . . . . . . . .3.3 Characteristic Functions . . . . . . . . . . . .3.3.1 Definition, Inversion Formula . . . . .3.3.2 Weak Convergence . . . . . . . . . . .3.3.3 Moments and Derivatives . . . . . . .3.3.4 Polya’s Criterion* . . . . . . . . . . . .3.3.5 The Moment Problem* . . . . . . . . .3.4 Central Limit Theorems . . . . . . . . . . . .3.4.1 i.i.d. Sequences . . . . . . . . . . . . .3.4.2 Triangular Arrays . . . . . . . . . . . .3.4.3 Prime Divisors (Erdös-Kac)* . . . . . .3.4.4 Rates of Convergence (Berry-Esseen)*3.5 Local Limit Theorems* . . . . . . . . . . . . .3.6 Poisson Convergence . . . . . . . . . . . . . .3.6.1 The Basic Limit Theorem . . . . . . .3.6.2 Two Examples with Dependence . . .3.7 Poisson Processes . . . . . . . . . . . . . . . .3.7.1 Compound Poisson Processes . . . . .3.7.2 Thinning . . . . . . . . . . . . . . . . .3.7.3 Conditioning . . . . . . . . . . . . . .3.8 Stable Laws* . . . . . . . . . . . . . . . . . .3.9 Infinitely Divisible Distributions* . . . . . . .3.10 Limit Theorems in Rd . . . . . . . . . . . . .4 Martingales4.1 Conditional Expectation . . . . . . . . . . .4.1.1 Examples . . . . . . . . . . . . . . .4.1.2 Properties . . . . . . . . . . . . . . .4.1.3 Regular Conditional Probabilities* .4.2 Martingales, Almost Sure Convergence . . .4.3 Examples . . . . . . . . . . . . . . . . . . .4.3.1 Bounded Increments . . . . . . . . .4.3.2 Polya’s Urn Scheme . . . . . . . . . .4.3.3 Radon-Nikodym Derivatives . . . . .4.3.4 Branching Processes . . . . . . . . .4.4 Doob’s Inequality, Convergence in Lp , p 14.5 Square Integrable Martingales* . . . . . . .4.6 Uniform Integrability, Convergence in L1 . .4.7 Backwards Martingales . . . . . . . . . . . .4.8 Optional Stopping Theorems . . . . . . . . .4.8.1 Applications to random walks . . . .4.9 Combinatorics of simple random walk* . . 74177178181182193196.205. 205. 207. 210. 214. 217. 224. 224. 226. 227. 230. 235. 240. 244. 249. 255. 257. 262
CONTENTSvii5 Markov Chains5.1 Examples . . . . . . . . . . . . .5.2 Construction, Markov Properties5.3 Recurrence and Transience . . . .5.4 Recurrence of Random Walks* . .5.5 Stationary Measures . . . . . . .5.6 Asymptotic Behavior . . . . . . .5.7 Periodicity, Tail σ-field* . . . . .5.8 General State Space* . . . . . . .5.8.1 Recurrence and Transience5.8.2 Stationary Measures . . .5.8.3 Convergence Theorem . .5.8.4 GI/G/1 queue . . . . . . .6 Ergodic Theorems6.1 Definitions and Examples . . .6.2 Birkhoff’s Ergodic Theorem . .6.3 Recurrence . . . . . . . . . . . .6.4 A Subadditive Ergodic Theorem6.5 Applications . . . . . . . . . . .7 Brownian Motion7.1 Definition and Construction . . . . . . . .7.2 Markov Property, Blumenthal’s 0-1 Law .7.3 Stopping Times, Strong Markov Property .7.4 Path Properties . . . . . . . . . . . . . . .7.4.1 Zeros of Brownian Motion . . . . .7.4.2 Hitting times . . . . . . . . . . . .7.5 Martingales . . . . . . . . . . . . . . . . .7.6 Itô’s formula* . . . . . . . . . . . . . . . .8 Applications to Random Walk8.1 Donsker’s Theorem . . . . . . . . . . . . .8.2 CLT’s for Martingales . . . . . . . . . . .8.3 CLTs for Stationary Sequences . . . . . . .8.3.1 Mixing Properties . . . . . . . . . .8.4 Empirical Distributions, Brownian Bridge8.5 Laws of the Iterated Logarithm . . . . . .9 Multidimensional Brownian Motion9.1 Martingales . . . . . . . . . . . . .9.2 Heat Equation . . . . . . . . . . . .9.3 Inhomogeneous Heat Equation . . .9.4 Feynman-Kac Formula . . . . . . .269. 269. 273. 281. 287. 299. 310. 317. 322. 325. 326. 327. 327.331. 331. 335. 339. 343. 347.353. 353. 360. 366. 370. 370. 371. 375. 379.389. 389. 396. 402. 406. 410. 416.421. 421. 424. 426. 428
viiiCONTENTS9.59.69.79.8Dirichlet problem . . . . . . . .9.5.1 Exit distributions . . . .Green’s Functions and PotentialPoisson’s Equation . . . . . . .9.7.1 Occupation times . . . .Schrödinger Equation . . . . . . . . . . . . . .Kernels. . . . . . . . . . . . .A Measure Theory DetailsA.1 Caratheéodory’s Extension TheoremA.2 Which Sets Are Measurable? . . . . .A.3 Kolmogorov’s Extension Theorem . .A.4 Radon-Nikodym Theorem . . . . . .A.5 Differentiating under the Integral . .432436438441444447.455455461464466470
Chapter 1Measure TheoryIn this chapter, we will recall some definitions and results from measuretheory. Our purpose here is to provide an introduction for readers whohave not seen these concepts before and to review that material for thosewho have. Harder proofs, especially those that do not contribute muchto one’s intuition, are hidden away in the appendix. Readers with a solidbackground in measure theory can skip Sections 1.4, 1.5, and 1.7, whichwere previously part of the appendix.1.1Probability SpacesHere and throughout the book, terms being defined are set in boldface.We begin with the most basic quantity. A probability space is a triple(Ω, F, P ) where Ω is a set of “outcomes,” F is a set of “events,” andP : F [0, 1] is a function that assigns probabilities to events. Weassume that F is a σ-field (or σ-algebra), i.e., a (nonempty) collectionof subsets of Ω that satisfy(i) if A F then Ac F, and(ii) if Ai F is a countable sequence of sets then i Ai F.Here and in what follows, countable means finite or countably infinite.Since i Ai ( i Aci )c , it follows that a σ-field is closed under countableintersections. We omit the last property from the definition to make iteasier to check.Without P , (Ω, F) is called a measurable space, i.e., it is a spaceon which we can put a measure. A measure is a nonnegative countablyadditive set function; that is, a function µ : F R with(i) µ(A) µ( ) 0 for all A F, and(ii) if Ai F is a countable sequence of disjoint sets, thenXµ( i Ai ) µ(Ai )i1
2CHAPTER 1. MEASURE THEORYIf µ(Ω) 1, we call µ a probability measure. In this book, probabilitymeasures are usually denoted by P .The next result gives some consequences of the definition of a measurethat we will need later. In all cases, we assume that the sets we mentionare in F.Theorem 1.1.1. Let µ be a measure on (Ω, F)(i) monotonicity. If A B then µ(A) µ(B).(ii) subadditivity. If A m 1 Am then µ(A) P m 1µ(Am ).(iii) continuity from below. If Ai A (i.e., A1 A2 . . . and i Ai A) then µ(Ai ) µ(A).(iv) continuity from above. If Ai A (i.e., A1 A2 . . . and i Ai A), with µ(A1 ) then µ(Ai ) µ(A).Proof. (i) Let B A B Ac be the difference of the two sets. Using to denote disjoint union, B A (B A) soµ(B) µ(A) µ(B A) µ(A).0(ii) Let A0n An A, B1 A01 and for n 1, Bn A0n n 1m 1 Am . Sincethe Bn are disjoint and have union A we have using (ii) of the definitionof measure, Bm Am , and (i) of this theoremµ(A) Xµ(Bm ) m 1 Xµ(Am )m 1(iii) Let Bn An An 1 . Then the Bn are disjoint and have m 1 Bm nA, m 1 Bm An soµ(A) Xm 1µ(Bm ) limn nXm 1µ(Bm ) lim µ(An )n (iv) A1 An A1 A so (iii) implies µ(A1 An ) µ(A1 A). Since A1 Awe have µ(A1 A) µ(A1 ) µ(A) and it follows that µ(An ) µ(A).The simplest setting, which should be familiar from undergraduateprobability, is:Example 1.1.2. Discrete probability spaces. Let Ω a countableset, i.e., finite or countably infinite. Let F the set of all subsets of Ω.LetXXP (A) p(ω) where p(ω) 0 andp(ω) 1ω Aω ΩA little thought reveals that this is the most general probability measureon this space. In many cases when Ω is a finite set, we have p(ω) 1/ Ω where Ω the number of points in Ω.
1.1. PROBABILITY SPACES3For a simple concrete example that requires this level of generalityconsider the astragali, dice used in ancient Egypt made from the anklebones of sheep. This die could come to rest on the top side of the bonefor four points or on the bottom for three points. The side of the bonewas slightly rounded. The die could come to rest on a flat and narrowpiece for six points or somewhere on the rest of the side for one point.There is no reason to think that all four outcomes are equally likely sowe need probabilities p1 , p3 , p4 , and p6 to describe P .To prepare for our next definition, we need note that it follows easilyfrom the definition If Fi , i I are σ-fields then i I Fi is. Here I 6 isan arbitrary index set (i.e., possibly uncountable). From this it followsthat if we are given a set Ω and a collection A of subsets of Ω, thenthere is a smallest σ-field containing A. We will call this the σ-fieldgenerated by A and denote it by σ(A).Let Rd be the set of vectors (x1 , . . . xd ) of real numbers and Rd be theBorel sets, the smallest σ-field containing the open sets. When d 1we drop the superscript.Example 1.1.3. Measures on the real line. Measures on (R, R)are defined by giving a Stieltjes measure function with the followingproperties:(i) F is nondecreasing.(ii) F is right continuous, i.e. limy x F (y) F (x).Theorem 1.1.4. Associated with each Stieltjes measure function F thereis a unique measure µ on (R, R) with µ((a, b]) F (b) F (a)µ((a, b]) F (b) F (a)(1.1.1)When F (x) x the resulting measure is called Lebesgue measure.The proof of Theorem 1.1.4 is a long and winding road, so we willcontent ourselves to describe the main ideas involved in this section andto hide the remaining details in the appendix in Section A.1. The choiceof “closed on the right” in (a, b] is dictated by the fact that if bn b thenwe have n (a, bn ] (a, b]The next definition will explain the choice of “open on the left.”A collection S of sets is said to be a semialgebra if (i) it is closedunder intersection, i.e., S, T S implies S T S, and (ii) if S Sthen S c is a finite disjoint union of sets in S. An important example ofa semialgebra isExample 1.1.5. Sd the empty set plus all sets of the form(a1 , b1 ] · · · (ad , bd ] Rdwhere ai bi
4CHAPTER 1. MEASURE THEORYThe definition in (1.1.1) gives the values of µ on the semialgebra S1 .To go from semialgebra to σ-algebra we use an intermediate step. Acollection A of subsets of Ω is called an algebra (or field) if A, B Aimplies Ac and A B are in A. Since A B (Ac B c )c , it follows thatA B A. Obviously a σ-algebra is an algebra. An example in whichthe converse is false is:Example 1.1.6. Let Ω Z the integers. A the collection of A Zso that A or Ac is finite is an algebra.Lemma 1.1.7. If S is a semialgebra then S̄ {finite disjoint unions ofsets in S} is an algebra, called the algebra generated by S.Proof. Suppose A i Si and B j Tj , where denotes disjoint unionand we assume the index sets are finite. Then A B i,j Si Tj S̄.As for complements, if A i Si then Ac i Sic . The definition of Simplies Sic S̄. We have shown that S̄ is closed under intersection, so itfollows by induction that Ac S̄.Example 1.1.8. Let Ω R and S S1 then S̄1 the empty set plusall sets of the form ki 1 (ai , bi ] where ai bi Given a set function µ on S we can extend it to S̄ byµ ( ni 1 Ai ) nXµ(Ai )i 1By a measure on an algebra A, we mean a set function µ with(i) µ(A) µ( ) 0 for all A A, and(ii) if Ai A are disjoint and their union is in A, thenµ ( i 1 Ai ) Xµ(Ai )i 1µ is said to be σ-finite if there is a sequence of sets An A so thatµ(An ) and n An Ω. Letting A01 A1 and for n 2, cA0n nm 1 Am or A0n An n 1m 1 Am Awe can without loss of generality assume that An Ω or the An aredisjoint.The next result helps us to extend a measure defined on a semi-algebraS to the σ-algebra it generates, σ(S)
1.1. PROBABILITY SPACES5Theorem 1.1.9. Let S be a semialgebra and let µ defined on S haveµ( ) 0. Suppose(i) if S S is a finite disjoint union of sets Si SPthen µ(S) i µ(Si ), and (ii) if Si , S S with S i 1 Si then µ(S) Pi 1 µ(Si ). Then µ has a unique extension µ̄ that is a measure on S̄the algebra generated by S. If µ̄ is sigma-finite then there is a uniqueextension ν that is a measure on σ(S)In (ii) above, and in what follows, i 1 indicates a countable union, whilea plain subscript i or j indicates a finite union. The proof of Theorems1.1.9 is rather involved so it is given in Section A.1. To check condition(ii) in the theorem the following is useful.Lemma 1.1.10. Suppose only that (i) holds. P(a) If A, Bi S̄ with A ni 1 Bi then µ̄(A) P i µ̄(Bi ).(b) If A, Bi S̄ with A ni 1 Bi then µ̄(A) i µ̄(Bi ).Proof. Observe that it follows from the definition that if A i Bi is afinite disjoint union of sets in S̄ and Bi j Si,j , thenXXµ(Si,j ) µ̄(Bi )µ̄(A) i,jiTo prove (b), we begin with the case n 1, B1 B. B A (B Ac )and B Ac S̄, soµ̄(A) µ̄(A) µ̄(B Ac ) µ̄(B)cTo handle n 1 now, let Fk B1c . . . Bk 1 Bk and note i Bi F1 · · · FnA A ( i Bi ) (A F1 ) · · · (A Fn )so using (a), (b) with n 1, and (a) againµ̄(A) nXk 1µ̄(A Fk ) nXµ̄(Fk ) µ̄ ( i Bi )k 1Proof of Theorem 1.1.4. Let
deleted from the fourth edition has been reinstated. The four sections of the random walk chapter have been relocated. Stopping times have been moved to the martingale chapter; recur-rence of random walks and the arcsine laws to the Markov chain chapter; renewal theory has been moved to Chapter 2.
Joint Probability P(A\B) or P(A;B) { Probability of Aand B. Marginal (Unconditional) Probability P( A) { Probability of . Conditional Probability P (Aj B) A;B) P ) { Probability of A, given that Boccurred. Conditional Probability is Probability P(AjB) is a probability function for any xed B. Any
Pros and cons Option A: - 80% probability of cure - 2% probability of serious adverse event . Option B: - 90% probability of cure - 5% probability of serious adverse event . Option C: - 98% probability of cure - 1% probability of treatment-related death - 1% probability of minor adverse event . 5
Review of Probability Theory Arian Maleki and Tom Do Stanford University Probability theory is the study of uncertainty. Through this class, we will be relying on concepts from probability theory for deriving mach
Dr Jonathan Jordan MAS113 Introduction to Probability and Statistics. Introduction Set theory and probability Measure Motivation - the need for set theory and measures If you have studied probability at GCSE or A-level, you may have seen a de nition of probability like this:
Chapter 4: Probability and Counting Rules 4.1 – Sample Spaces and Probability Classical Probability Complementary events Empirical probability Law of large numbers Subjective probability 4.2 – The Addition Rules of Probability 4.3 – The Multiplication Rules and Conditional P
Probability measures how likely something is to happen. An event that is certain to happen has a probability of 1. An event that is impossible has a probability of 0. An event that has an even or equal chance of occurring has a probability of 1 2 or 50%. Chance and probability – ordering events impossible unlikely
Engineering Formula Sheet Probability Conditional Probability Binomial Probability (order doesn’t matter) P k ( binomial probability of k successes in n trials p probability of a success –p probability of failure k number of successes n number of trials Independent Events P (A and B and C) P A P B P C
Target 4: Calculate the probability of overlapping and disjoint events (mutually exclusive events Subtraction Rule The probability of an event not occurring is 1 minus the probability that it does occur P(not A) 1 – P(A) Example 1: Find the probability of an event not occurring The pr
