Uniform distribution conjecture for the generalized coupon collector time

Let n1n\geq 1, let c{1,,n}c\in\{1,\ldots,n\}, and let p=(p1,,pn)(0,1)np=(p_1,\ldots,p_n)\in(0,1)^n satisfy p1++pn1p_1+\cdots+p_n\leq 1. Write

p0=1(p1++pn),v=(v1,,vn),vi=1p0n,u=(1n,,1n).p_0=1-(p_1+\cdots+p_n),\qquad v=(v_1,\ldots,v_n),\quad v_i=\frac{1-p_0}{n},\qquad u=\left(\frac1n,\ldots,\frac1n\right).

Here Tc,n(p)T_{c,n}(p) denotes the time needed in the generalized coupon collector problem with coupon distribution pp. Uniform distribution conjecture. For every k0k\geq 0,

\mathbbmP{Tc,n(p)>k}\mathbbmP{Tc,n(v)>k}\mathbbmP{Tc,n(u)>k}.\mathbbm{P}\{T_{c,n}(p)>k\}\geq\mathbbm{P}\{T_{c,n}(v)>k\}\geq\mathbbm{P}\{T_{c,n}(u)>k\}.

Equivalently, the complementary distribution function of Tc,nT_{c,n} is minimized by the uniform distribution, with the intermediate equalization distribution vv providing the stated comparison. The paper presents this as a new conjecture; no resolution is supplied in the given text.

Sources & referencesView supporting material

Primary source

Emmanuelle Anceaume, Yann Busnel and Bruno Sericola, “New results on a generalized coupon collector problem using Markov chains”, arXiv:1402.5245 (2014).

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.