= Solution
The vertices visited by a <simple symmetric random walk> form an integer interval: nearest-neighbour steps cannot skip a vertex. At the <stopping time> $T_k$, write that interval as $[\ell,r]$, with $r-\ell+1=k$. The walk is at one of its endpoints, because the $k$th new vertex must extend the earlier interval. This also covers $k=1$, when both endpoints coincide.
The <Strong Markov property> restarts the walk from this endpoint. Visiting a new vertex is exactly exiting $[\ell,r]$, or reaching $\ell-1$ or $r+1$. Translate these absorbing boundaries to $0,k+1$. The starting point becomes either $1$ or $k$, so the <expected duration of symmetric gambler's ruin> is $k$ in both cases. Taking <conditional expectations> and then <expected values> gives the <expected time to expand a random-walk range>:
$$
\boxed{\mathbb E[T_{k+1}-T_k]=k.}
$$
Back to article page
