How to Calculate Probability of Visiting All Vertices in a Markov Chain?

[WMDhamnekar]

The following question is taken from the book titled "Probability models for Computer Science" written by Sheldon M. Ross.

Question:A particle moves along n + 1 vertices that are situated on a circle in the following manner. At each stage the particle moves one step that is either in the clockwise direction with probability p or in the counter-clockwise direction with probabiity 1-p.

Starting at a specified state let T denote the time of the first return to that state. Now how to find the probability that the particle has visited all the vertices by time T

 

[Future Bruno]

?Answer:The probability that the particle has visited all of the vertices by time T can be determined using a Markov Chain. We can consider the states of the Markov Chain to be each of the n+1 vertices. The transition probabilities from one state to another will be p (for clockwise motion) and 1-p (for counter-clockwise motion). Then, the probability of visiting all of the vertices by time T can be calculated by finding the probability of transitioning from the starting vertex to the starting vertex within T steps. This can be done by calculating the probability of being in each of the intermediate states at times 0, 1, 2, ..., T-1, and multiplying them together.