Consider a variant of the traditional coupon collector's problem. There're $n$ kinds of coupons and there's a $1 \times n$ grid. Each grid corresponds to one kind of coupon. Once picking a coupon, we color the corresponding grid. I'd like to ask what's the expected number of coupons to pick such that the maximum number of consecutive uncolored grids is not greater than $k$?

Note that if we denote the expectation as $f(n,k)$, the traditional coupon collector's problem is just $f(n,0) = n\sum_{i=1}^{n}\frac{1}{i}$.

It can also be considered as a balls-in-bins variant if viewing the grids as bins and coupons as balls. There're $n$ bins and infinite balls. At each round, a ball is put into a random bin. We are interested in the expected number of balls to put such that the maximum number of consecutive empty bins is not greater than $k$.

It seems that the problem is quite difficult, and some analysis for small cases ($k = 1, 2, \cdots)$ is also welcome.

Edit: Let $X_i$ be the number of balls in $Bin_{i}, \cdots, Bin_{i+k-1}$. The problem is simplified to calculate $Prob[X_1=0 \ \vee \cdots \vee X_{n-k+1}=0]$. Using inclusive-exclusive principle, the problem reduces to calculate $Prob_{x\in S}[x=0]$ for any subset $S$ of $\{X_1,\cdots,X_{n-k+1}\}$. But the final piece is missing since it's not easy to calculate the coefficients.

  • $\begingroup$ Where is your focus on the problem ? Asymptotics behavior when $n$ becomes large or fixed $n$ (not necessarily large) and various $k$? Pretty interesting problem indeed. $\endgroup$ – Gâteau-Gallois Dec 2 '18 at 10:57
  • $\begingroup$ Also I believe you can say quite a lot on the Markov Chain $X_l$ where $X_l$ represents your $k$ at each time step $l$. The transition matrix seems pretty easy to write at least for large values of $k$. $\endgroup$ – Gâteau-Gallois Dec 2 '18 at 11:13
  • $\begingroup$ I'm interested in the closed form of $f$. $\endgroup$ – Hang Wu Dec 2 '18 at 11:24

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.