Markov chain approach to the coupon collector problem with universal coupon

Abstract

The classical coupon collector problem has various modifications and generalizations. One group of generalizations is based on the idea of introducing additional coupons, with special purposes, to the set of available coupons. We consider the case when this set consists of standard coupons (that can belong to the collection), a null coupon (which can be drawn, but does not belong to any collection), and an additional universal coupon, that can replace any of the standard coupons. By employing a Markov chain approach, we derive the exact forms of the k-step transition matrix and the fundamental matrix, which we use to obtain the properties of the waiting time until a subcollection, or a full collection is sampled, and some additional characteristics of the collecting process (probability that the coupon collecting procedure ends in a particular way). We also provide numerical examples and explain possible applications of the variant of the coupon collector problem we considered.