# How can I stop DiscreteMarkovProcess[] from relabeling vertices?

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];
Print[Mean[FirstPassageTimeDistribution[DMPG,2]]


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[]?

• 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[]"? Apr 29, 2013 at 12:09

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];
MapThread[(#1 /.UndirectedEdge[i_,j_] :> (g[[i, j]] = g[[j, i]] = #2;)) &,
{EdgeList[G],list = RandomReal[{0, 1}, Length@EdgeList[G]];(list/Total[list])}]; 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"] 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]]}

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