I extended the example below (from Ross: Introduction to Probability Models, p. 84) to the following question:
What is the expected number of steps before all nodes have been visited?
I can determine the expectations in the first two nontrivial cases (m = 2, m = 3, with results 3 and 35/6 respectively) by traversing the probability tree and solving some equations. I don't think I can use this approach for higher m's. Maybe programatically with Mathematica. Is there some other technique? How would you try and solve this?
Mathematica code below approximates the expectations for m = 2...10:
sim[m_] := NestWhileList[
Mod[RandomChoice[# + {1, -1}], m + 1] &, 0, Union[{##}] != Range[0, m] &, All]
With[{k = 1000, n = 10},
Table[{m, Table[Length[sim[m]] - 1, k] // Mean // N}, {m, 2, n}]]
(* {{2, 2.999}, {3, 6.007}, {4, 9.994}, {5, 14.953}, {6, 21.18},
{7, 27.07}, {8, 34.993}, {9, 44.029}, {10, 55.108}} *)
The solution is essentially the same as has been implemented, but with a slight reformulation it can be broken up into smaller problems.
At any time, the particle has visited a given number of points, let's say $k$ points, and is located at one of those $k$ points. Let's enumerate those $k$ points $1,\ldots,k$ from one end to the other (not the enumeration $0,\ldots,m$ used in the original problem formulation). We say that the particle is in a state $S_{k,i}$ if it has visited a total of $k$ points and is presently in point $i\in\{1,\ldots,k\}$. It starts in state $S_{1,1}$ at time $0$.
In each step, it may move to either side with likelihood $1/2$: from $S_{k,i}$ to either $S_{k,i-1}$ or $S_{k,i+1}$, except that if it goes to $S_{k,0}$ or $S_{k,k+1}$ it immediately moves to $S_{k+1,1}$ or $S_{k+1,k+1}$ respectfully.
We may now analyse the movements within level $k$. Let $T_{k,i}$ denote the expected time until it moves to level $k+1$. This corresponds to moving to position $i=0$ or $i=k+1$. The expected time follows the relation $$T_{k,i}=1+\frac{T_{k,i-1}+T_{k,i+1}}{2}$$ where we set $T_{k,0}=T_{k,k+1}=0$. The solution to this difference equation is $T_{k,i}=i(k+1-i)$.
When you first enter level $k$, you enter at $S_{k,1}$ or $S_{k,k}$, and the expected time to move on to level $k+1$ is then $T_{k,1}$ or $T_{k,k}$ which are both $k$.
The problem is to start at level $1$, and arrive at level $m+1$ where all $m+1$ points have been visited. This then takes $1+2+\cdots+m=m(m+1)/2$ steps.