3
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ You say that you don't have a reasonably small proof. Do you have a long proof? $\endgroup$ Apr 7, 2016 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, 2016 at 18:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.