# DiscreteMarkovProcess: labelling of states

Related, but it seems like the respondents there misunderstood the question.

The following errors as DiscreteMarkovProcess::invsm:

p = DiscreteMarkovProcess[10, Graph[{10, 11}, {10 \[DirectedEdge] 11}]];

RandomFunction[p, {0, 5}]


If we simply change 10, 11 to 1, 2, it works without issue:

q = DiscreteMarkovProcess[1, Graph[{1, 2}, {1 \[DirectedEdge] 2}]];

RandomFunction[q, {0, 5}]


The problem appears to be that DiscreteMarkovProcess has relabeled the vertices of the graph to 1 and 2, since:

p2 = DiscreteMarkovProcess[1, Graph[{10, 11}, {10 \[DirectedEdge] 11}]];
RandomFunction[p2, {0, 5}]


works as q did (the only change from p is the first argument to DiscreteMarkovProcess). This should not happen in any reasonable interpretation that I can see.

Is there a way to make Mathematica work with the vertex names I have provided (without relabelling them 1, 2, …), or else of recovering the mapping 10 -> 1, 11 -> 2 which it turns out Mathematica has applied above?

• There is no state naming in MMA Markov Procs. The first fails because you're saying "start in state 10", when there is no such thing in your case. Changing the first parameter to 1 fixes that. States returned will be the Markov state labels, so just build a simple replace rule to translate them to your desired domain.
– ciao
Jul 20, 2015 at 19:30
• But I asked the Markov chain to operate on a particular state-transition graph - namely, one with vertex names 10 and 11. Is it not really weird that it relabels them to 1 and 2? I should note that this behaviour appears to be undocumented and highly counterintuitive. Jul 20, 2015 at 19:35
• @PatrickStevens The second example in the docs for MarkovProcessProperties[ ] shows you how to manually cope with that. Many graph functions in Mma share this idiosyncrasy. (Not that I'm pleased with it) Jul 20, 2015 at 19:47
• The Details section states (among other things): "The states of DiscreteMarkovProcess are integers between 1 and n, where n is the length of transition matrix m." and "The transition matrix in the case of a graph g is constructed to give equal probability of transitioning to each incident vertex.". From this it can be concluded that graphs are converted to n x n transition matrices and that vertex labels, which can be anything, will not be used. I assume that the position of a label in the VertexList determines the Markov state with which it will be identified. Jul 20, 2015 at 19:48
• To accommodate your wishes one could do the following (assuming the graph is assigned to g): MapIndexed[(state[#1] = #2[[1]]) &, VertexList[g]] . This defines a function state that turn a label into a state number. Jul 20, 2015 at 20:03

The Details section of the DiscreteMarkovProcess documentaion states (among other things):

The states of DiscreteMarkovProcess are integers between 1 and n, where n is the length of transition matrix m.

and

The transition matrix in the case of a graph g is constructed to give equal probability of transitioning to each incident vertex.

From this it can be concluded that graphs are converted to n x n transition matrices and that vertex labels, which can be anything, will not be used. The position of a label in the VertexList determines the Markov state with which it will be identified.

You can keep using labels if you introduce helper functions state and label as follows:

Example graph:

g = Graph[{"pipo" -> "qwe", "qwe" -> "ape" , "ape" -> "pipo" ,
"ape" -> "nut"}, VertexLabels -> "Name"]


ClearAll[state, label]
MapIndexed[(state[#1] = #2[[1]]) &, VertexList[g]];
MapIndexed[(label[#2[[1]]] = #1) &, VertexList[g]];


Markov process starting at state "pipo":

p = DiscreteMarkovProcess[state["pipo"], g];


Show simulation states:

label /@ RandomFunction[p, {0, 5}]["Values"]


{"pipo", "qwe", "ape", "nut", "nut", "nut"}

Apparently I failed to read the docs, although it would be extremely helpful if this were in "Possible Issues" rather than "Details". DiscreteMarkovProcess does not support labelled state names, and converts them all to integers in the range 1…n. That is, if initialised from a graph, DiscreteMarkovProcess forgets all the graph structure except the form of the adjacency matrix. As best as I can tell, Mathematica assigns integers 1…n to the input graph in the order the vertices are supplied to Graph:

p = DiscreteMarkovProcess[1, Graph[{11, 10}, {11 \[DirectedEdge] 10}]];
RandomFunction[p, {0, 5}]["Values"]


returns {1, 2, 2, 2, 2, 2}, indicating that the chain has absorbed in what Mathematica calls "state 2" - that is, state 10. By contrast,

p = DiscreteMarkovProcess[1, Graph[{10, 11}, {11 \[DirectedEdge] 10}]];
RandomFunction[p, {0, 5}]["Values"]


returns {1, 1, 1, 1, 1, 1}, so it has absorbed in what Mathematica calls "state 1" - that is, state 10 again.

In the case that no vertex-list is supplied to Graph, it again uses the order in which vertices appear:

p = DiscreteMarkovProcess[3, Graph[{9 \[DirectedEdge] 5, 11 \[DirectedEdge] 10}];
RandomFunction[p, {0, 5}]["Values"]


returns {4, 4, 4, 4, 4, 4}, so it has absorbed in what Mathematica calls "state 4" - that is, state 10 again.