= Expected cover time of a cycle
{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.
Back to article page
