Introduction To Probability Models
Introduction To Probability Models STAT 22500
Popular in Course
Popular in Statistics
This 17 page Class Notes was uploaded by Bailey Macejkovic on Saturday September 19, 2015. The Class Notes belongs to STAT 22500 at Purdue University taught by Ryan Martin in Fall. Since its upload, it has received 74 views. For similar materials see /class/207941/stat-22500-purdue-university in Statistics at Purdue University.
Reviews for Introduction To Probability Models
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/19/15
Stat 225 Lecture Notes Counting Techniques Ryan Martin Spring 2009 1 Basic Counting Rule Recall that in the classical probability model7 the probability of an event E is ME l E 7 11 lt gt m lt gt the number of outcomes in E divided by the total number of outcomes Counting the number of outcomes that make up a given event can be very dif cult and impractical since7 even for relatively simple situations7 there can be a tremendous number of such outcomes For example 0 There are 275987960 ways to deal a poker hand 0 A sequence of 10 tosses of a coin has 1024 possible outcomes 0 There are 13983816 to select 6 out of 49 lottery numbers Let7s consider an easier example rst Example 11 Suppose we ip a coin and then roll a 6 sided die Let E be the event that we get a Tail77 on the coin and an even number on the die To use formula 11 to nd ENE7 we need to know the total number of outcomes From a tree diagram see Figure 1 it is easy to see that there are 12 possible outcomes Three of the outcomes result in a Tail77 and an even roll7 therefore7 ME 312 025 Exercise 12 I own 5 shirts7 2 pair of pants and two pair of shoes How many di erent out ts could I wear Draw a tree diagram Mathematicians are lazy and did not want to work this hard They developed a set of counting rules7 which are included in what is called combinatorics The rst is the Basic Counting Rule BCR7 often called the multiplication rule for obvious reasons Proposition 13 BCR Suppose that r actions are to be performed in a de nite order Suppose further that there are ink possibilities for action k for k 1 r Then there are mlmg m possibilities altogether for the r actions Fig 1 A tree diagram for Exercise 11 The rst set of branches denote the outcome of the coin toss H or T and the second set denote the outcome of the die roll 176 Exercise 14 If you rolled four fair six sided dice7 what is the probability that you get at least one 3 Exercise 15 How many di erent pizzas can be made with 10 distinct toppings More generally7 how many possible subsets does a set containing 71 elements have Exercise 16 Let A and B be nite sets7 each with n elements How many one to one functions are there from A to B Relate your answer to the number of tries it would take to successfully decode a simple substitution cipher by guessing Note a substitution cipher is the coding scheme used in a standard cryptogram 2 Sampling With and Without Replacement De nition 21 Consider a population with N members 0 Sampling with replacement is where 71 members of the population are selected7 one at a time7 and after the observation is made the member is returned to the population for possible re selection 0 Sampling without replacement is the same as with7 except the selected member is not returned to the population for re selection Exercise 22 ls the experiment of ipping a coin ve times considered sampling with replacement or without Exercise 23 How many possible outcomes are there if you draw three cards from standard deck with replacement Without replacement Exercise 24 A baseball team has nine starting players How many di erent batting orders does the coach have to choose from 3 Permutations First is a de nition you may recall from calculus De nition 31 The product of the rst n positive integers is called n factorial and is denoted by nl De ne 0 1 De nition 32 A permutation of r objects from a collection of m objects is any ordered arrangement of r distinct objects from the m objects The number of possible permuta tions of r objects that can be formed from a collection of m objects is denoted In the above de nition the term ordered77 means that the order in which the objects are arranged matters matters in the sense that di erent ordering count as di erent permutations In other words a permutation abc is not the same as bac since they are not in the same order A standard example of this are the so called committee problems which we will encounter shortly Exercise 33 Consider a collection of four objects u my a List all possible permutation of two objects from the collection of four b How many permutations are there in your list from a c Use the BCR to determine 42 Even in the relatively simple exercise above listing all possible permutations is te dious The permutation rule will help simplify this task Proposition 34 Permutations Rule The number of permutations ofr objects from a collection ofm objects is ml m m 7 r Proof We will use the BCR to prove the claim The kth action is choosing one of the remaining in 7 k 1 objects remaining from the list of m where k 1 r In the notation of the BCR mkm7k1 k1r Then according to the BCR in would be the product of the mk7s ie mm71m7r1m7r1 ml T 1 7 1 7 m mltm m Tgt mirm7r711 ier which proves the claim D Exercise 35 Suppose 6 teams take part in an international soccer championship How many ways can the gold silver and bronze medals be distributed among the teams as sume there are no ties Exercise 36 You and two friends visit a local restaurant that features 10 different beverages How many ways can you and your thirsty friends each enjoy a beverage An important special case of the permutations rule is Proposition 37 Special Permutations Rule The rzumber of possible permutations of m objects among themselves is ml Proof WT 64 ml D Exercise 38 Five children will sit down randomly in a line of ve chairs How many possible arrangements of children are there What is the probability that the two friends Matt and Ben sit next to one another Exercise 39 Suppose 3 business 5 mathematics and 2 statistics books are arranged randomly on a shelf What is the probability that the books of the same subject are together Nearly all probability courses discuss the following problem called the Birthday Prob lem Not only does its solution require the counting techniques discussed above but the conclusion is quite surprising BIRTHDAY PROBLEM Assume that people7s birthdays are equally likely to occur among the 365 days of the year we are ignoring leap years and the fact that birth rates are not constant over the entire year What is the probability that at least two people in a group of size n will share the same birthday It is obvious that the probability changes with 71 why Let E be the event that at least two people out of 71 share the same birthday and let 0 The surprising result in this problem is that 0 can be relatively large for small 71 somewhat contrary to what one would expect Under the classical probability model 0 Now NQ is just the number of ways we could choose 71 birthdays sampling with replacement First NQ of ways to choose 71 b days w replacement 365 For the numerator we make use of the complementation rule That is of ways to choose 71 distinct b days 365 which is sampling without replacement Putting everything together we have 1 2 71 017PE 17177 17717 365 365 365 Using a computer program we can graph 0 versus 71 to see what happens see Figure 2 Note that 023 gt 05 and 060 m 1 Fig 2 Plot of 9 vs n 4 Combinations A concept related to permutations is combinations7 which we de ne below De nition 41 A combination of r objects from a collection ofm objects is an unordered arrangement of r distinct objects from the m objects The number of possible combina tions of r objects that can be formed from a collection of m objects is denoted and read in choose r7 The de nition of a combination is similar to that of a permutation The important di erence is in the keyword unordered This will be discussed in more detail in the following section Exercise 42 Explain what is meant by unordered77 in the de nition of combination Exercise 43 A popular brewpub features a sampler special 10 off your choice of two out of the ve beer selections Write out all possible samplers that are available How many are there Exercise 44 Which is larger7 m or Just as they did for permutations7 the lazy mathematicians developed a rule for the number of combinations to simply calculation of Proposition 45 Combinations Rule The number ofpossible combinations ofr objects from a collection ofm is m 7 ml r T rlm 7 ry these numbers are referred to as binomial coef cients Exercise 46 Explain how this follows immediately from the Permutations Rule Before we get to the examples let7s rst discuss how to compute Most calculators have factorial functions However you may encounter problems when m is large It is often better to use the equivalent expression for mm 1m127 3939m 7 1 In the next exercise you are asked to prove that can be de ned recursively This recursive relation how a computer nds can also be used to construct the diagram called Pascal s Triangle shown below Pascal7s Triangle Exercise 47 Prove the following identity for k S n n n n 1 k71k k Example 48 Suppose three balls are to be placed randomly in three boxes What is the probability that exactly one box remains empty Let E be the said event There are 3 ways to choose the one box that remains empty 2 ways to choose the box that gets two balls and 2 ways to place the balls Thus NE 3 2 2 12 Finally the total number of ways to distribute the three balls is found as follows There are 3 boxes we could put the rst ball in 3 boxes we could put the second ball in and 3 boxes would could put the third ball in thus NQ 33 27 Therefore the probability that exactly one box remains empty is 4 ME 7 7 i 7 m 044 9 Exercise 49 A teacher plans to construct a 25 question exam from previous exams The previous exams consist of 50 true false questions and 80 multiple choice questions a How many exams can be constructed b How many exams can be constructed having exactly 13 true false questions Exercise 410 Suppose the statistics department consists of 15 full professors 10 asso ciate professors and 25 assistant professors If a committee of 6 is selected at random what is the probability that all the members of the committee are associate professors Exercise 411 In the de nition of it was mentioned that these numbers are often referred to as binomial coe cients and this exercise explains why From calculus you are certainly familiar with the Binomial Theorem if n 2 1 then V L a b Zemkakbn k a b E R k0 for some sequence of numbers cmk Prove that on 5 Combinations vs Permutations The key difference in the de nition of permutation and combination is whether or not ordering matters That is in the context of permutations the two collections 1102 and a2a1 would be considered different while in the context of combinations those collections would be the same Standard problems that illustrate the difference are committee problems If you are asked to choose a three person committee from a group of ten people this is a combi nation problem Alternatively if the committee consists of a president vice president and treasurer then the problem is a permutation problem In summary Permutation gt order matters Combination gt order does not matter 6 Partitions The nal class of counting problem we will consider is that of counting the number of ways a collection can be partitioned into distinct subgroups De nition 61 An ordered partition ofm objects into h distinct groups ofsizes 7711 771 is any division of the m objects into a combination of m objects constituting group i for i 12 h The number of such partitions possible is denoted by m m1m2gtmgtmk 39 Exercise 62 Suppose you have six differently colored balls and three baskets ln how many ways can you put three balls in the rst basket two in the second and one in the third Proposition 63 Partitions Rule Let m1 771 be non negative integers whose sum is m The number of possible ordered partitions of m objects into h groups of size 7711 mk respectively is lt m ml 7 m1mk m1lmkl and these numbers are referred to as multinomial coef cients Exercise 64 Explain how the Combinations Rule is simply a special case of the Parti tions Rule Exercise 65 How many possible arrangements of the letters BOILERS are there This can be done using the BCR as well as the Partitions Rule Give both arguments Exercise 66 In the game of Bridge each of four players are dealt 13 cards from a 52 card deck What is the probability that one player gets all the spades Example 67 The Partition rule can also be used when some orderings are indistin guishable7 Suppose we have a handful of Skittles consisting of 5 red 3 orange and 2 yellow Skittles Note that we cannot tell the difference between those Skittles of the same color So given an arrangement such as RRYOYRORRO we could interchange the rst two reds and still as far as we can tell have the same arrangement We think about this problem as follows for each of the 10 arrangements there are 5 ways we can order the reds 3 ways we can order the oranges and 2 ways we can order the yellows within the arrangment of 10 Therefore the number of distin guishable arrangments is 10 i 10 5 32 532 39 7 More Practice Problems Counting problems can often be dif cult to solve because it is not immediately obvious which of BCR Permutations Combinations or Partitions Rule you should use In some cases you will need a combination of more than one of the rules It takes practice to be able to easily solve these problems Here are some to try Exercise 71 If ve girls and ve boys are randomly assigned to one of ten positions in a line what is the probability that all the girls are in a row and all the boys are in a row Exercise 72 In some state the license plate numbers consist of three distinct letters followed by three distinct digits 079 How many different license plates can be made Exercise 73 You are required to select a six character case sensitive password for an online account Each character may be an upper case letter a lower case letter or a digit from 079 How many different passwords can be created under each of the following restrictions a There are no restrictions b The rst character may not be a number c The last four characters must all be different d There must be at least one upper case and at least one lower case letter Exercise 74 A club has 11 members How many ways can a president7 Vice president and treasurer be chosen Exercise 75 A deck of cards labeled 1 2 n is shuf ed and the cards are dealt one at a time What is the probability that the tenth card dealt is the card labeled 10 Exercise 76 A fair coin is ipped ten times What is the probability you get exactly ve Heads Exercise 77 Briefcases often have a lock with a three digit combination Find the probability that a thief guesses the correct combination if a The three digits in the combination must be distinct and order does not matter b The three digits in the combination must be distinct and order does matter c The three digits in the combination need not be distinct and order does not matter d The three digits in the combination need not be distinct and order matters Exercise 78 If four die are rolled7 what is the probability they all show different faces Exercise 79 Prove the combinatorial identity 2 133 7 3 12 7 if using probabilistic reasoning and ii algebra and the Combinations Rule Exercise 710 Consider a game of bridge Find the probability of the following hands a Exactly two Aces b An 8 4 1 distribution c A 5 5 2 1 distribution d No Diamonds 8 Even More Practice Problems Warning Some of these problems are dif cult 1 In the game of Bridge7 each of four players are dealt 13 cards from a 52 card deck How many ways can this be done Hint use the Partitions rule What is the probability that one player gets all spades 2 Suppose 71 balls are distributed randomly in 71 boxes What is the probability that exactly one of the 71 boxes is empty Hint See Example 48 3 If Sam and Peter are among 71 men who are arranged at random in a line7 what is the probability that exactly k men are seated between them 4 lTaP will soon require we each change our passwords every 30 days Furthermore7 they recommend not using actual words because these are easier to hack into Many people have expressed concern that it will be dif cult to remember their password if it is always changing Here are the strategies of two hypothetical Purdue students a So that Tiffany can remember her password7 she decides to use a pattern She will always have six characters and only choose from lower case letters7 digits 0797 and the tilde symbol If her password always starts with a letter and has at least two numbers and the tilde7 how many passwords can she choose from A 7 V Reggie decides to use an eight character password The rst three letters are alway A7 U and G for his birth month but the case upper or lower will be chosen randomly The remaining ve characters are three lower case letters and two digits in 079 How many passwords can Reggie create Stat 225 7 Conditional Probability Practice Problems Solutions 021109 1 Your keychain holds six keysiexactly one is your house key Suppose you arrive home after dark and cannot see the keys To open the door you randomly try each key until you get the correct one making sure you do not try the same key twice Find the probability that the third key tried is the house key using a A 7 V A O V counting techniques This experiment can be visualized as laying out the keys in a random order If the third key is to be the correct one then we only have 5 of the 6 positions free to play with There are 51 ways to arrange the other ve keys out of the total of 61 arrangements so the probability is 5161 16 the multiplication rule Let Ak be the event that the k th key tried is correct k 12 6 Then we want to nd PAf A A3 the other three tries don7t matter Using the multiplication rule we have PM 6 AS 6 AE PA1PA lA1PA3lA1 A3 56 45 14 16 a symmetry argument The correct key has come up on one of the six tries A little re ection about the approach in part a reveals that there is nothing particularly special about the third positionithat is all six of the possible positions would have the same probability Since there are six equal probabilities that must add to 1 the probability can be nothing but 16 2 Suppose you have two decks of cardsione is a standard deck and the other is a trick deck77 that has all Clubs four of each face value a If you pick a card at random from the trick deck whats the probability of selecting an Ace of Clubs Let A be the event that an Ace of Clubs is drawn and T the event that the card was drawn from the trick deck Out of the 52 cards there are 4 Ace of Clubs so the conditional probability is PAlT 452 Suppose you pick one of the two decks at random and then take a random card from the selected deck What is the probability of selecting an Ace of Clubs Use the total probability formula PA PAlTPT PA1T0PTc 45212 15212 5104 c A friend plays the game in b but does not tell you which deck she chose frorn7 only that she selected an Ace of Clubs What is the probability she drew from the standard deck We want to nd PTclA which we know would require Bayes formula c PAlTCPTC 15212 Pam PM 7 5104 715 3 The Purdue rnen7s and wornen7s basketball teams are both playing on the same night Suppose that the men will win with probability 075 and the women with probability 070 The probability that at least one of them will win is 095 a If the women win7 what is the probability that the men will also win Use the de nition of conditional probability and the addition rule PM m W PM PW i PM o W P M W lt l PM PM 075 070 7 095 0714 070 b Are the events M rnen win and W wornen win independent Since 0714 31 075 PM7 the two events are not independent Stat 225 Lecture Notes Set Theory 8 Fundamentals of Probability Ryan Martin Spring 2009 1 Set Theory Set theory is concerned with mathematical properties of very abstract collections of ob jects ln Stat 2257 we will need only the very basics7 which we discuss below This material is taken primarily from Weiss7 Section 12 11 Set Notation A set is just a collection of objects7 called elements Some common notations follow 0 Universal and Empty Sets It is assumed that there is a universal set7 denoted by U or 97 that contains everything There is also an empty set7 denoted by 07 that contains nothing 0 Containment If x is an element of a set A7 we write x E A If x is not an element of A7 we write z A o Subsets If for two sets A and B7 all elements in A are also in B7 then we A a subset of B and write A C B If A is not a subset of B7 we write A B To verify that A C B7 one must show that if z E A then x E B Sets are often de ned by some property that its elements satisfy lf Pz is a statement about 7 then x E Q is the set of all z E 9 such that PW is true For example7 Pz could be z is less than or equal to 2777 in which case7 x E Q oo 2 De nition 11 Let Q be a set with subsets A and B i The complement of A is A0 x E Q z A ii The unionoanndB isAUBEQz AoerB iii The intersection of A and B is A B x E Q z E A and z E B Exercise 12 Let Q 1234567A 1234 and B 24 6 Write out the elements in each of A U B7 A B and BC Exercise 13 lfA x x S r and B x z gt s for s S 7 describe AC and A B Those of you familiar with formal logic might see some similarities between the nota tion there and the set notation introduced above In particular U ltgt or ltgt and ltgt not To illustrate this relationship let Pz and Qz be statements concerning an element x and let A x and B x Then AUBxEQP gQ A BxEQP QQ ACEQLmPx 96 96 De nition 14 Two sets A and B are said to be disjoint if A B 0 In other words the sets A and B have no elements in common Exercise 15 For an arbitrary set A give an example of a set B such that A B 0 12 Venn Diagrams Venn diagrams are an easy way to visualize sets and set operations Let Q be the universal set with subsets A B C etc Figure 1 shows an example of a Venn diagram for three sets A B and 0 Exercise 16 Draw a Venn Diagram of A A B and A BC Exercise 17 Draw a Venn Diagram of disjoint A and B Exercise 18 Draw a Venn diagram of sets A and B such that A C B Shade in the regions A U B and A B Exercise 19 In a class with 100 students 50 like math 60 like statistics and 16 like math and statistics Draw a Venn Diagram to nd the following a How many students like only math b How many student like neither math nor statistics Be careful It is not always possible to ll in the areas of a Venn diagram directly A convenient way to handle this is to let one area be a variable say x ll in everything else as if z where known and then solve for x The next two exercises illustrate this idea Exercise 110 There are fty ve athletes training for a triathalonia race that consists of running swimming and biking On a given day you nd that o Twenty six of the athletes will swim o Twenty seven will bike 0 Thirty will run Aquot Fig 1 A Venn diagram for A7 B and 0 Can you shade in the region 0 H A U BY 0 Fourteen will run and bike 0 Three will bike and swim7 but not run 0 Eight will run7 bike and swim 0 Four will take the day off and not train Draw a three way Venn diagram and ll in the regions with the appropriate counts Hint Let x be the number in R S BC and work out everything else assuming z is known then solve for Exercise 111 Data collected over the last calendar year showed that 68 of the days where sunny7 24 of the days had min7 and 10 of the days had snow 15 of the days had sun and min7 4 had min and snow7 and surprisingly 1 of the days had min7 sun and snow Finally7 there were 22 of the days that did not t in any of these three categories Create a three way Venn diagram with all the numbers lled in 13 Order of Set Operations ln algebra7 the operations 777 7777 gtlt and 77 can be applied in many di erent orders and the order in which they are carried out matters eg ab c 31 ab ac There are similar rules for ordering the set operations 0 Commutative Laws i A U B B U A ii A B B A o Associative Laws i AUBUO AUBUO ii A B O A B O o Distributive Laws i A BUO A BUA O ii AUB O AUB AUO 0 De Morgan7s Laws 1 A U B0 AC BC ii A BC A0 U B0 Exercise 112 Draw Venn diagrams to verify that DeMorgan7s laws are true To prove these results formally7 what one must do is show that the event on the left hand side of the equal sign is a subset of the event on the right hand side7 and vice versa in other words7 events A and B are the same if and only if A C B and B C A We illustrate this logic below Proof of DeMorgtm s Law Suppose z E AUB Then z Z AUB or7 in other words7 z Z A AND z Z B Therefore7 z E A0 AND z 6 B07 or z E A0 B07 which proves A U B0 C A0 BC If we start with z E A0 B07 the argument is the same in reverse7 showing Ac B0 C A U B Therefore7 x AUBC ltgt x AUB ltgt x Aandx B ltgt AcandzEBc ltgt xEAc Bc which proves DeMorgan7s law D Exercise 113 Prove the following a AAUB ifandonlyifB CA b AA B ifandonlyifACB c AA BUA BC d A C B implies B0 C AC 2 From Set Theory to Probability ln probability7 there is an underlying random experimentirandom in the sense that the outcome cannot be determined ahead of time Set theory allows us to be able to describe the outcomes of the random experiment
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'