A simple symmetric random walk on a cycle of vertices, started at vertex zero, has its last newly visited vertex uniformly distributed on the other vertices. To prove this for a specified vertex , cut the cycle at , representing it by a path with absorbing endpoints both corresponding to . All other vertices are visited before exactly when both interior endpoints are visited before absorption. After the first hit on either interior endpoint, the probability of reaching the other before the adjacent absorbing endpoint is by gambler's ruin. The Strong Markov property makes this the desired probability, independent of the original start position. For the sole unvisited vertex has probability one.
Articles by others on the same topic
There are currently no matching articles.