Expected cover time of a cycle

ID: expected-cover-time-of-a-cycle

A simple random walk on a cycle graph of vertices has expected value of its cover time equal to , from any starting vertex. Lift the walk to the integers using the same increments. Its contiguous visited interval covers all residues precisely when it reaches length . Sum the expected time to expand a random-walk range, , using linearity of expectation; no independence of expansion times is needed.

New to topics? Read the docs here!