ProbabilityTheory - Harvard Mathematics Department

1 probability TheoryCourse Notes Harvard University 2011C. McMullenSeptember 28, 2017 ContentsI The Sample Space .. 2II Elements of Combinatorial Analysis .. 5 III Random Walks .. 15IV Combinations of Events .. 24V Conditional probability .. 29VI The Binomial and Poisson Distributions .. 37 VII Normal Approximation .. 44 VIII Unlimited Sequences of Bernoulli Trials ..55IX Random Variables and Expectation .. 60X Law of Large Numbers .. 68XI Integral Valued Variables. Generating Functions .. 70 XIV Random Walk and Ruin Problems .. 70I The Exponential and the Uniform Density.

2 75II Special Densities. Randomization .. 94 These course notes accompany Feller,An Introduction to ProbabilityTheory and Its Applications, Wiley, The Sample SpaceSome sources and uses of randomness, and philosophical Flipped The interrupted game of chance (Fermat).3. The last roll of the game in backgammon (splitting the stakes at MonteCarlo).4. Large numbers: elections, gases, True randomness? Quantum Randomness as a model (in reality only one thing happens).Paradox:what if a coin keeps coming up heads?7. Statistics: testing a drug. When is an event good evidencerather thana random artifact?

3 8. Significance: among 1000 coins, if one comes up heads 10 times in arow, is it likely to be a 2-headed coin? Applications to economics,investment and Randomness as a tool: graph theory ; scheduling; begin with some are the chances of 10 heads in a row? The probability is1/1024, less than Implicit assumptions: no biases and are the chance of heads 5 out of ten times? ((105)= 252, so 252/1024= 25%).The birthday are the chances of 2 people in a crowdhaving the same birthday? Implicit assumptions: all 365 days are equallylikely; no leap days; different birthdays are that no 2 people among 30 have the same birthday is Back of the envelope calculation gives logP= (1/365)(1 + 2 + + 29) 450/365; and exp( 450/365) = are the Sunday babies?

4 US studies show 16% fewer this make it easier or harder for people to have the same birthday?The Dean says with surprise, I ve only scheduled 20 meetingsout-of-townfor this year, and already I have a conflict. What faculty is hefrom?Birthdays on Jovian day is hours, and a Jovian yearis earth years. Thus there areN= 10,467 possible birthdays onJupiter. How big does the class need to be to demonstrate the birthdayparadox?It is good to know that log(2) = .. By the back ofthe envelope calculation, we want the number of peoplekin class to satisfy1 + 2 +..+k k2/2 withk2/(2N) , ork 121.

5 (Although since Jupiter s axis is only tilted 3 , seasonal variations aremuch less and the period of one year might have less cultural significance.)The rule of fact that 10 log(2) is about 7 is related to the rule of 7 in banking: to double your money at a (low) annual interest rateof k% takes about 70/kyears (not 100/k).(A third quantity that is useful to know is log 10 .)The mailman mailman deliversnletters at random tonrecipients. The probability that the first letter goes to theright person is1/n, so the probability that it doesn t is 1 1/n. Thus the probability thatno one gets the right letter is (1 1/n)n 1/e= 37%.

6 Now consider the casen= 2. Then he either delivers the letters forAandBin order (A, B) or (B, A). So there is a 50% chance that no one getsthe right letter. But according to our formula, there is onlya 25% chancethat no one gets the right is going on?Outcomes; functions and injective porter s deliveriesare described by the setSof all functionsf:L Bfromnletters tonboxes. The mailman s deliveries are described by the spaceS Sof all1 1 functionsf:L B. We have|S|=nnand|S |=n!; they givedifferent statistics for equal sample collectionSof all possible completely specifiedoutcomes of an experiment or task or process is called thesample For a single toss at a dartboard,Sis the unit For the high temperature today,S= [ 50,200].

7 3. For a toss of a coin,S={H, T}.34. For the roll of a die,S={1,2,3,4,5,6}.5. For the roll of two dice,|S|= Fornrolls of a die,S={(a1, .. , an) : 1 ai 6}; we have|S|= formally,Sis the set of functions on [1,2, .. , n] with values in[1,2, .. ,6].7. For shuffling cards,|S|= 52! = 8 a subset ofS. For example: a bull s eye; a comfortable day;heads; an odd number on the die; dice adding up to 7; never getting a 3 innrolls; the first five cards form a royal combinations of events correspond to the operatorsof set example:A = notA=S A;A B=AandB;A B= now focus attention on adiscrete sample space.

8 Thenaprobability measureis a functionp:S [0,1] such that Sp(s) = , out of ignorance or because of symmetry, we havep(s) = 1/|S|(allsamples have equal likelihood).The probability of aneventis given byP(A) = s Ap(s).If allshave the same probability , thenP(A) =|A|/|S|.Proposition haveP(A ) = 1 P(A).Note that this formula is not based on intuition (although itcoincideswith it), but is derived from the definitions, since we haveP(A) +P(A ) =P(S) = 1. (We will later treat other logical combinations of events).Example: mail pesky porter throws letters into the pi-geonholes of thenstudents;Sis the set of all functionsf:n n.

9 Whilethe mixed-up mailman simple chooses a letter at random for each house;Sis the space of allbijectivefunctionsf:n n. These givedifferent answersfor the probability of a successful delivery. (Exercise: who does a better jobforn= 3? The mailman is more likely than the porter to be a completefailure that is, to make no correct delivery. The probability of failure forthe porter is (2/3)3= 8/27, while for the mailman it is 1/3 = 2/3! = 8 trend continues for alln, although for both the probability of completefailure tends to 1/e.)An infinite sample you flip a fair coin until it comesup heads.

10 ThenS=N { }is the number of flips it takes. We havep(1) = 1/2,p(2) = 1/4, and n=11/2n= 1, sop( ) = of flips it takes isE= 1n/2n= 2. To evaluatethis, we note thatf(x) = 1xn/2n= (x/2)/(1 x/2) satisfiesf (x) = 1nxn 1/2nand henceE=f (1) = 2. This is the method s event that a numberXbegins with a 1 in base 10depends only on log(X) mod 1 [0,1]. It occurs when log(X) [0,log 2] =[0, ..]. In some settings ( populations of cities, values of theDow) this means there is a 30% chance the first digit is one (andonly a 5%chance that the first digit is 9).For example, once the Dow has reached 1,000, it must double invalue tochange the first digit; but when it reaches 9,000, it need onlyincrease about10% to get back to Elements of Combinatorial AnalysisBasic counting To choosekordered items from a setA, with replacement, is thesame as to choose an element ofAk.