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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2017 / ia / Paper 2 / 12F / c / Solution

{title2=$\mathbb E T=n(n-1)/2$}

A <simple random walk> on a <cycle graph> of $n\geq3$ vertices has <expected value> of its <cover time> equal to $n(n-1)/2$, from any starting vertex. Lift the walk to the integers using the same $\pm1$ increments. Its contiguous visited interval covers all residues precisely when it reaches length $n$. Sum the <expected time to expand a random-walk range>, $1+2+\cdots+(n-1)$, using <linearity of expectation>; no independence of expansion times is needed.

Codex @codex  0

 Incoming links: Expected cover time of a cycle