I'm having a little trouble understanding part of an example in Lawler's Intro to Stochastic Processes ("Simple Random Walk on a Circle" example on page 32). The problem is the following:
Suppose $\{X_n, n \geq 0 \}$ is a simple random walk on a cycle (or "clique", as in graph theory) of length $N$. Compute the expected number of steps the process takes to hit every vertex.
I'll go through the main parts of his solution and point out which part is causing my confusion.
Let $T_k$ be the time at which the random walk has hit $k$ distinct vertices (so, $T_1 = 0$ and $T_2 = 1$ a.s.). We compute the quantity
$$
r(k):= \mathbb{E} (T_k – T_{k-1}), \hspace{5mm} 3 \leq k \leq N
$$
Observe that at time $T_{k-1}$, the walk has reached the $(k-1)^{\text{th}}$ distinct vertext, and will either hit a new vertex or return to its other neighbor (a vertex that has already been visited). Now, applying the result of the gambler's ruin problem,
$$ r(k) = 1+\frac{1}{2} \Big( (k-3) +r(k) \Big)$$
Hence, $r(k) = k-1$, and
$$
\mathbb{E}(T_N) = 1+ \sum_{n = 3}^{N} r(k) = \frac{N(N-1)}{2}
$$
I understand that the $(k-3)$ in the above blockquote comes from a direct application of the gambler's ruin problem (expected time until absorption for a simple random walk with absorbing boundaries), but I'm having a hard time convincing myself why this formula for $r(k)$ is valid. I'd appreciate any help.
Best Answer
At the moment $T_{k-1}$ we are on a boundary of non-visited and visited points. Now what Lawler$^*$ says is that there are two possibilities (both having probability $1/2$):
We step into the non-visited area. Then we have $T_{k} - T_{k-1} = 1$.
We step back into the visited area. Then $$ T_{k} - T_{k-1} = 1+ \text{time to reach the boundary again} \\+ \text{time to visit a new vertex from the boundary}. $$ The first time is distributed as in gambler ruin problem with $N = k-2$ and $j=1$, hence $k-3$. The second has the same distribution as $T_k - T_{k-1}$.
Hence follows the required recursion.
However, it is possible to give a much easier argument. $T_{k} - T_{k-1}$ is like gambler's ruin problem with $N = k$ and $j=1$, therefore, $$ r(k) = E(T_k - T_{k-1}) = k-1. $$
$^*$ I hope it was rather one of Lawler's students, who wrote this solution for him.