LECTURE 3: BASIC PROBABILITYTHEORYKey words: Permutation, Combination, Bayes Theorem, Conditional Probability, Independence,Multiplication RuleRequired Textbook: The material in this lecture is related to Sections 2.3, 2.6, 2.7 and 2.8.Methods of CountingSome Implications of ProbabilityQuestion: How to evaluate probability of event A?Some Implications(i) If event A includes k basic outcomes A1; A2; :::; Akin S. Then A = [ki=1Ai; andP (A) =Pki=1P (Ai):This is the basic formula to compute the probability of any event.(ii) If there are totally n basic outcomes A1; A2; :::; Anin S, ThenPni=1P (Ai) = 1.Questions: Suppose A1; A2; :::; Anare collectively exhaustive for S: Then(a) Is P ([ni=1Ai) = 1? (b) IsPni=1P (Ai) = 1?(iii) If S consists of n equally likely basic outcomes A1; :::; An; then P (Ai) = n1for alli = 1; :::; n :(iv) If S consists of n equally likely basic outcomes A1; :::; An; and event A consists of nAbasic outcomes. ThenP (A) =# of basic outcomes in A# of basic outcomes in S=nAn:Remark: We will consider two important counting methods (permutation and combination) tocalculate probability.Fundamental Theorem of Counting: If a random experiment consists of k separate tasks,the i th of which can be done in niways, i = 1; 2; :::; k, then the entire job can b e done inn1 n2 ::::  nkways.Proof: First prove for k=2; then by induction.The …rst task can be done in n1ways, and for each of these ways, there are n2to do thesecond tasks. Therefore, the total ways for doing the …rst and the second jobs is n1 n2:1PermutationExample: Suppose you are going to choose two letters from four letters fA,B,C,Dg in di¤erentorders, with each letter being used at most once each time. How many possible orders could youhave?AB, BA,AC, CAAD, DABC, CBBD, DBCD, DCThere are 12 ways.Question: How many ways to choose 20 letters from the 26 letters. How many di¤erent ways?General problem: Suppose that there are x boxes arranged in row and there are n objects,where x  n. We are going to choose x from the n objects to …ll in the x boxes. Each objectcan be used at most once in each arrangement. How many possible di¤erent sequences couldyou obtain?(i) First, how many ways I can …ll box 1. There are n objects, so there are n ways.(ii) Second, suppose I have …lled Box 1, then how many di¤erent ways can I …ll Box 2?Because there has been one object used to …ll box 1, n-1 objects remain and each of thesen  1 objects can be used to box 2. Therefore, there are (n  1) ways to …ll box 2.Note: There are n (n  1) ways to …ll the …rst two boxes.(iii) Third, suppose that I have …lled the …rst two boxes, then there are n-2 ways to …ll thethird box.Note: there are n(n  1)(n  2) ways to …ll the …rst three boxes..... .(x) The last box (i.e. the x-th box), there are n  (x  1) objects left, so there are n-(x-1)ways …ll the last box.The total number of possible orderings of n objects isPxn= n(n  1)(n  2)::::(n  (x  1))= n!=(n  x)!:This is called “n factorial”.Convention: 0!=1.2Now verify the previous example: n=4, x=2.Pxn= P24= n!=(n  x)! = 4!=(4  2)! = 12:Example: A company has six sales representatives and has the following incentive scheme.It decides that the most successful representative during the previous year will be awarded aJanuary vacation in Hawaii, while the second most successful will win a vacation in Las Vegas.The other representatives will be required to attend Econ 3130 at Cornell. How many di¤erentoutcomes are possible?ANS: Ordering matters here. Use Permutation: n = 6; x = 2:Pxn= n!=(n  x)! = 6!=(6  2)! = 30:Example [Birthday Problem]: Suppose there are k students in this class, where 2  k  365:What is the probability that at least two students have the same birthday? (That is, on thesame day of the same month, not not necessarily of the same year)?Assumptions:(i) No twins.(ii) Each of the 365 days is equally likely be to the birthday of anyone in the class.(iii) Anyone born on Feb 29 will be considered as on March 1.ANS:First, how many possible ways in which the whole class could be born? This is a problem ofordering with replacement:365  365      365 = 365k:Second, the event that at least 2 students have the same birthday is complement to the eventActhat all k people have di¤erent birthdays?How many ways that k people can have di¤erent birthdays? This is a problem of choosing kdi¤erent days of out of 365. We have365!(365  k)!Therefore,P (A) = 1  P (Ac)= 1 365!=(365  k)!365k:Remark: k = 20; P = 0:411; k = 30; P = 0:706; k = 40; P = 0:891;k = 50; P = 0:970:CombinationExample: Suppose you are going to choose two letters from four letters A,B,C,D. Each letteris used at most once in each arrangement but now we are not concerned with their ordering.How many possible pairs could you have?3fA,Bg fA,Cg fA,Dg fB,Cg fB,Dg fC,Dg.There are six possible ways of choosing 2 out of the four, without ordering.It is better to write {A,B}, {B,C}, {A,D}, {B,C}, {B,D}, {C,D}.More generally, suppose we are interested in the number of di¤erent ways that x objects canbe chosen from the n objects but are not concerned about the order of the x objects. Also, eachobject can be used at most only once in each arrangement. How many ways?Basic formula:The total number of choosing x from n with ordering= total number of choosing x from n (without ordering) the number of ordering x objects.Pxn= Cxn x!That is,n!(n  x)!= Cxn x!:It follows thatCxn=Pxnx!=n!(n  x)!x!:(i) First, to cho ose x objects from n, there are n!=(n  x)! possible ordered sequences.(ii) x objects can be ordered in x! ways.It follows that the number of combinations of choosing x from n without order isCxn= (nx) = Pxn=x! = n!=x!(n  x)!Verify Example 2. n = 4; x = 2:More examples below:Example: A personnel o¢ cer has 8 candidates to …ll 4 positions. Five candidates are men, andthree are women, If in fact, every combination of candidates is equally likely to be chosen, whatis the probability that no women will be hired?ANS: Let event A be “no woman is hired”.Step: Find the number of basic outcomes in S:(a) Note that ordering does not matter. How many ways to select 4 out of 8? The totalnumber of possible combinations of candidates is4n = 8; x = 4:C48=n!(n  x)!x!=8!(8  4)!4!= 70:(b) Now in order to for no women to be hired, the four successful candidates must come fromthe available …ve men. The