= Expected time to expand a random-walk range
{title2=$\mathbb E[T_{k+1}-T_k]=k$}
For a <simple symmetric random walk> on the integers, let $T_k$ be the first time that $k$ distinct vertices have been visited. The visited set is an interval, and at $T_k$ the walk is at an endpoint. The <Strong Markov property> turns the time to add one vertex into <gambler's ruin> between the two immediately exterior vertices, starting one step from a boundary. The <expected duration of symmetric gambler's ruin> is therefore $k$. This also holds at $k=1$.
Back to article page
