Probabilityand RandomProcesses - Princeton University

1 Ramon van HandelProbability andRandom ProcessesORF 309/MAT 380 Lecture NotesPrinceton UniversityThis version: February 22, 2016 PrefaceThese lecture notes are intended for a one-semester undergraduate course inapplied probability. Such a course has been taught at Princeton for many yearsby Erhan inlar. The choice of material in these notes was greatly inspired by inlar s course, though my own biases regarding the material and presentationare inevitably reflected in the present always, some choices had to be made regarding what to present: It should be emphasized that this course isnotintended for a pure math-ematics audience, for whom an entirely different approach would be in-dicated. The course is taken by a diverse range of undergraduates in thesciences, engineering, and applied mathematics. For this reason, the focusis on probabilistic intuition rather than rigorous proofs, and the choice ofmaterial emphasizes exact computations rather than inequalities or asymp-totics.

2 The main aim is to introduce an applied audience to a range of basicprobabilistic notions and to quantitative probabilistic reasoning. A principle I have tried to follow as much as possible is not to introduceany concept out of the blue, but rather to have a natural progression oftopics. For example, every new distribution that is encountered is derivednaturally from a probabilistic model, rather than being defined hope is that this helps students develop a feeling for the big pictureand for the connections between the different topics. The range of topics is quite large for a first course on probability, and thepace is rapid. The main missing topic is an introduction to martingales; Ihope to add a chapter on this at the end at some point in the is a fact of life that lecture notes are a perpetual construction zone.

3 Surelyerrors remain to be fixed and presentation remains to be improved. Manythanks are due to all students who provided me with corrections in the past,and I will be grateful to continue to receive such feedback in the ,January 2016 Contents0 Introduction.. What is probability? .. Why do we need a mathematical theory? .. This course .. 41 Basic Principles of Probability.. Sample space .. Events .. Probability measure .. Probabilistic modelling .. Conditional probability.. Independent events .. Random variables .. Expectation and distributions .. Independence and conditioning .. 312 Bernoulli Processes.. Counting successes and binomial distribution .. Arrival times and geometric distribution .. The law of large numbers .. From discrete to continuous arrivals.

4 563 Continuous Random Variables.. Expectation and integrals .. Joint and conditional densities .. Independence .. 744 Lifetimes and Reliability.. Lifetimes .. Minima and maxima .. * Reliability .. * A random process perspective .. 895 Poisson Processes.. Counting processes and Poisson processes.. Superposition and thinning .. Nonhomogeneous Poisson processes .. 1106 Random Walks.. What is a random walk? .. Hitting times .. Gambler s ruin .. Biased random walks .. 1277 Brownian Motion.. The continuous time limit of a random walk .. Brownian motion and Gaussian distribution .. The central limit theorem .. Jointly Gaussian variables .. Sample paths of Brownian motion .. 1558 Branching Processes.. The Galton-Watson process .. Extinction probability.

5 1639 Markov Chains.. Markov chains and transition probabilities .. Classification of states .. First step analysis .. Steady-state behavior .. The law of large numbers revisited .. What is probability?Most simply stated, probability is the study of randomness. Randomness isof course everywhere around us this statement surely needs no justification!One of the remarkable aspects of this subject is that it touches almost ev-ery area of the natural sciences, engineering, social sciences, and even puremathematics. The following random examples are only a drop in the bucket. Physics: quantities such as temperature and pressure arise as a direct con-sequence of the random motion of atoms and molecules. Quantum me-chanics tells us that the world is random at an even more basic level. Biology and medicine: random mutations are the key driving force behindevolution, which has led to the amazing diversity of life that we see models are essential in understanding the spread of disease, bothin a population (epidemics) or in the human body (cancer).

6 Chemistry: chemical reactions happen when molecules randomly models of chemical kinetics are particularly important in systemswith very low concentrations, such as biochemical reactions in a single cell. Electrical engineering: noise is the universal bane of accurate transmissionof information. The effect of random noise must be well understood inorder to design reliable communication protocols that you use on a dailybasis in your cell phones. The modelling of data, such as English text, usingrandom models is a key ingredient in many data compression schemes. Computer science: randomness is an important resource in the design ofalgorithms. In many situations, randomized algorithms provide the bestknown methods to solve hard problems. Civil engineering: the design of buildings and structures that can reliablywithstand unpredictable effects, such as vibrations, variable rainfall andwind, etc.

7 , requires one to take randomness into Introduction Finance and economics: stock and bond prices are inherently unpre-dictable; as such, random models form the basis for almost all work in thefinancial industry. The modelling of randomly occurring rare events formsthe basis for all insurance policies, and for risk management in banks. Sociology: random models provide basic understanding of the formationof social networks and of the nature of voting schemes, and form the basisfor principled methodology for surveys and other data collection methods. Statistics and machine learning: random models form the foundation foralmost all of data science. The random nature of data must be well under-stood in order to draw reliable conclusions from large data sets. Pure mathematics: probability theory is a mathematical field in its ownright, but is also widely used in many problems throughout pure mathe-matics in areas such as combinatorics, analysis, and number theory.

8 (insert your favorite subject here)As a probabilist1, I find it fascinating that the same basic principles lie atthe heart of such a diverse list of interesting phenomena: probability theory isthe foundation that ties all these and innumerable other areas together. Thisshould already be enough motivation in its own right to convince you (in caseyou were not already convinced) that we are on to an exciting we can have a meaningful discussion, we should at least have a basicidea of what randomness means. Let us first consider the opposite I throw a ball many times at exactly the same angle and speed andunder exactly the same conditions. Every time we run this experiment , theball will land in exactly the same place: we can predict exactly what is goingto happen. This is an example of theopposite of determinism: a random phenomenon is one that can yield differentoutcomes in repeated experiments, even if we use exactly the same conditionsin each experiment .

9 For example, if we flip a coin, we know in advance thatit will either come up heads or tails, but we cannot predict before any givenexperiment which of these outcomes will occur. Our challenge is to develop aframework to reason precisely about random Why do we need a mathematical theory?It is not at all obvious at first sight that it is possible to develop a rigorous the-ory of probability: how can one make precise predictions about a phenomenonwhose behavior is inherently unpredictable? This philosophical hurdle ham-pered the development of probability theory for many definition from the Oxford English Dictionary: probabilist, expertor specialist in the mathematical theory of probability. Why do we need a mathematical theory?3To illustrate the pitfalls of an intuitive approach to probability, let us con-sider a seemingly plausible definition.

10 You probably think of the probabilitythat an eventEhappens as the fraction of outcomes in whichEoccurs (thisis not entirely unreasonable). We could posit this as a tentative definitionProbability ofE=Number of outcomes whereEoccursNumber of all possible sort of intuitive definition may look at first sight like it matches yourexperience. However, it is totally meaningless: we can easily use it to come toentirely different that we flip two coins. What is the probability thatwe obtain one heads (H) and one tails (T)? Solution 1: The possible outcomes areHH,HT,TH,TT. The outcomeswhere we have one heads and one tails areHT,TH. Hence,Probability of one heads and one tails=24=12. Solution 2: The possible outcomes aretwo heads, one heads and one tails,two tails. Only one of these outcomes has one heads and one tails.