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