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.

3 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: 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).}

4 ,(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.)

5 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: 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.

6 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.

7 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.

8 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: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.

9 ,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]?)

10 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.