ProbabilityandStochasticProcesses withApplications

1 probability and Stochastic Processeswith ApplicationsOliver KnillContentsPreface31 What is probability theory? .. Some paradoxes in probability theory .. Some applications of probability theory .. 182 Limit probability spaces, random variables, independence .. Kolmogorov s 0 1 law, Borel-Cantelli lemma .. Integration, Expectation, Variance .. Results from real analysis .. Some inequalities .. The weak law of large numbers .. The probability distribution function .. Convergence of random variables .. The strong law of large numbers .. The Birkhoff ergodic theorem .. More convergence results .. Classes of random variables .. Weak convergence .. The central limit theorem .. Entropy of distributions.

2 Markov operators .. Characteristic functions .. The law of the iterated logarithm .. 1233 Discrete Stochastic Conditional Expectation .. Martingales .. Doob s convergence theorem .. L evy s upward and downward theorems .. Doob s decomposition of a stochastic process .. Doob s submartingale inequality .. Doob sLpinequality .. random walks .. The arc-sin law for the 1D random walk .. The random walk on the free group .. The free Laplacian on a discrete group .. A discrete Feynman-Kac formula .. Discrete Dirichlet problem .. Markov processes .. 1934 Continuous Stochastic Brownian motion .. Some properties of Brownian motion .. The Wiener measure .. L evy s modulus of continuity .. Stopping times.

3 Continuous time martingales .. Doob inequalities .. Khintchine s law of the iterated logarithm .. The theorem of Dynkin-Hunt .. Self-intersection of Brownian motion .. Recurrence of Brownian motion .. Feynman-Kac formula .. The quantum mechanical oscillator .. Feynman-Kac for the oscillator .. Neighborhood of Brownian motion .. The Ito integral for Brownian motion .. processes of bounded quadratic variation .. The Ito integral for martingales .. Stochastic differential equations .. 2725 Selected Percolation .. random Jacobi matrices .. Estimation theory .. Vlasov dynamics .. Multidimensional distributions .. Poisson processes .. random maps .. Circular random variables .. Lattice points near Brownian paths.

4 Arithmetic random variables .. Symmetric Diophantine Equations .. Continuity of random variables .. 357 PrefaceThese notes grew from an introduction to probability theory taught duringthe first and second term of 1994 at Caltech. There was a mixed audience ofundergraduates and graduate students in the first half of the course whichcovered Chapters 2 and 3, and mostly graduate students in the second partwhich covered Chapter 4 and two sections of Chapter been online for many years on my personal web sites, the text gotreviewed, corrected and indexed in the summer of 2006. It obtained someenhancements which benefited from some other teaching notes and research,I wrote while teaching probability theory at the University of ArizonainTucson or when incorporating probability in calculus courses at Caltechand Harvard of Chapter 2 is standard material and subject of virtually anycourseon probability theory.

5 Also Chapters 3 and 4 is well covered by the litera-ture but not in this last chapter selected topics got considerably extended in the summerof 2006. While in the original course, only localization and percolation prob-lems were included, I added other topics like estimation theory, Vlasov dy-namics, multi-dimensional moment problems, random maps, circle-valuedrandom variables, the geometry of numbers, Diophantine equations andharmonic analysis. Some of this material is related to research I gotinter-ested in over the text assumes no prerequisites in probability , a basic exposure tocalculus and linear algebra is necessary. Some real analysis as well assomebackground in topology and functional analysis can be would like to get feedback from readers. I plan to keep this text alive andupdate it in the future.

6 You can email this to andalso indicate on the email if you don t want your feedback to be acknowl-edged in an eventual future edition of these get a more detailed and analytic exposure to probability , the studentsof the original course have consulted the book [109] which containsmuchmore material than covered in class. Since my course had been taught,many other books have appeared. Examples are [20, 34].For a less analytic approach, see [40, 94, 100] or the still excellent classic[25]. For an introduction to martingales, we recommend [113] and [47]fromboth of which these notes have benefited a lot and to which the studentsof the original course had access Brownian motion, we refer to [74, 67], for stochastic processes to [16],for stochastic differential equation to [2, 55, 77, 67, 46], for random walksto [103], for Markov chains to [26, 90], for entropy and Markov operators[62].

7 For applications in physics and chemistry, see [111].For the selected topics, we followed [32] in the percolation section. Thebooks [104, 30] contain introductions to Vlasov dynamics. The bookof [1]gives an introduction for the moment problem, [76, 65] for circle-valuedrandom variables, for Poisson processes , see [49, 9]. For the geometry ofnumbers for Fourier series on fractals [45].The book [114] contains examples which challenge the theory with counterexamples. [33, 95, 71] are sources for problems with theory can be developed using nonstandard analysis on finiteprobability spaces [75]. The book [42] breaks some of the material ofthefirst chapter into attractive stories. Also texts like [92, 79] are not only formathematical live in a time, in which more and more content is available diffuses from papers and books to online websites and databaseswhich also ease the digging for knowledge in the fascinating field of proba-bility Knill, March 20, 2008 Acknowledgements and thanks: Sep 3, 2007: Thanks to Csaba Szepesvari for pointing out that intheorem , the conditionP1 = 1 was missing.

8 Jun 29, 2011, Thanks to Jim Rulla for pointing out a typo in thepreface. Csaba Szepesvari contributed a clarification in Theorem Victor Moll mentioned a connection of the graph on page 337 with apaper in Journal of Number Theory 128 (2008) 1807-1846. (Septem-ber 2013: thanks also for pointing out some typos).Contents5 March and April, 2011: numerous valuable corrections and sugges-tions to the first and second chapter were submitted by Shiqing corrections about the third chapter were contributed by Shiqingin May, 2011. Some of them were proof clarifications which were hardto spot. They are all implemented in the current document. Thanks! April 2013, thanks to Jun Luo for helping to clarify the proof ofLemma February 2017, thanks to Bernd Eggen for some corrections andad-ditional entries about Section : June 2, 2011: Foshee s variant of Martin Gardner s boy-girl problem.

9 June 2, 2011: page rank in the section on Markov What is probability theory? probability theory is a fundamental pillar of modern mathematics withrelations to other mathematical areas like algebra, topology, analysis, ge-ometry or dynamical systems. As with any fundamental mathematical con-struction, the theory starts by adding more structure to a set . In a similarway as introducing algebraic operations, a topology, or a time evolution ona set, probability theory adds ameasure theoretical structureto whichgeneralizes counting on finite sets: in order to measure theprobabilityof a subsetA , one singles out a class of subsetsA, on which one canhope to do so. This leads to the notion of a -algebraA. It is a set of sub-sets of in which on can perform finitely orcountably manyoperationslike taking unions, complements or intersections.

10 The elements inAarecalledevents. If a point in the laboratory denotes an experiment ,an event A Ais a subset of , for which one can assign a proba-bility P[A] [0,1]. For example, if P[A] = 1/3, the event happens withprobability 1/3. If P[A] = 1, the event takes place almost certainly. Theprobability measureP has to satisfy obvious properties like that theunionA Bof two disjoint eventsA,Bsatisfies P[A B] = P[A] + P[B] or thatthecomplementAcof an eventAhas the probability P[Ac] = 1 P[A].With a probability space ( ,A,P) alone, there is already some interestingmathematics: one has for example thecombinatorial problemto find theprobabilities of events like the event to get a royal flush in is a subset of an Euclidean space like the plane, P[A] =RAf(x,y)dxdyfor a suitable nonnegativefunctionf, we are led tointegration problemsin calculus.