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?

enter image description here

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}} *)
  • $\begingroup$ @BoLe: It appears that for all positive integers $m$, the expected number of steps required to visit all nodes is exactly $\binom {m+1}{2}$. I've verified this for $1 \le m \le 50$. $\endgroup$
    – quasi
    Jul 20, 2017 at 13:58
  • $\begingroup$ A simulation tends to indicate all the nodes have the same probability to be the last visited one, except for the starting node 0, which has probability 1 when m=0 (one node) and probability when m>0 (more than one node). This result is obvious when m=1 (two node) where the last visited node is always the non starting one. And when m=2 (three nodes) the last visited node is any of the two non starting node with equal probability. $\endgroup$
    – AlainD
    Jul 20, 2017 at 14:17
  • $\begingroup$ @AlainD: The OP is using the same setup as in the exercise, but is asking a different question. $\endgroup$
    – quasi
    Jul 20, 2017 at 14:19
  • $\begingroup$ @quasi It seems you're right. Did you verify this by simulating the system, similarly to what I did? $\endgroup$
    – BoLe
    Jul 20, 2017 at 16:47
  • $\begingroup$ @BoLe: No, I computed the expected values exactly via recursion (using a computer program to solve based on the recursive relationships). $\endgroup$
    – quasi
    Jul 20, 2017 at 16:54

2 Answers 2


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.

  • $\begingroup$ This is just what I needed. Thinking about the visitation process in stages eases the way to the solution. Formally, I changed the notation to random variables: $X$, number of moves needed to visit all nodes; $X_k$, having visited $k$ unique nodes and with the cursor at one of the two edge nodes, the number of moves needed to advance to the next level, with $k+1$ visited nodes. I solved the difference equation in the answer by solving a system of equations with tridiagonal matrix. $\endgroup$
    – BoLe
    Jul 23, 2017 at 11:15

As requested, here's the Maple program I wrote to compute, for a given value of $m$, the expected number of steps required to visit all nodes other than the starting node. enter image description here enter image description here


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .