Collecting coupons is faster with friends

Alistarh D-A, Davies P. 2021. Collecting coupons is faster with friends. Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 12810, 3–12.

Download
OA Population_Coupon_Collector.pdf 319.73 KB

Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019). We provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.
Publishing Year
Date Published
2021-06-20
Proceedings Title
Structural Information and Communication Complexity
Acknowledgement
Peter Davies is supported by the European Union’s Horizon2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.
Volume
12810
Page
3-12
Conference
SIROCCO: International Colloquium on Structural Information and Communication Complexity
Conference Location
Wrocław, Poland
Conference Date
2021-06-28 – 2021-07-01
ISSN
eISSN
IST-REx-ID

Cite this

Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: Structural Information and Communication Complexity. Vol 12810. Springer Nature; 2021:3-12. doi:10.1007/978-3-030-79527-6_1
Alistarh, D.-A., & Davies, P. (2021). Collecting coupons is faster with friends. In Structural Information and Communication Complexity (Vol. 12810, pp. 3–12). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_1
Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” In Structural Information and Communication Complexity, 12810:3–12. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_1.
D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,” in Structural Information and Communication Complexity, Wrocław, Poland, 2021, vol. 12810, pp. 3–12.
Alistarh D-A, Davies P. 2021. Collecting coupons is faster with friends. Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 12810, 3–12.
Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” Structural Information and Communication Complexity, vol. 12810, Springer Nature, 2021, pp. 3–12, doi:10.1007/978-3-030-79527-6_1.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2021-07-01
MD5 Checksum
fe37fb9af3f5016c1084af9d6e7109bd


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search