ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let nn and ellell be fixed positive integers. A fair mechanism consists of a family of ellell-subsets of an nn-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 ellell-subsets.

Grunbaum–Yaakobi conjecture. Among all fair mechanisms on fixed parameters (n,ell)(n,ell), 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.