I'm attempting to calculate the mean first passage time between two vertices, $v_1$ and $v_2$, provided some undirected graph $G$. However, I noticed that running the following script:

DMPG = DiscreteMarkovProcess[1, G];

Returns a value for the mean first passage time between $v_1$ and some $v_i$ (instead of the desired $v_2$) due to a vertex name reassignment by DiscreteMarkovProcess[]. How can I stop this, or find the mapping between vertices in $G$ and nodes in the Markov chain generated by DiscreteMarkovProcess[]?

  • $\begingroup$ Can you describe how your problem differs from the first example given [here] (reference.wolfram.com/mathematica/ref/…) . What do you mean by "a vertex name reassignment by DiscreteMarkovProcess[]"? $\endgroup$
    – jerome
    Commented Apr 29, 2013 at 12:09

1 Answer 1


First, I am not a specialist on probability theory and random processes! I will try to address your question from the very limited knowledge I got from the Mathematica documentation. The documentation for DiscreteMarkovProcess tells the following

"A discrete Markov process can be seen as a random walk on a graph, where the probability of transitioning from state $i$ to state $j$ is specified by m[[i,j]]."

So I first take a random graph and extract the AdjacencyMatrix and randomly assign some probability to the edges.

G = RandomGraph[{18, 19}, VertexLabels -> "Name", ImagePadding -> 12];
g = AdjacencyMatrix[G];
MapThread[(#1 /.UndirectedEdge[i_,j_] :> (g[[i, j]] = g[[j, i]] = #2;)) &,
{EdgeList[G],list = RandomReal[{0, 1}, Length@EdgeList[G]];(list/Total[list])}];

enter image description here

Now I suppose we get a meaningful Mean here

DMPG = DiscreteMarkovProcess[1, g];
dist = FirstPassageTimeDistribution[DMPG, 2];
{Mean[dist], Variance[dist]} // N

{33.8978, 755.914}

Lets look at the layered picture of the Markov process.

gr = Graph[DMPG, GraphLayout -> "LayeredDrawing"]

enter image description here

Note: If you try to find passage time between $v_1$ and some $v_i$ where $v_i$ is not connected to $v_1$ Mathematica will return the following without any warning or error! Here due to the underlying graph topology no transition is possible from state $1$ to state $12$.

dist = FirstPassageTimeDistribution[DMPG, 12];
{Mean[dist], Variance[dist]} // N

{Mean[FirstPassageTimeDistribution[DiscreteMarkovProcess[1,SparseArray[<40>,{18,18}]],12]], Variance[FirstPassageTimeDistribution[DiscreteMarkovProcess[1,SparseArray[<40>,{18,18}]],12]]}

  • $\begingroup$ If you try to take a subgraph of $G$ and then generate the Markov process, the vertex labels stop matching up... $\endgroup$
    – Peter
    Commented Apr 30, 2013 at 0:49
  • $\begingroup$ @Peter you can initiate the subgraph by assigning zero transition probability to all the complimentary edges in $G/S$ $\endgroup$ Commented Apr 30, 2013 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.