Coupon Collector's Problem with delayed replacement 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.


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.
