Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
    
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[]"? –  Jerome Apr 29 '13 at 12:09
add comment

1 Answer

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

share|improve this answer
    
If you try to take a subgraph of $G$ and then generate the Markov process, the vertex labels stop matching up... –  Peter Apr 30 '13 at 0:49
    
@Peter you can initiate the subgraph by assigning zero transition probability to all the complimentary edges in $G/S$ –  PlatoManiac Apr 30 '13 at 8:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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