1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy