3
$\begingroup$

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}} *)
$\endgroup$
10
  • $\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

2
$\begingroup$

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.

$\endgroup$
1
  • $\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
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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