# Coupon Collector's Problem and Balls in Bins Variant

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.

• 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. – Gâteau-Gallois Dec 2 '18 at 10:57
• 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$. – Gâteau-Gallois Dec 2 '18 at 11:13
• I'm interested in the closed form of $f$. – Hang Wu Dec 2 '18 at 11:24