I'm trying to find the expected time to cover all $N$ nodes on an undirected cycle graph, starting from a given node $k$. The probabilities of moving clockwise and anticlockwise are $\frac{1}{2}$ each.

Could you direct me to some entry-level texts/resources which would explain this problem?


1 Answer 1


This is example 11.1 in Markov Chains and Mixing Times by Levin, Peres, and Wilmer. The book is available online here.

  • $\begingroup$ Thank you, that's exactly what I needed. $\endgroup$
    – user73876
    Commented Apr 23, 2013 at 1:35

You must log in to answer this question.