Circular random walk coupon collector's problem for large numbers of coupons

Question

I need to know if there is a formula or asymptotic approximation for the following coupon collector's problem involving very large numbers of coupons.

1. Coupons are arranged in a circle
2. It doesn't matter which coupon is collected first
3. Coupon exploration is by random walk, one step at a time, either clockwise or counter-clockwise i.e., $\pm1$ step from the current position
4. You collect a coupon the first time that you visit its location
5. Exploration stops only after collecting all coupons

I don't get a simple curve that fits Monte Carlo results up to 300 coupons, and Monte Carlo trials are out of the question when it comes to large numbers like $10^{30}$ coupons. An asymptotic lower bound would be OK.

Answer 1

• It is well known that with a simple random walk starting at $0$, the expected number of steps to reach the first of the positions $-a$ and $+b$ is $ab$.
• So in your circle, as soon as you have collected the $k$th coupon, the expected number of steps to reach the $k+1$th coupon you will collect is $k$.
• So the total expected number of steps to collect all $n$ coupons in the circle is $1+2+\cdots +(n-1)= \frac12n(n-1)$.

As a check for very small $n$,

1. for $n=1$ this gives $0$ corresponding to a single coupon which you collect at the start before moving;
2. for $n=2$ this gives $1$ corresponding to you starting with the initial coupon and finishing with the other coupon after a single step in either direction;
3. for $n=3$ this gives $3$ which calculated another way would be $2 \times \frac12+3\times \frac14+4 \times \frac18 +5\times \frac1{16}+\cdots$.