Collecting a Set of CouponsDate: 02/03/2000 at 09:32:18 From: Amal Subject: Probability Suppose that there are N different types of coupons and each time one obtains a coupon it is equally likely to be any one of the N types. a) Find the expected number of different types of coupons that are contained in a set of (n) coupons b) Find the variance and the expected number of coupons one needs to collect before obtaining a complete set of at least one of each type. c) Find the variance of the random variables in both case (a) and (b). Date: 02/04/2000 at 08:37:59 From: Doctor Anthony Subject: Re: Probability Hi Amal, a) Expected Number of New Numbers in a Sample ------------------------------------------- A simple model will be that of throwing a die 6 times (n = 6) and finding the probabilities of N = 1, 2, ..., 6 different numbers. This can further be modeled by thinking of distributing 6 balls into N = 1, 2, 3, 4, 5 and 6 urns. To deal with equi-probable outcomes we must use the T(n,m) function. Suppose we have n numbered balls and m numbered cells, n > m. Then the function T(n,m) is the number of ways we can distribute the balls into the cells such that no cell is empty. The required result is given by n! T(n,m) = SUM[-----------------] ...........................(1) n1!n2!n3!...n(m)! where n1 = number of objects in cell(1), n2 = number of objects in cell(2) etc. The sum is taken over all solutions of: n1 + n2 + n3 + ... + n(m) = n [and n(i) NOT= 0] With no cell empty expression (1) is denoted by T(n,m) For example: 3! 3! T(3,2) = ----- + ----- = 3 + 3 = 6 1! 2! 2! 1! 4! 4! 4! T(4,3) = -------- + -------- + -------- = 12 + 12 + 12 = 36 1! 1! 2! 1! 2! 1! 1! 1! 2! We have the following recurrence relation T(n,m) = m[T(n-1,m-1) + T(n-1,m)] For example: T(5,3) = 3[T(4,2) + T(4,3)] Think of this as the number of ways of distributing 5 objects into 3 cells so that no cell is empty. If we have already distributed 4 objects, the 5th object can be placed in one of the cells in 3 ways. Then there are 2 situations to consider. The chosen cell was empty and the other 4 had been distributed in T(4,2) ways. (This is okay because we are concerned that there should be no empty cell AFTER the 5th ball has been placed.) The chosen cell was occupied and the other 4 must then have been distributed in T(4,3) ways. It follows that T(5,3) = 3[T(4,2) + T(4,3)] The formula for T(n,m) is also given by the summation m T(n,m) = SUM[(-1)^k*C(m,k)*(m-k)^n] k=0 Example: T(5,3) = 3^5 - 3(2^5) + 3(1^5) = 243 - 96 + 3 = 150 The proof of this form of the expression follows from the inclusion-exclusion principle and I have shown it at the end so as not to get in the way of our problem with the number of different numbers showing after we throw the die 6 times. We can work through the values T(6,1), T(6,2) ... T(6,6) fairly quickly. Having calculated T(6,r) we must also multiply by C(6,r) to take account of the r cells from 6 that we can choose. T(6,1) = C(1,0) 1^6 = 1 T(6,2) = C(2,0) 2^6 - C(2,1) 1^6 = 62 T(6,3) = C(3,0) 3^6 - C(3,1) 2^6 + C(3,2) 1^6 = 540 T(6,4) = C(4,0) 4^6 - C(4,1) 3^6 + C(4,2) 2^6 - C(4,3) 1^6 = 1560 T(6,5) = C(5,0) 5^6 - C(5,1) 4^6 + C(5,2) 3^6 - C(5,3) 2^6 + C(5,4) 1^6 = 1800 T(6,6) = C(6,0) 6^6 - C(6,1) 5^6 + C(6,2) 4^6 - C(6,3) 3^6 + C(6,4) 2^6 - C(6,5) 1^6 = 720 So we have the following table: | T(6,r) C(6,r) T(6,r) x C(6,r) ------|---------------------------------- r = 1 | 1 6 6 r = 2 | 62 15 930 r = 3 | 540 20 10800 r = 4 | 1560 15 23400 r = 5 | 1800 6 10800 r = 6 | 720 1 720 -------|---------------------------------- Total = 46656 and 6^6 = 46656 so this checks the arithmetic. The probabilities are then each of the numbers divided by 6^6. The expected number of new numbers is then: 1*6 + 2*930 + 3*10800 + 4*23400 + 5*10800 + 6*720 ------------------------------------------------- 46656 = 3.9906 The calculation of E(x^2) is then 1^2*6 + 2^2*930 + 3^2*10800 + 4^2*23400 + 5^2*10800 +6^2*720 ------------------------------------------------------------ 46656 = 16.5304 And Var(x) = 16.5304 - 3.9906^2 = 0.60559 Formula for T(n,m) using Inclusion-Exclusion -------------------------------------------- Suppose we let |A| be the number of ways that cell(1) is empty, |B| is the number of ways that cell(2) is empty and |C| is the number of ways that cell(3) is empty. |U| is the universal set and is the total number of ways of distributing 5 different objects into 3 cells, = 3^5. If S(0) = |U| S(1) = |A| + |B| + |C| S(2) = |AB| + |BC| + |CA| s(3) = |ABC| Then |A'B'| = S(0) - S(1) + S(2) |A'B'C'| = S(0) - S(1) + S(2) - S(3) which means that none of cell(1), cell(2) or cell(3) is empty, and clearly this idea can be extended to any number of cells. The general formula is: m |A'B'C'D'E'...M'| = SUM[(-1)^k*S(k)] k=0 Which is the formula for T(n,m) quoted above. Example: Find T(5,3) We have S(0) = 3^5 = 243 S(1) = 2^5 + 2^5 + 2^5 = 96 S(2) = 1 + 1 + 1 = 3 S(3) = 0 = 0 and applying the formula for inclusion exclusion we get |A'B'C'| = 243 - 96 + 3 - 0 = 150 as we found before. The general formula to use for n objects and m cells is: m T(n,m) = SUM[(-1)^k*C(m,k)*(m-k)^n] k=0 b) Find the variance and the expected number of coupons one needs to collect before obtaining a complete set of at least one of each type. Here you will want to refer to my answer to "The Probable Pen in the Cereal Box" in the Dr. Math archives: http://mathforum.org/dr.math/problems/kuropatwa.11.25.99.html c) Find the variance of the random variables in both case (a) and (b) To find the variance you would need to find the value of E(x^2) for each new number, e.g. E(x^2) = 1^2(5/6) + 2^2(1/6)(5/6) + 3^2(1/6)^2*(5/6) + ... = (5/6)[1 + 4(1/6) + 9(1/6)^2 + 16(1/6)^3 + ...] The method for finding the sum of such a series is as follows: S = 1 + 2^2.x + 3^2.x^2 + 4^2.x^3 + ... INT[S.dx} = x + 2x^2 + 3x^3 + 4x^4 + ... = x[1 + 2x + 3x^2 + 4x^3 + ...] = x/(1-x)^2 from earlier part of the question and so to find the series S we differentiate this expression: (1-x)^2 + 2x(1-x) 1-x + 2x 1+x S = ----------------- = -------- = ------- (1-x)^4 (1-x)^3 (1-x)^3 putting x = 1/6 we get S = (7/6)/(5/6)^3 and E(x^2) = (5/6)(7/6)/(5/6)^3 = (7/6)/(5/6)^2 = 42/5 and var(x^2) = 42/5 - (6/5)^2 = 174/25 and similar calculations for other variances. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/