|
Abstract:
|
This dissertation deals with the coupon collector problem, which in its
simplest (classical) form can be formulated as follows: A collector wants to collect
a set of n distinct coupons, by buying a single coupon each day. The random
variable of interest is the waiting time until the collection is completed.
The goal of the dissertation is to propose and analyze three new generalizations
of the classical coupon collector problem obtained by introducing additional
coupons with special purposes into the set of n standard coupons.
The first two chapters are devoted to the results on the classical coupon
collector problem and the known generalizations obtained by introducing
additional coupons into the coupon set ([1], [2], [39], [54]).
New results are presented in chapters 3,4, and 5.
The third chapter of the dissertation is dedicated to the case where, in addition
to the standard coupons, the coupon set consists of a null coupon (which can
be drawn, but does not belong to any collection), and an additional universal
coupon, that can replace any standard coupon. For the case of equal probabilities
of standard coupons, the asymptotic behavior (as n → ∞) of the expectated value
and variance of the waiting time for a fixed size subcollection of a collection of
coupons is obtained when one or both probabilities of additional coupons are fixed,
and the remaining coupons have equal small probabilities. These results, published
in [27], generalize part of the results in [2]. The same problem is analyzed using a
Markov chain approach, which led to the determination of the fundamental matrix
and some related features of the collection process (probability that the coupon
collection process ends in a certin way). These results are contained in the paper
[24]. For the case of unequal probabilities of standard coupons, a class of bounds
is derived for the first and second moments of the waiting time until the end of the
experiment by using majorization techniques and refining the bounds proposed in
[51]. The quality of the proposed bounds is tested in numerical experiments, and
the specific bounds from the class with the most desirable properties are given.
These results are published in [26].
The fourth chapter of the dissertation deals with the generalization in which
the additional coupon (so called, penalty coupon) interferes with the collection of
standard coupons in the sense that the collection process ends when the absolute
difference between the number of collected standard coupons and the number
of collected penalty coupons is equal to n. This generalization can be seen as a
special case of the random walk with two absorbing barriers. The distribution and
a simple upper bound on the first moment of the corresponding waiting time are
determined by combinatorial considerations. The application of the Markov chain
approach led to obtaining the fundamental matrix. These results are published in
[53].
In the fifth chapter of the dissertation another additional coupon (so called
reset coupon) is introduced, which acts as a reset button, in the sense that the set
of coupons drawn up to time (day) t becomes empty if the reset coupon is drawn on
day t+1. In the case of unequal probabilities of standard coupons, the distribution
of the corresponding waiting time is obtained by combinatorial considerations. For
the case of equal probabilities of obtaining standard coupons, For the case of equal
probabilities, applying the first step analysis for the correspondingly constructed
Markov chains led to the expressions for the expected waiting time and its simple
form in terms of the beta function. These results are used for analysing the
asymptotic behavior (when the size of the collection tends to infinity) of the
expected waiting time, taking into account possible values of the probability of
obtaining a reset coupon. These results are published in [25].
Setting the probabilities of the additional coupons to zero, all three
generalizations of the coupon collector problem defined and analyzed in this
dissertation as well as the obtained results reduce to the corresponding results
for the classical coupon collector problem. |