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.
Articles by others on the same topic
There are currently no matching articles.