conference paper published yes Dan-Adrian Alistarh author 4A899BFC-F248-11E8-B48F-1D18A9856A870000-0003-3650-940X Peter Davies author 11396234-BB50-11E9-B24C-90FCE56974250000-0002-5646-9524 DaAl department SIROCCO: International Colloquium on Structural Information and Communication Complexity ISTplus - Postdoctoral Fellowships project 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. https://research-explorer.ista.ac.at/download/9620/9621/Population_Coupon_Collector.pdf application/pdfno Springer Nature2021Wrocław, Poland eng 0302-9743 1611-3349 9783030795269 00129278840000110.1007/978-3-030-79527-6_1 128103-12 Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” <i>Structural Information and Communication Complexity</i>, vol. 12810, Springer Nature, 2021, pp. 3–12, doi:<a href="https://doi.org/10.1007/978-3-030-79527-6_1">10.1007/978-3-030-79527-6_1</a>. Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: <i>Structural Information and Communication Complexity</i>. Vol 12810. Springer Nature; 2021:3-12. doi:<a href="https://doi.org/10.1007/978-3-030-79527-6_1">10.1007/978-3-030-79527-6_1</a> D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,” in <i>Structural Information and Communication Complexity</i>, Wrocław, Poland, 2021, vol. 12810, pp. 3–12. D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 3–12. Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” In <i>Structural Information and Communication Complexity</i>, 12810:3–12. Springer Nature, 2021. <a href="https://doi.org/10.1007/978-3-030-79527-6_1">https://doi.org/10.1007/978-3-030-79527-6_1</a>. 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, D.-A., &#38; Davies, P. (2021). Collecting coupons is faster with friends. In <i>Structural Information and Communication Complexity</i> (Vol. 12810, pp. 3–12). Wrocław, Poland: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-79527-6_1">https://doi.org/10.1007/978-3-030-79527-6_1</a> 96202021-07-01T11:04:43Z2025-09-10T10:04:46Z