Assume that you draw coupons uniformly at random from a collection of $n$ coupons and you want to collect $m_i$ coupons of type $i$. This is referred to as the coupon collector with quota (http://www.combinatorics.org/ojs/index.php/eljc/article/download/v15i1n31/pdf)

Assume now that you draw your coupon by batches of $k\le n$ distinct coupons and let $T_{\vec{m},k})$ be the number of coupons that one has to buy in order to collect $m_i$ coupons of type $i$ (for each $i$).

Intuitively (and numerically), the expectation $\mathbb{E}[T_{\vec{m},k}]$ is decreasing in $k$ but I am not able to find a reference (or a proof for general $k$).

My questions are:

  • does anyone know a reference?
  • is it still true if the batches are of random size or if the coupons have non uniform probabilities?

Note that the $T_{\vec{m},k}$ are not stochastically ordered. For example when $\vec{m}=(2,0)$, we have $T_{\vec{m},1}$ and $T_{\vec{m},2}$ have the same mean but none of them is stochastically greater than the other one.

Edit: answer for $k=2$ (11 april)

For $k=1$, the function $E(m,k)=\mathbb{E}[T_{k,m}]$ is uniquely defined by: $$ E(x,1) = \left\{ \begin{array}{ll} 0 & if x =0\\ 1+\frac{1}{N}\sum_{i=1}^n E((x-e_{i})^+,1) & \end{array}\right.$$ where $e_i$ is the vector with a "1" on its $i$th coordinate and 0 otherwise; $(x)^+=max(x,0)$ (coordinate-wise).

More generally, for $k\ge 1$, we have: $$ E(x,k) = \left\{ \begin{array}{cc} 0 & if x =0\\ 1+\frac{(N-k)!}{N!}\sum_{i_1\dots i_k distincts} E((x-e_{i_1}-\dots-e_{i_k})^+,k) & \end{array}\right.$$

Using the above equation, I am able to show by induction on $x$ that $E(x,2)\le E(x,1)$ by showing that $2E(x-e_i-e_j) \le E(x-2e_i) + E(x-2e_j)$.

  • $\begingroup$ You say that you don't have a reasonably small proof. Do you have a long proof? $\endgroup$ – Douglas Zare Apr 7 '16 at 18:29
  • $\begingroup$ I have a proof that $k=2$ requires less coupon than $k=1$. This proof is based on using a recurrence equation (on $m$) for $\mathbb{E}[T_{k,\vec{m}}]$. $\endgroup$ – N. Gast Apr 7 '16 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.