1
$\begingroup$

Context: The code below produces the graph of a Markov chain with the transition probabilities shown on each edge. If I chose any vertex to start from, say vertex 1, I would then like the graph of all 2 steps through the Markov chain to be drawn along with the vertex labels shown. The graph would look like a tree diagram, with the root node (top node) being labeled 1, for instance.

g = DiscreteMarkovProcess[{1, 0, 0, 0}, {{0, 1/2, 0, 1/2}, {1/3, 0, 1/3, 1/3}, {0, 1/2, 0, 1/2}, {1/3, 1/3, 1/3, 0}}];
Graph[g, VertexStyle -> {1 -> Yellow, 2 -> Yellow, 3 -> Yellow, 4 -> Yellow}, EdgeLabels -> {DirectedEdge[i_, j_] :> MarkovProcessProperties[g, "TransitionMatrix"][[i, j]]}]

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Frankly, I still don't get what you want. Very likely that's why you got no answer. I withdrew my close vote and deleted my comment after your initial edit, but it's still not a well-phrased question. What you need is not a bounty but a clear explanation. $\endgroup$ – Szabolcs Dec 29 '18 at 7:37
5
+50
$\begingroup$

This is an update after the OP clarified what they meant (old answer below):

step[_, _, 0] := {}
step[T_, p : (_ -> i_), n_] := Flatten@Table[
   If[T[[i, j]] > 0,
    {
     Property[p -> (p -> j), EdgeLabels -> T[[i, j]]],
     step[T, p -> j, n - 1]
     },
    Nothing
    ],
   {j, Length@T}
   ]

Graph[
 step[MarkovProcessProperties[g, "TransitionMatrix"], Begin -> 1, 2],
 VertexStyle -> Yellow,
 VertexSize -> 0.3,
 VertexLabels -> {(_ -> j_) :> Placed[j, {1/2, 1/2}]}
 ]

enter image description here

How this works

The step function recursively builds a list of edges. It gets 3 arguments:

  • The transition matrix $T$
  • The path to the current vertex (we pass along the full path to ensure that e.g. 1->3->1 and 1 are distinct vertices)
  • The number of remaining steps

At each step, we create new edges corresponding to all non-zero entries of $T$, and call step again with the new vertex and n-1. At the end, we simply create a graph from the list of edges, where we use only the last part of the path as vertex label. The initial vertex is specified as Begin->1 to ensure that it matches the pattern _->i_.

Old answer

You can easily compute the transition probabilities for an $n$-step process using $T^n$, where $T$ is the transition matrix and $\square^\square$ denotes MatrixPower:

g2 = DiscreteMarkovProcess[
   {1, 0, 0, 0},
   MatrixPower[MarkovProcessProperties[g, "TransitionMatrix"], 2]
   ];
Graph[
 g2,
 VertexStyle -> {1 -> Yellow, 2 -> Yellow, 3 -> Yellow, 4 -> Yellow},
 EdgeLabels -> {
   DirectedEdge[i_, j_] :> MarkovProcessProperties[g2, "TransitionMatrix"][[i, j]]
   }
 ]

enter image description here

In this new Markov process represented by the graph above, a single step corresponds to exactly two steps in the original process. From here, it is straightforward to get the representation you want:

g3 = WeightedAdjacencyGraph[
   MarkovProcessProperties[g2, "InitialProbabilities"]*MarkovProcessProperties[g2, "TransitionMatrix"] /. (0 -> Infinity)
   ];
Graph[
 g3,
 VertexStyle -> {1 -> Yellow, 2 -> Yellow, 3 -> Yellow, 4 -> Yellow},
 EdgeLabels -> "EdgeWeight",
 VertexSize -> 0.3,
 VertexLabels -> Placed[Automatic, {1/2, 1/2}]
 ]

This creates the graph from the given transition probabilities, which we get by multiplying the initial state with $T^n$ (1 element per row)

enter image description here

$\endgroup$
  • $\begingroup$ I'm looking for the tree diagram that forms from a 2-step transition, say startiing at Vertex 1 $\endgroup$ – PRG Dec 28 '18 at 23:17
  • $\begingroup$ Can't you just build a tree graph using the first row of the transition matrix of g2 to achieve that? Or am I misunderstanding what you're after? $\endgroup$ – Lukas Lang Dec 28 '18 at 23:18
  • $\begingroup$ It would be nice to have the tree graph generated automatically by choosing the starting vertex, say vertex 1 which would be row 1 of the T^2 matrix $\endgroup$ – PRG Dec 28 '18 at 23:25
  • $\begingroup$ @PRG I've updated the answer - is this what you meant? $\endgroup$ – Lukas Lang Dec 29 '18 at 13:26
  • $\begingroup$ Very close and many thanks! ... I was looking for a graph that generates ALL the intermediate transitions (from a starting vertex you choose) on the way to the transition state you want at the end (say 2nd transition). It would look like a classic "probability tree diagram" $\endgroup$ – PRG Dec 29 '18 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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