A random walk on a circle with $n$ points. What is the probability that the walk will end at point $i$ ? ($0 \le i \le n-1$) [duplicate]

For a graph $G$, let $W$ be the (random) vertex occupied at the first time the random walk has visited every vertex. That is, $W$ is the last new vertex to be visited by the random walk. Prove the following remarkable fact:

For the random walk on an $n$-cycle, $W$ is uniformly distributed over all vertices different from the starting vertex.

Consider a simple symmetric random walk on the integer line starting from $0$ and, for some integers $-a\leqslant 0\leqslant b$ such that $(a,b)\ne(0,0)$, the event that the walk visits every vertex in $[-a,b]$ before visiting vertex $-a-1$ or vertex $b+1$. This is the disjoint union of two events:

• Event 1: Starting from $0$, the walk visits $b$ before visiting $-a$, then, starting from $b$, it visits $-a$ before visiting $b+1$,
• Event 2: Starting from $0$, the walk visits $-a$ before hitting $b$, then, starting from $-a$, it visits $b$ before hitting $-a-1$.

Recall that the probability that a simple symmetric random walk starting from $i$ visits $i-j\leqslant i$ before visiting $i+k\geqslant i$ is $\frac{k}{k+j}$, for every nonnegative integers $j$ and $k$.

Hence, the probability of Event 1 is $\frac{a}{a+b}\cdot\frac1{a+b+1}$, the probability of Event 2 is $\frac{b}{a+b}\cdot\frac1{a+b+1}$, and the probability of their union is $\frac1{a+b+1}$. Note that this last formula is also valid when $a=b=0$.

If $b=x-1$ and $a=n-x-1$ with $1\leqslant x\leqslant n-1$ and $n\geqslant2$, then $a+b+1=n-1$ hence the computation above shows that the probability that the last visited vertex in the discrete circle $\{0,1,\ldots,n-1\}$ is $x$ is $\frac1{a+b+1}=\frac1{n-1}$. That is, the probability of the event $[W=x]$ is $\frac1{n-1}$ for each $x\ne0$ in the circle, and $W$ is uniformly distributed on the circle minus the starting point of the random walk.

In order to reach $W$ last, the walk has to visit one of $W$'s neighbours for the last time and then go all around the cycle to arrive at $W$ from the other side. Let's call a segment of a random walk on the cycle that starts at some vertex $V$ and reaches one of $V$'s neighbours by going around the cycle without returning to $V$ a final segment. Then the last vertex reached after time $t$ is the final vertex of the first final segment that begins at or after $t$. Consider a random walk on the cycle, and for every final segment that ends at $W$, consider the stretch of times $t$ for which it is the first final segment that begins at or after $t$. If we can show that all vertices except $W$ occur with the same frequency in this stretch, then it will follow that conversely $W$ is reached last with the same probability from all other vertices, and thus all vertices $W$ are reached last with the same probability from a given initial vertex.

But the stretch extends precisely up to the last visit to $W$ before the segment, so the frequency of vertices in it is just that between any two successive visits to $W$, which is just the frequency of occurrence of the vertices other than $W$ in the walk in general, which is the same for all vertices.

P.S.: It's actually not too difficult to determine the probability of each vertex to be the last vertex visited at any stage in the process. The vertices already visited always form an interval. If the current position is at the end of an interval of $k$ visited vertices, every unvisited vertex has the same $1/(n-1)$ probability of becoming the last one, except the first unvisited vertex at the other end of the interval, which has $k/(n-1)$. This is because for all vertices except this one, exactly the same realizations of the walk will make them the last vertex as would be the case if no vertices had been visited yet. Thus, every vertex has a constant probability $1/(n-1)$ of ending up as the last vertex until the walk first visits one of its neighbours.

If the current position is in the interior of the interval of visited vertices, the probability of reaching one end of the interval before the other varies linearly over the interval, and thus so do the probabilities of the two unvisited vertices bordering the interval to become the last vertex – the sum of their probabilities is $(k+1)/(n-1)$, and this shifts by $1/(n-1)$ by each move, in favour of the vertex that the move moves away from.