Here is some statement from my textbook. Let $T$ be the time it takes for the random walk to reach $0$ or $N$, and let $$G(j)=E[T|\,X_0=j] = j(N-j),\quad j=1,\cdots,n-1 \qquad (1.18)$$ By (1.18), we have the expected time that it takes the random walk from the interior point(next to the boundary point) to reach a boundary is $k-3$. We therefore get the equation $$r(k) = 1+\frac{1}{2}[(k-3)+r(k)]$$ where $r(k)=E(T_k-T_{k-1})$ for $k=3,\cdots,N$ and $T_k$ denotes the first time at which the number of distincte points visited equals $k$.
I have a question at the bottom of the page. Why the expected time is $k-3$ and how do we get the recurrence?
The Equation (1.18) gives the expected time to reach either node 0 or node $N$ (either end of $N+1$ total nodes). In the simple random walk on the circle, at time $T_{k-1}$ we have $k-1$ visited points, so $N=k-2$, and when we move to the first interior point $j=1$, so $j(N-j)=k-3$
So if the expected number of steps to reach a new point is $r(k)$, we have that $r(k)= \frac{1}{2}(1)+\frac{1}{2}\left( 1 + (k-3) + r(k)\right)$
The $\frac{1}{2}(1)$ is from the probability of reaching the new point in one step, and the $\frac{1}{2}\left( 1 + (k-3) + r(k)\right)$ is from the probability of taking one step to an interior point, then an average of $(k-3)$ steps to the edge again, then an average of $r(k)$ steps to a new point.