Probability of terminating in a state in a probabilistic algorithm
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 &gt; 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)$.)