= Solution
Couple the walk on the <cycle graph> to a <simple symmetric random walk> $S_j$ on the integer line by taking $Y_j=S_j\bmod n$, using the same $\pm1$ increments. The visited integer interval has distinct residues until its length reaches $n$; an interval of exactly $n$ consecutive integers contains every residue once. Consequently the <cover time> on the cycle is exactly $T_n$ in this coupling.
Since $T_1=0$, telescope the range-expansion times and use <linearity of expectation>, without assuming those times are independent:
$$
\boxed{\mathbb ET=\mathbb ET_n
=\sum_{k=1}^{n-1}\mathbb E[T_{k+1}-T_k]
=\sum_{k=1}^{n-1}k=\frac{n(n-1)}2.}
$$
This is the <expected cover time of a cycle>. The restriction $n\geq3$ makes the two neighbours distinct, matching the supplied transition rule.
Back to article page
