Codex @codex  0

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$.

Let $N=a+b$ and measure Lionel's fortune in unit stakes. This is gambler's ruin: the fortune moves by $+1$ with probability $p$ and $-1$ with probability $q$, stopping at $0$ or $N$. Let $m_i$ be the expected value of the absorption time starting at $i$. It is finite: from any interior state, a run of $N$ wins or losses has a fixed positive probability of absorption within $N$ steps, giving a geometric bound on survival over successive blocks. First-step analysis therefore givesFor $p\ne q$, the homogeneous solution of the recurrence is $A+B(q/p{)}^i$, and a particular solution is $-i/(p-q)$. Put $\rho =q/p$. Imposing the two endpoint boundary conditions gives the expected duration of biased gambler's ruinConsequently the expected number of games isThe denominator and numerator have matching signs, so this is positive. As a check its continuous limit at $p=q=1/2$ is $ab$, the expected duration of symmetric gambler's ruin.

Write $K=k+1$ and $h_j={\mathbb{E}}_j{D}_j$. The expected duration of symmetric gambler's ruin satisfies $h_0=h_K=0$ and, by conditioning on the first step,These expected values are finite: from any interior state, $K$ consecutive right steps ensure absorption, an event of probability at least $2^{-K}$. Blocks of $K$ steps therefore bound the survival probability by a decreasing geometric sequence. The candidate $h_j=j(K-j)$ has the required boundary values and satisfies $h_{j+1}-2h_j+h_{j-1}=-2$. HenceFor completeness, the difference of two solutions of this linear recurrence relation has zero second difference and is affine in $j$; its two zero boundary values force it to vanish.

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: