# How to derive the graph of any n-step transitions through a Markov chain

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


• 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. – Szabolcs Dec 29 '18 at 7:37

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


### 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_.

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


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)

• I'm looking for the tree diagram that forms from a 2-step transition, say startiing at Vertex 1 – PRG Dec 28 '18 at 23:17
• 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? – Lukas Lang Dec 28 '18 at 23:18
• 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 – PRG Dec 28 '18 at 23:25
• @PRG I've updated the answer - is this what you meant? – Lukas Lang Dec 29 '18 at 13:26
• 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" – PRG Dec 29 '18 at 18:19