A generalization of coupon collector's problem: take an adjacent pair each time.

Question

We have $n$ distinct kinds of coupons (of unlimited supply), the categories are denoted $1\dots n$.Each time we could draw two coupons, but the two must be of adjacent kind (it could be any of $\{(1,2),(2,3)...,(n-1,n),(n,1)\}$, the probability of drawing any pair is equal). What is the expected number of draws before collecting all $n$ distinct coupons?

Some progress: This is different than just drawing two coupons with replacement randomly, where I already know a formula. And the "pattern" of selecting does not matter, this means drawing $\{(1,3),(2,4)...,(n-1,1),(n,2)\}$ yields the same result.

Answer 1

Here is a formula. My fault, I should have realized this problem being equivalent to Project Euler 645, which I have solved earlier. $$E(n)=1-n\sum_{i=1}^{n-1}\frac{1}{i}\left((-1)^i\binom{n-1}{i}+\frac{\binom{n-i}{i}}{\binom{n-1}{i}}\right)$$ I am now working on the case when a draw includes more than 2 coupons.

Answer 2

(After the answer of @mayoi, this approach is surpassed, however I am putting it just to show a Markovian approach).

Suppose that, upon turn $t$, you have acquired $m$ coupon out the $n$ avalaible.
Suppose also, for the moment, that the acquired coupon are in succession $\{1,2, \cdots,m \}$.

Now,
- if you get coupons $(m,m+1)$ or $(n,1)$ you increase by one the amount collected;
- if you get coupons $(m+1,m+2), \cdots (n-1,n)$ you increase by two the amount collected;
- in any other case you remain with the collected amount;

Case 1 corresponds to $2$ extractions, case 2 to $n-m-1$ extractions and case 3 gives the remaining $m-1$ extractions of the total $n$.
When $m=0$ we have $0,n,0$, while if it were $m=1$ (but it cannot occur) we would have $2, n-2,0$, then when $m=n-1$ we have $[2,0,n-2]$ and for $n=m$ it is $[0,0,n]$.

Because of symmetry, it is easy to deduce that the above counting holds whichever type are the $m$ coupon collected.

Therefore the transition matrix for the number of coupons collected, indexed $[0,n] \times [0,n]$, is $$ \eqalign{ & T_{\,m,\,q} \quad \left| {\;0 \le m,q \le n} \right.\quad = \cr & = \left[ {0 = n} \right] + {{\left[ {1 \le n} \right]} \over n}\left( {\left( {m - \left[ {m < n} \right]} \right)\left[ {1 \le m} \right]\left[ {q = m} \right] + 2\left[ {1 \le m} \right]\left[ {q = m + 1} \right] + \left( {n - m - \left[ {1 \le m} \right]} \right)\left[ {q = m + 2} \right]} \right) \cr} $$

where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

For example, for $n=4,5$ the matrices are $$ \eqalign{ & {\bf T}_{\,4} = \left( {\matrix{ 0 & 0 & 1 & 0 & 0 \cr 0 & 0 & {1/2} & {1/2} & 0 \cr 0 & 0 & {1/4} & {1/2} & {1/4} \cr 0 & 0 & 0 & {1/2} & {1/2} \cr 0 & 0 & 0 & 0 & 1 \cr } } \right) \cr & {\bf T}_{\,5} = \left( {\matrix{ 0 & 0 & 1 & 0 & 0 & 0 \cr 0 & 0 & {2/5} & {3/5} & 0 & 0 \cr 0 & 0 & {1/5} & {2/5} & {2/5} & 0 \cr 0 & 0 & 0 & {2/5} & {2/5} & {1/5} \cr 0 & 0 & 0 & 0 & {3/5} & {2/5} \cr 0 & 0 & 0 & 0 & 0 & 1 \cr } } \right) \cr} $$

The matrix exhibits an interesting symmetry.
Its eigenvalues follows a regular path $\left\{ {{k \over h}\quad \left| {\;0 \le k \ne h - 1 \le h} \right.} \right\}$ (for $2 \le h$), with the null value being double. The matrix is diagonalizable, and we can apply the Markov theory to get various interesting parameters.