New Results on a Generalized Coupon Collector Problem Using Markov Chains
New Results on a Generalized Coupon Collector Problem Using Markov Chains
复制标题
使用马尔可夫链的广义优惠券收集器问题的新结果
DOI：
10.1017/s0021900200012547
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
B. Sericola
中科院分区：
文献类型：
--
作者：
E. Anceaume;Yann Busnel;B. Sericola
本文研究了一个广义的优惠券收集器问题，它包括在确定的分布和时刻的时间需要收集一个给定数量的不同的优惠券，从一组优惠券与任意概率分布。我们假设有一种叫做空息票的特殊息票可以被提取，但从来不属于任何集合。在这种情况下，我们得到的分布和时刻的表达式。我们还证明了几乎均匀分布，其中所有的非空券有相同的绘图概率，是最小化的预期时间，以获得一个固定的不同的优惠券的子集的分布。将这一优化结果推广到考虑全集合时的互补分布，顺便证明了这一著名猜想。最后，我们提出了一个新的猜想，它表达了这样一个事实，即几乎均匀分布应尽量减少互补分布的时间需要得到任何固定数量的不同的优惠券。
We study in this paper a generalized coupon collector problem, which consists in determining the distribution and the moments of the time needed to collect a given number of distinct coupons that are drawn from a set of coupons with an arbitrary probability distribution. We suppose that a special coupon called the null coupon can be drawn but never belongs to any collection. In this context, we obtain expressions of the distribution and the moments of this time. We also prove that the almost-uniform distribution, for which all the non-null coupons have the same drawing probability, is the distribution which minimizes the expected time to get a fixed subset of distinct coupons. This optimization result is extended to the complementary distribution of that time when the full collection is considered, proving by the way this well-known conjecture. Finally, we propose a new conjecture which expresses the fact that the almost-uniform distribution should minimize the complementary distribution of the time needed to get any fixed number of distinct coupons.