Expected number of steps needed until every point is visited in bounded simple symmetric random walk?

Question

I was wondering how to calculate this. Say the state-space is $\{1, \dots, N \}$. Would it be correct to calculate the expected value of the first hitting time of $N$ starting from $1$ by using the coupon's collector formula?

Answer 1

Let $e_k$ be the expected number of steps to reach state $N$ if we are currently in state $k$. Then $$e_k = 1+\frac12(e_{k-1}+e_{k+1})\tag1$$ because we take one step and then with probability $\frac12$ we need $e_{k-1}$ more steps on average, and with probability $\frac12$ we need $e_{k+1}$ more steps on average. We have the boundary condition $e_N=0$.

We can rewrite $(1)$ as $$e_{k+1}-2e_k+e_{k-1}=-2$$ which has characteristic equation $$r^2-2r+1=0$$ which has $1$ as a double root. Therefore, the general solution to the homogeneous equation is $e_k=a$ for a constant $a$.

Now we must find a particular solution to $(1)$. From the form of the equation,, we guess that a quadratic polynomial will work, and we quickly find that $e_k=-k^2$ is a solution. The general solution to $(1)$ is the general solution to the associated homogeneous equation, plus any particular solution to the inhomogeneous equation, so the general solution is $$e_k=a-k^2$$ Substituting the boundary condition, we find $a=N^2$ so that $e_k=K^2-k^2$ and the expected number of steps starting in state $1$ is $$e_1=\boxed{N^2-1}$$

Observe that this is nothing like the answer for the coupon collector's problem. The two problems have nothing in common except that the absorbing state is state $N$.