Grunbaum–Yaakobi conjecture on fair coupon-collecting mechanisms
Statement
Let and be fixed positive integers. A fair mechanism consists of a family of -subsets of an -element coupon set in which every coupon appears in the same number of admissible sets, with the sampling distribution uniform on that family. The full model samples uniformly from all -subsets.
Grunbaum–Yaakobi conjecture. Among all fair mechanisms on fixed parameters , the full model maximizes the expected coverage time.
Grunbaum and Yaakobi established exact formulas for several fair mechanisms and general upper and lower bounds for all fair mechanisms. In all previously analyzed fair mechanisms, the expected coverage time is strictly smaller than that of the full model. It remains open whether the full model is always maximal and whether substantially larger gaps can occur.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.