Lecture Notes 1 Basic Probability - Stanford University

1 Lecture Notes 1 Basic Probability Set theory Elements of Probability Conditional Probability Sequential Calculation of Probability Total Probability and Bayes Rule Independence CountingEE 178/278A: Basic ProbabilityPage 1 1 Set theory Basics A set is a collection of objects, which are itselements Ameans that is an element of the setA A set with no elements is called theempty set, denoted by Types of sets: Finite:A={ 1, 2, .. , n} Countably infinite:A={ 1, 2, ..}, , the set of integers Uncountable: A set that takes a continuous set of values, , the[0,1]interval, the real line, etc. A set can be described by all having a certain property, ,A= [0,1]can bewritten asA={ : 0 1} A setB Ameans that every element ofBis an element ofA Auniversal set containsallobjects of particular interest in a particularcontext, , sample space for random experimentEE 178/278A: Basic ProbabilityPage 1 2 Set Operations Assume a universal set Three Basic operations: Complementation: A complement of a setAwith respect to isAc={ : / A}, so c= Intersection:A B={ : Aand B} Union:A B={ : Aor B} Notation: ni=1Ai=A1 A2.

2 An ni=1Ai=A1 A2.. An A collection of setsA1, A2, .. , Anaredisjointormutually exclusiveifAi Aj= for alli6=j, , no two of them have a common element A collection of setsA1, A2, .. , Anpartition if they are disjoint and ni=1Ai= EE 178/278A: Basic ProbabilityPage 1 3 Venn Diagrams(e)A B(f)A B(b)A(d)Bc(a) (c)BEE 178/278A: Basic ProbabilityPage 1 4 Algebra of Sets Basic =S2.(Ac)c= Ac= 4. Commutative law:A B=B A5. Associative law:A (B C) = (A B) C6. Distributive law:A (B C) = (A B) (A C)7. DeMorgan s law:(A B)c=Ac BcDeMorgan s law can be generalized tonevents:( ni=1Ai)c= ni=1 Aci These can all be proven using the definition of set operationsor visualized usingVenn DiagramsEE 178/278A: Basic ProbabilityPage 1 5 Elements of Probability Probability theory provides the mathematical rules for assigning probabilities tooutcomes of random experiments, , coin flips, packet arrivals, noise voltage Basic elements of Probability : Sample space : The set of all possible elementary or finest grain outcomes of the random experiment (also calledsample points) The sample points are alldisjoint The sample points arecollectively exhaustive, , together they make upthe entire sample space Events: Subsets of the sample space Probability law: An assignment of probabilities to events in a mathematicallyconsistent wayEE 178/278A.

3 Basic ProbabilityPage 1 6 Discrete Sample Spaces Sample space is calleddiscreteif it contains a countable number of samplepoints Examples: Flip a coin once: ={H, T} Flip a coin three times: ={HHH, HHT, HT H, ..}={H, T}3 Flip a coinntimes: ={H, T}n(set of sequences of H and T of lengthn) Roll a die once: ={1,2,3,4,5,6} Roll a die twice: ={(1,1),(1,2),(2,1), .. ,(6,6)}={1,2,3,4,5,6}2 Flip a coin until the first heads appears: ={H, T H, T T H, T T T H, ..} Number of packets arriving in time interval(0, T]at a node in acommunication network : ={0,1,2,3, ..}Note that the first five examples havefinite , whereas the last two havecountably infinite . Both types are called discreteEE 178/278A: Basic ProbabilityPage 1 7 Sequential models: For sequential experiments, the samplespace can bedescribed in terms of a tree, where each outcome correspondsto a terminalnode (or aleaf)Example: Three flips of a coin| H| H|@@@@@@T|AAAAAAAAAAAT| H|@@@@@@T| HHHHHHHT HHHHHHHT HHHHHHHT HHHHHHHT|HHH|HHT|HT H|HT T|T HH|T HT|T T H|T T TEE 178/278A: Basic ProbabilityPage 1 8 Example: Roll a fair four-sided die space can be represented by a tree as above, or graphicallyffffffffffffffff2nd roll1st roll12341234EE 178/278A: Basic ProbabilityPage 1 9 Continuous Sample Spaces Acontinuoussample space consists of a continuum of points and thus containsan uncountable number of points Examples: Random number between 0 and 1: = [0,1] Suppose we pick two numbers at random between 0 and 1, then thesamplespace consists of all points in theunit square, , = [0,1] 178/278A.)

4 Basic ProbabilityPage 1 10 Packet arrival time:t (0, ), thus = (0, ) Arrival times fornpackets:ti (0, ), fori= 1,2, .. , n, thus = (0, )n A sample space is said to bemixedif it is neither discrete nor continuous, , = [0,1] {3}EE 178/278A: Basic ProbabilityPage 1 11 Events Events aresubsetsof the sample space . An event occurs if the outcome of theexperiment belongs to the event Examples: Any outcome (sample point) is an event (also called an elementary event), ,{HTH}in three coin flips experiment or{ }in the picking of arandom number between 0 and 1 experiment Flip coin 3 times and get exactly one H. This is a more complicated event,consisting of three sample points{TTH, THT, HTT} Flip coin 3 times and get an odd number of H s. The event is{TTH, THT, HTT, HHH} Pick a random number between 0 and 1 and get a number between The event is[0, ] An event might haveno pointsin it, , be the empty set EE 178/278A: Basic ProbabilityPage 1 12 Axioms of Probability Probability law (measure or function) is an assignment of probabilities to events(subsets of sample space ) such that the following three axioms are (A) 0, for allA(nonnegativity) ( ) = 1(normalization)3.

5 IfAandBare disjoint (A B= ), thenP(A B) = P(A) + P(B)(additivity)More generally,3 . If the sample space has an infinite number of points andA1, A2, ..aredisjoint events, thenP ( i=1Ai) = i=1P(Ai)EE 178/278A: Basic ProbabilityPage 1 13 Mimics relative frequency, , perform the experimentntimes ( , roll a dientimes). If the number of occurances ofAisnA, define the relative frequency ofan eventAasfA=nA/n Probabilities are nonnegative (like relative frequencies) Probability something happens is 1 (again like relative frequencies) Probabilities ofdisjointevents add (again like relative frequencies) Analogy: Except for normalization, Probability is ameasuremuch like mass length area volumeThey all satisfy axioms 1 and 3 This analogy provides some intuition but is not sufficient to fully understandprobability theory other aspects such as conditioning, independence, , areunique to probabilityEE 178/278A: Basic ProbabilityPage 1 14 Probability for Discrete Sample Spaces Recall that sample space is said to bediscreteif it is countable The Probability measurePcan be simply defined by first assigning probabilitiesto outcomes, , elementary events{ }, such that.

6 P({ }) 0,for all ,and P({ }) = 1 The Probability of any other eventA(by the additivity axiom) is simplyP(A) = AP({ })EE 178/278A: Basic ProbabilityPage 1 15 Examples: For the coin flipping experiment, assignP({H}) =pandP({T}) = 1 p,for0 p 1 Note:pis thebiasof the coin, and a coin isfairifp=12 For the die rolling experiment, assignP({i}) =16,fori= 1,2, .. ,6 The Probability of the event the outcome is even ,A={2,4,6},isP(A) = P({2}) + P({4}) + P({6}) =12EE 178/278A: Basic ProbabilityPage 1 16 If is countably infinite, we can again assign probabilities to elementaryeventsExample: Assume ={1,2, ..}, assign probability2 kto event{k}The Probability of the event the outcome is even P(outcome is even) = P({2,4,6,8, ..})= P({2}) + P({4}) + P({6}) +..= k=1P({2k})= k=12 2k=13EE 178/278A: Basic ProbabilityPage 1 17 Probability for Continuous Sample space Recall that if a sample space iscontinuous, is uncountably infinite For continuous , we cannot in general define the Probability measurePby firstassigning probabilities to outcomes To see why, consider assigning a uniform Probability measure to = (0,1] In this case the Probability of each single outcome event is zero How do we find the Probability of an event such asA=[12,34]?)

7 For this example we can define uniform Probability measure over[0,1]byassigning to an eventA, the probabilityP(A) = length ofA, ,P([0,1/3] [2/3,1]) = 2/3 Check that this is a legitimate assignmentEE 178/278A: Basic ProbabilityPage 1 18 Another example: Romeo and Juliet have a date. Each arrives late with arandom delay of up to 1 hour. Each will wait only 1/4 of an hour before is the Probability that Romeo and Juliet will meet?Solution: The pair of delays is equivalent to that achievable by picking tworandom numbers between 0 and 1. Define Probability of an eventas itsareaThe event of interest is represented by the cross hatched Probability of the event is:area of crosshatched region= 1 2 12( )2= 178/278A: Basic ProbabilityPage 1 19 Basic Properties of Probability There are several useful properties that can be derived fromthe axioms (Ac) = 1 P(A) P( ) = 0 P(A) 12. IfA B, thenP(A) P(B) (A B) = P(A) + P(B) P(A B) (A B) P(A) + P(B), or in generalP( ni=1Ai) n i=1P(Ai)This is called theUnion of Events Bound These properties can be proved using the axioms of Probability and visualizedusing Venn diagramsEE 178/278A: Basic ProbabilityPage 1 20 Conditional Probability Conditional Probability allows us to compute probabilities of events based onpartial knowledge of the outcome of a random experiment Examples: We are told that the sum of the outcomes from rolling a die twice is 9.

8 Whatis the Probability the outcome of the first die was a 6? A spot shows up on a radar screen. What is the Probability thatthere is anaircraft? You receive a 0 at the output of a digital communication system. What is theprobability that a 0 was sent? As we shall see, conditional Probability provides us with two methods forcomputing probabilities of events: thesequentialmethod and thedivide-and-conquermethod It is also the basis ofinferencein statistics: make an observation and reasonabout the causeEE 178/278A: Basic ProbabilityPage 1 21 In general, given an eventBhas occurred, we wish to find the Probability ofanother eventA,P(A|B) If all elementary outcomes are equally likely, thenP(A|B) =# of outcomes in bothAandB# of outcomes inB In general, ifBis an event such thatP(B)6= 0, theconditional probabilityofany eventAgivenBis defined asP(A|B) =P(A B)P(B),orP(A, B)P(B) The functionP( |B)for fixedBspecifies a Probability law, , it satisfies theaxioms of probabilityEE 178/278A: Basic ProbabilityPage 1 22 Example Roll a fair four-sided die twice.

9 So, the sample space is{1,2,3,4}2. All samplepoints have Probability 1/16 LetBbe the event that the minimum of the two die rolls is 2 andAm, form= 1,2,3,4, be the event that the maximum of the two die rolls ism. FindP(Am|B) Solution:fffffffffffffffffffff2nd roll1st roll12341234-6mP(Am|B)1234EE 178/278A: Basic ProbabilityPage 1 23 Conditional Probability Models Before: Probability law conditional probabilities Reverse is often more natural: Conditional probabilities Probability law We use thechain rule(also calledmultiplication rule):By the definition of conditional Probability ,P(A B) = P(A|B)P(B). SupposethatA1, A2, .. , Anare events, thenEE 178/278A: Basic ProbabilityPage 1 24P(A1 A2 A3 An)= P(A1 A2 A3 An 1) P(An|A1 A2 A3 An 1)= P(A1 A2 A3 An 2) P(An 1|A1 A2 A3 An 2) P(An|A1 A2 A3 An 1)..= P(A1) P(A2|A1) P(A3|A1 A2) P(An|A1 A2 A3 An 1)=n i=1P(Ai|A1, A2, .. , Ai 1),whereA0= EE 178/278A: Basic ProbabilityPage 1 25 Sequential Calculation of Probabilities Procedure:1.

10 Construct a tree description of the sample space for a sequential experiment2. Assign the conditional probabilities on the corresponding branches of the tree3. By the chain rule, the Probability of an outcome can be obtained bymultiplying the conditional probabilities along the path from the root to theleaf node corresponding to the outcome Example (Radar Detection): LetAbe the event that an aircraft is flying aboveandBbe the event that the radar detects it. AssumeP(A) = ,P(B|A) = , andP(B|Ac) = is the Probability of Missed detection?, ,P(A Bc) False alarm?, ,P(B Ac)The sample space is: ={(A, B),(Ac, B),(A, Bc),(Ac, Bc)EE 178/278A: Basic ProbabilityPage 1 26 Solution: Represent the sample space by a tree with conditional probabilities onits edges} P(A) = } P(B|A) = }@@@@@@P(Bc|A) = (A, B)}AAAAAAAAAAAAP(Ac) = } P(B|Ac) = }(A, Bc)(Missed detection)@@@@@@P(Bc|Ac) = }(Ac, B)(False alarm)(Ac, Bc)EE 178/278A: Basic ProbabilityPage 1 27 Example: Three cards are drawn at random (without replacement) from a deckof cards.