---
_id: '9620'
abstract:
- lang: eng
  text: "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).\r\n\r\nWe 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."
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Peter
  full_name: Davies, Peter
  id: 11396234-BB50-11E9-B24C-90FCE5697425
  last_name: Davies
  orcid: 0000-0002-5646-9524
citation:
  ama: '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>'
  apa: '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>'
  chicago: 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>.
  ieee: 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.
  ista: '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.'
  mla: 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>.
  short: D.-A. Alistarh, P. Davies, in:, Structural Information and Communication
    Complexity, Springer Nature, 2021, pp. 3–12.
conference:
  end_date: 2021-07-01
  location: Wrocław, Poland
  name: 'SIROCCO: International Colloquium on Structural Information and Communication
    Complexity'
  start_date: 2021-06-28
date_created: 2021-07-01T11:04:43Z
date_published: 2021-06-20T00:00:00Z
date_updated: 2025-09-10T10:04:46Z
day: '20'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/978-3-030-79527-6_1
ec_funded: 1
external_id:
  isi:
  - '001292788400001'
file:
- access_level: open_access
  checksum: fe37fb9af3f5016c1084af9d6e7109bd
  content_type: application/pdf
  creator: pdavies
  date_created: 2021-07-01T11:21:40Z
  date_updated: 2021-07-01T11:21:40Z
  file_id: '9621'
  file_name: Population_Coupon_Collector.pdf
  file_size: 319728
  relation: main_file
file_date_updated: 2021-07-01T11:21:40Z
has_accepted_license: '1'
intvolume: '     12810'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Preprint
page: 3-12
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Structural Information and Communication Complexity
publication_identifier:
  eisbn:
  - '9783030795276'
  eissn:
  - 1611-3349
  isbn:
  - '9783030795269'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Collecting coupons is faster with friends
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 12810
year: '2021'
...