How can I stop DiscreteMarkovProcess[] from relabeling vertices?

Question

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

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])}];

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]]}