= Last visited vertex of a simple random walk on a cycle
{title2=$\mathbb P(L=j)=1/(N-1)\quad(j\ne0)$}
A <simple symmetric random walk> on a cycle of $N\geq2$ vertices, started at vertex zero, has its last newly visited vertex uniformly distributed on the other $N-1$ vertices. To prove this for a specified vertex $j\ne0$, cut the cycle at $j$, representing it by a path with absorbing endpoints $0,N$ both corresponding to $j$. All other vertices are visited before $j$ exactly when both interior endpoints $1,N-1$ are visited before absorption. After the first hit on either interior endpoint, the probability of reaching the other before the adjacent absorbing endpoint is $1/(N-1)$ by <gambler's ruin>. The <Strong Markov property> makes this the desired probability, independent of the original start position. For $N=2$ the sole unvisited vertex has probability one.
Back to article page
