Probability of terminating in a state in a probabilistic algorithm

Question

Suppose i have a circular array of $n$ elements. At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves left from 0 it goes to position $n$). When i visited all the positions at least once the algorithm returns the position it terminated into.
Launching the algorithms many times shows that it stops with the same probability in any of the n positions (except for zero obviously). How do i demonstrate that the probability of ending up in each state is uniform?
My understanding is that this process is explained by a doubly stochastic Markov chain, but is there a theorem i can quote about this specific case?

Answer 1

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a move to $b$. When $a=b=0$, we arbitrarily define $\ell(0,0) = 1$ and $r(0,0) = 0$.

If we are at the situation counted by $\ell(a,b)$, then known formulas show that we move to the situation counted by $\ell(a-1,b)$ with probability $1-1/(b-a+2)$, and to the situation counted by $r(a,b+1)$ with probability $1/(b-a+2)$. Together with an analogous argument for $r(a,b)$, this gives the recurrences $$ \ell(a,b) = \left(1 - \frac{1}{b-a+1}\right) \ell(a+1,b) + \frac{1}{b-a+1} r(a+1,b), \\ r(a,b) = \frac{1}{b-a+1} \ell(a,b-1) + \left(1 - \frac{1}{b-a+1}\right) r(a,b-1). $$ We want to show that for $i=1,\ldots,n-1$, $$ r(i-n+1,i) + \ell(i-n,i-1) = \frac{1}{n-1}. $$ We will prove the stronger result $$ r(i-n+1,i) = \frac{i}{n(n-1)}, \\ \ell(i-n,i-1) = \frac{n-i}{n(n-1)}. $$ When $n=2$, we need to show $$ r(0,1) = \ell(-1,0) = \frac{1}{2}, $$ which can be checked directly. For $n > 2$, we have $$ r(i-n+1,i) = \frac{1}{n} \ell(i-n+1,i-1) + \frac{n-1}{n} r(i-n+1,i-1) = \\ \frac{1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{n-1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{i}{n(n-1)}, $$ and similarly $$ \ell(i-n,i-1) = \frac{n-1}{n} \ell(i-n+1,i-1) + \frac{1}{n} r(i-n+1,i-1) = \\ \frac{n-1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{n-i}{n(n-1)}. $$ (We don't really need to calculate the two cases separately, since symmetry arguments show that $r(i-n+1,i) = \ell(-i,n-i-1)$.)