The lower-bound conjecture for coupon collecting with friends

Let nn) collectors each seek a complete collection of mm coupon types. The process has a collection phase of rcr_c rounds, followed by an exchanging phase of rer_e rounds in which collectors interact and exchange coupons.

Lower-bound conjecture. If

rc=O(n+nlnnm),r_c=O\left(n+\frac{n\ln n}{m}\right),

then

re=Ω(mlogmn)r_e=\Omega(m\log mn)

is necessary to succeed with any positive constant probability.

The conjecture asserts that the currently known upper bound on the number of interactions is tight even when only a positive constant success probability is required. The motivation is that existing lower bounds account only for the difficulty of ensuring a single interaction, not for the difficulty collectors with incomplete collections face in obtaining multiple coupons during the exchanging phase.

Sources & referencesView supporting material

Primary source

Dan Alistarh and Peter Davies, “Collecting Coupons is Faster with Friends”, arXiv:2112.05830 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.