Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Coupon Collecting with Quotas. | Coupon Collecting with Quotas Russell May 150 University Blvd. UPO 701 Morehead State University Morehead KY 40351-1689 UsA Submitted April 7 2008 Accepted Jul 28 2008 Published Aug 18 2008 Mathematics Subject Classifications 05A15 60C05 Abstract We analyze a variant of the coupon collector s problem in which the probabilities of obtaining coupons and the numbers of coupons in a collection may be non-uniform. We obtain a finite expression for the generating function of the probabilities to complete a collection and show how this generalizes several previous results about the coupon collector s problem. Also we provide applications about computational complexity and approximation. 1 Introduction Soft drink manufacturers have popularized the under-the-cap game in which they imprint a letter of a payoff word usually the name of the manufacturer itself underneath bottle caps and dispense bottles of the soft drink randomly. Consumers then buy bottle after bottle of the soft drink hoping to collect enough letters to spell out the payoff word. Discerning consumers might wonder how many bottles they would expect to purchase in order to spell out the payoff word and win the game. If the letters in the payoff word are distinct like in Sprite and the letters are distributed uniformly this problem is the same as the classic coupon collector s problem in which coupons of d kinds are randomly dispensed and collectors ask how many coupons they must obtain on average to form a complete set of at least one of each kind. A classic argument shows that on average a collector must obtain d 1 1 d coupons to form a complete set. Generalizations of the coupon collector s problem date back to at least 1934 when von Schelling in 6 and re-published in 7 computed the expected number of coupons to obtain a complete collection under the condition that the probabilities of obtaining a coupon could be non-uniform. Then in 1960 Newman and Shepp in their well-known The .
