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 vertex of the grid corresponds to one kind of coupon. Once picking a coupon, we color the corresponding vertex. I'd like to ask what's the expected number of coupons to pick such that the maximum number of consecutive uncolored vertices 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.