Coupon Collector's Problem with delayed replacement

Question

I have a set of 28 items (coupons) that are picked one at a time with replacement, but the same coupon is never picked twice in a row. In effect, a coupon is not replaced immediately — each coupon is replaced after the next one is picked. What is the expected number of picks? How can this be conceptualized?

Details: My computer app displays a set of eight (yellow) dots arranged in a circle, with another (blue) dot that moves randomly between them, tracing paths as it goes. The moving dot will never return back along the same path it just took (although it could traverse that path again later, in either direction). This eliminates some wasted movements and reduces the average number of traversals required. I want to know how many movements, on average, there will be before all 28 paths are traversed.

Without my restriction, the expectation is 110 traversals. With my restriction, I find the average (empirically) to be about 100.

Answer 1

If it were simply 28 items, replaced after one step, I think the expected number of steps is $1+27H_{27}\approx106$.

I had a go at your problem, but with 4 dots and 6 paths instead of 8 and 28, and got $345/32$ steps. I think you have to worry exactly which edges have been traveled, and what was the latest step. So it is more complicated than just how many edges have been traveled.

From now on, just consider how long an edge is delayed before it can appear again; and use Ross' arguments.

No edge is the same as the next one, nor the one after that. The second edge goes to a third vertex, so the third edge is not the same as the first. You might expect $2+\sum\frac{n-2}{n-k}$, which for 28 edges gives $2+26H_{26}\approx 102.2$ steps.

If the first edge is AB, then the fourth edge can be AB in the same direction, but not BA. So it is only half as likely to be the fourth edge. Perhaps, having gone from $28H_{28}$ to $1+27H_{27}$ to $2+26H_{26}$ it is now "$2.5+25.5H_{25.5}$" whatever that means. Interpolating halfway between $2+26H_{26}$ and $3+25H_{25}$ gives a value around $100.3$, which is what was observed.

Answer 2

Let us do it for $n$ coupons. Recall that in the usual case after you have drawn $k$ distinct coupons you have $\frac {n-k}n$ chance of drawing a new one, so on average it takes $\frac n{n-k}$ draws to get the next new one. We need to replace this formula with one that reflects your new drawing procedure. The first draw always gets you a coupon. The draw after you get the $k^{th}$ new one you are drawing from $n-k$ new ones and $k-1$ old ones, so the chance you get a new one is $\frac {n-k}{n-1}$. Draws after that you have again drawn an old one, so you again have $\frac {n-k}{n-1}$ chance of getting a new one. The expected number of draws to get the next new one is then $\frac {n-1}{n-k}$. The expected time to get all $n$ is then $$1+\sum_{k=1}^{n-1} \frac {n-1}{n-k}=1+(n-1)H_{n-1}$$ where $H_{n-1}$ is the $n-1^{st}$ Harmonic number, about $\log (n-1)+\gamma$. For $n=28$ this is about $105.57$