Math 240 Archives - Page 3 of 9 - Shawn Zhong

7.1 An Introduction to Discrete Probability

Probability of an Event • Introduction ○ We first study Pierre-Simon Laplace’s classical theory of probability ○ which he introduced in the 18th century, when he analyzed games of chance. • Experiment ○ A procedure that yields one of a given set of possible outcomes. • Sample space ○ The sample space of the experiment is the set of possible outcomes. • Event ○ An event is a subset of the sample space. • Probability ○ If S is a finite sample space of equally likely outcomes and E is an event ○ Then the probability of E is p(E)=|E|/|S| ○ For every event E, we have 0≤p(E)≤1 ○ This follows directly from the definition because ○ 0≤p(E)=|E|/|S| ≤|S|/|S| ≤1, since 0≤|E|≤|S| Applying Laplace’s Definition • Example 1 ○ An urn contains four blue balls and five red balls. ○ What is the probability that a ball chosen from the urn is blue? ○ The probability that the ball is chosen is 4/9 ○ since there are nine possible outcomes, and four of these produce a blue ball. • Example 2 ○ What is the probability that when two dice are rolled, the sum of the numbers on the two dice is 7? ○ By the product rule there are 62 = 36 possible outcomes. ○ Six of these sum to 7. ○ Hence, the probability of obtaining a 7 is 6/36 = 1/6. • Example 3 ○ In a lottery, a player wins a large prize when they pick four digits that match, in correct order, four digits selected by a random mechanical process. ○ What is the probability that a player wins the prize? ○ By the product rule there are 104 = 10,000 ways to pick four digits. ○ Since there is only 1 way to pick the correct digits, ○ the probability of winning the large prize is 1/10,000 = 0.0001. • Example 4 ○ A smaller prize is won if only three digits are matched. ○ What is the probability that a player wins the small prize? ○ If exactly three digits are matched, one of the four digits must be incorrect and the other three digits must be correct. ○ For the digit that is incorrect, there are 9 possible choices. ○ Hence, by the sum rule, there a total of 36 possible ways to choose four digits that match exactly three of the winning four digits. ○ The probability of winning the small price is § 36/10,000 = 9/2500 = 0.0036 • Example 5 ○ There are many lotteries that award prizes to people who correctly choose a set of six numbers out of the first n positive integers, where n is usually between 30 and 60. ○ What is the probability that a person picks the correct six numbers out of 40? ○ The number of ways to choose six numbers out of 40 is § C(40,6) = 40!/(34!6!) = 3,838,380. ○ Hence, the probability of picking a winning combination is § 1/ 3,838,380 ≈ 0.00000026. • Example 6 ○ What is the probability that the numbers 11, 4, 17, 39, and 23 are drawn in that order from a bin with 50 balls labeled with the numbers 1,2, …, 50 if ○ The ball selected is not returned to the bin. § Sampling without replacement: § The probability is 1/254,251,200 since there are § 50 ∙49 ∙47 ∙46 ∙45 = 254,251,200 ways to choose the five balls. ○ The ball selected is returned to the bin before the next ball is selected. § Sampling with replacement: § The probability is 1/〖50〗^5 = 1/312,500,000 since 〖50〗^5 = 312,500,000. The Probability of Complements and Unions of Events • Theorem 1 ○ Let E be an event in sample space S. ○ The probability of the complementary event of E:E ̅ = S − E is given by ○ p(E ̅ )=1−p(E) • Proof ○ Using the fact that |E ̅ |=|S|−|E| ○ p(E ̅ )=(|S|−|E|)/|S| =1−|E|/|S| =1−p(E) • Example ○ A sequence of 10 bits is chosen randomly. ○ What is the probability that at least one of these bits is 0? ○ Let E be the event that at least one of the 10 bits is 0. ○ Then E ̅ is the event that all of the bits are 1s. ○ The size of the sample space S is 210. Hence, ○ p(E)=1−p(E ̅ )=1−|E ̅ |/|S| =1−1/2^10 =1−1/1024=1023/1024 • Theorem 2 ○ Let E_1 and E_2 be events in the sample space S. Then ○ p(E_1∪E_2 )=p(E_1 )+p(E_2 )−p(E_1∩E_2 ) • Proof ○ Given the inclusion-exclusion formula from Section 2.2 ○ |A ∪ B| = |A| + |B| − |A ∩ B|, it follows that § p(E_1∪E_2 )=|E_1∪E_2 |/|S| § =(|E_1 |+|E_2 |−|E_1∩E_2 |)/|S| § =|E_1 |/|S| +|E_2 |/|S| −|E_1∩E_2 |/|S| § =p(E_1 )+p(E_2 )−p(E_1∩E_2 ) • Example ○ What is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5? ○ Let E_1 be the event that the integer is divisible by 2 ○ Let E_2 be the event that it is divisible 5. ○ Then the event that the integer is divisible by 2 or 5 is E_1∪E_2 ○ And E_1∩E_2 is the event that it is divisible by 2 and 5. ○ It follows that: ○ p(E_1∪E_2 )=p(E_1 )+p(E_2 )−p(E_1∩E_2 )=50/100+20/100−10/100=3/5 Monty Hall Puzzle • You are asked to select one of the three doors to open. • There is a large prize behind one of the doors and if you select that door, you win the prize. • After you select a door, the game show host opens one of the other doors (which he knows is not the winning door). • The prize is not behind the door and he gives you the opportunity to switch your selection. • Should you switch? • You should switch. • The probability that your initial pick is correct is 1/3. • This is the same whether or not you switch doors. • But since the game show host always opens a door that does not have the prize, • If you switch the probability of winning will be 2/3 • Because you win if your initial pick was not the correct door • And the probability your initial pick was wrong is 2/3.

6.5 Generalized Permutations and Combinations

Permutations with Repetition • Theorem 1 ○ The number of r-permutations of a set of n objects with repetition allowed is ○ GP(n,r) n^r • Proof ○ There are n ways to select an element of the set ○ for each of the r positions in the r-permutation when repetition is allowed ○ Hence, by the product rule there are n^r r-permutations with repetition. • Example ○ How many strings of length r can be formed from the uppercase letters of the English alphabet? ○ The number of such strings is 〖26〗^r ○ which is the number of r-permutations of a set with 26 elements • Example 2 ○ How many function are there f:A→B where |A|=k, and |B|=m? m^k Combinations with Repetition • Example ○ How many ways are there to select five bills from a box containing at least five of each of the following denominations: $1, $2, $5, $10, $20, $50, and $100? ○ Place the selected bills in the appropriate position of a cash box illustrated below: ○ Some possible ways of placing the five bills: ○ The number of ways to select five bills corresponds to ○ the number of ways to arrange six bars and five stars in a row. ○ This is the number of unordered selections of 5 objects from a set of 11. ○ Hence, there are § C(11,5)=11!/5!6!=462 ○ ways to choose five bills with seven types of bills • Theorem 2 ○ The number of r-combinations from a set with n elements when repetition of elements is allowed is ○ C(n+r−1,r)=C(n+r−1,n−1) • Proof ○ Each r-combination of a set with n elements with repetition allowed can be represented by a list of n – 1 bars and r stars. ○ The bars mark the n cells containing a star for each time the ith element of the set occurs in the combination. ○ The number of such lists is C(n+r−1,r) ○ because each list is a choice of the r positions to place the stars ○ from the total of n+r−1 positions to place the stars and the bars. ○ This is also equal to C(n+r−1,n−1) ○ which is the number of ways to place the n – 1 bars • Example 1 ○ How many solutions does the equation x_1+x_2+x_3=11 (x_1,x_2,x_3∈Z+ ) have ○ Each solution corresponds to a way to select 11 items from a set with 3 elements ○ x_1 elements of type one, x_2 of type two, and x_3 of type three. ○ By Theorem 2 it follows that the number of solution is ○ C(3+11−1,11)=C(13,11)=C(13,2)=(13⋅12)/(1⋅2)=78 • Example 2 ○ Suppose that a cookie shop has four different kinds of cookies. ○ How many different ways can six cookies be chosen? ○ The number of ways to choose six cookies is ○ the number of 6-combinations of a set with four elements. ○ By Theorem 2 the number of ways to choose six cookies from the four kinds is ○ C(9,6)=C(9,3)=(9⋅8⋅7)/(1⋅2⋅3)=84 Permutations and Combinations with and without Repetition

6.4 Binomial Coefficients and Identities

$Powers of Binomial Expressions • A binomial expression is the sum of two terms, such as x+y. • (More generally, these terms can be products of constants and variables.) • We can use counting principles to find the coefficients of (x+y)^n where n∈Z+. • To illustrate this idea, we first look at the process of expanding (x+y)^3. • (x+y)(x+y)(x+y) expands into a sum of terms that are the product of a term from each of the three sums. • Terms of the form x^3,x^2 y.xy^2,y^3 arise. • The question is what are the coefficients? ○ To obtain x^3, an x must be chosen from each of the sums. ○ There is only one way to do this. So, the coefficient of x^3 is 1. ○ To obtain x^2 y, an x must be chosen from two of the sums and a y from the other. ○ There are (█(3@2)) ways to do this and so the coefficient of x^2 y is 3. ○ To obtain xy^2, an x must be chosen from of the sums and a y from the other two. ○ There are (█(3@1)) ways to do this and so the coefficient of xy^2 is 3. ○ To obtain y^3, a y must be chosen from each of the sums. ○ There is only one way to do this. So, the coefficient of y^3 is 1. • We have used a counting argument to show that (x+y)^3=x^3+3x^2 y+3xy^2+y^3 Binomial Theorem • Binomial Theorem ○ Let x and y be variables, and n a nonnegative integer. Then: ○ (x+y)^n=∑_(j=0)^n▒〖(█(n@j)) x^(n−j) y^j 〗=(█(n@0)) x^n+(█(n@1)) x^(n−1) y+⋯+(█(n@n−1))xy^(n−1)+(█(n@n)) y^n • Proof ○ We use combinatorial reasoning. ○ The terms in the expansion of (x+y)^n are of the form x^(n−j) y^j for j=0,1,2,…,n ○ To form the term x^(n−j), it is necessary to choose n−j xs from the n sums. ○ Therefore, the coefficient of x^(n−j) is (█(n@n−j)) which equals (█(n@j)). Using the Binomial Theorem • What is the coefficient of x^12 y^13 in the expansion of (2x−3y)^25? • We view the expression as (2x+(−3y))^25. • By the binomial theorem ○ (2x+(−3y))^25=∑_(j=0)^25▒〖(█(25@j)) (2x)^(25−j) (−3y)^j 〗 • Consequently, the coefficient of x^12 y^13 in the expansion is obtained when j = 13. A Useful Identity • Corollary 1 ○ With n≥0, ∑_(k=0)^n▒(█(n@k)) =2^n • Proof (using binomial theorem) ○ With x = 1 and y = 1, from the binomial theorem we see that: ○ 2^n=(1+1)^2=∑_(k=0)^n▒〖(█(n@k)) 1^k 1^(n−k) 〗=∑_(k=0)^n▒(█(n@k)) • Proof (combinatorial) ○ Consider the subsets of a set with n elements. ○ There are (█(n@0)) subsets with zero elements, (█(n@1)) with one element, (█(n@2)) with two elements, …, and (█(n@n)) with n elements ○ Therefore the total is ∑_(k=0)^n▒(█(n@k)) ○ Since, we know that a set with n elements has 2^n subsets, we conclude: ○ ∑_(k=0)^n▒(█(n@k)) =2^n Pascal’s Identity • Pascal’s Identity ○ If n and k are integers with n ≥ k ≥ 0, then ○ (█(n+1@k))=(█(n@k−1))+(█(n@k)) • Proof ○ Let T be a set where |T|=n+1,a∈T, and S=T−{a} ○ There are (█(n+1@k)) subsets of T containing k elements. ○ Each of these subsets either: § contains a with k−1 other elements, or § contains k elements of S and not a. ○ There are § (█(n@k−1)) subsets of k elements that contain a § since there are (█(n@k−1)) subsets of k − 1 elements of S § (█(n@k)) subsets of k elements of T that do not contain a § because there are (█(n@k)) subsets of k elements of S. ○ Hence § (█(n+1@k))=(█(n@k−1))+(█(n@k)) Pascal’s Triangle • The nth row in the triangle consists of the binomial coefficients (█(n@k)), k=0,1,…,n • By Pascal’s identity, adding two adjacent binomial coefficients results is • the binomial coefficient in the next row between these two coefficients.$