Coupon Collecting with Quotas

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 genera...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2008-08, Vol.15 (1)
Main Author: May, Russell
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1077-8926
1077-8926
DOI:10.37236/906