1

Consider the directed probability graph, with 4 vertices (0, 1, 2, 3) represented by the following adjacency matrix P:

[1/3,  1/3,   0, 1/3]
[1/3,  1/3, 1/3,   0]
[  0,    0,   0,   0]
[  0,    0,   0,   0]

The edges represent transition probabilities between vertices. The edges are [(0,0), (0,1), (0,3), (1,0), (1,1), (1,2)] each with transition probability 1/3. There are two self loops (0,0) and (1,1), and a cycle created by edges (0,1) and (1,0).

For such (and possibly bigger and complex) graphs (with self loops and cycles, and hence possibly infinite number of possible paths), how does one go about calculating the total probability of all possible cycles that start at vertex 0 and end at vertex 0?

I've calculated this for 3-vertex graphs using geometric series. For instance, which comes out to:

P(0,2) * [ P(2,0) + P(1,2)*P(2,0) ] + P(0,1) * [ P(1,0) + P(1,2)*P(2,0) ]
-------------------------------------------------------------------------
                        [ 1 - P(1,2) * P(2,1) ]

Which is basically the sum of probabilities of simple paths, divided by some factor which does correction for the loop made by edges (1,2) and (2,1).

With this calculation, the results for 3-vertex graphs tally with the results of the problem I'm trying to solve. I'm not sure how to scale this to bigger graphs.

PS: This is in continuation to this question and the accepted answer, in which a parameter Pr(Cii(0)|G needs to be calculated.

Aditya
  • 11
  • 3
  • Good question, maybe take a look at powers of the transition matrix. P(0, 0) = p(0 to 0 in 1 step), P^2(0, 0) = p(0 to 0 in 2 steps), P^3(0, 0) = p(0 to 0 in 3 steps), etc? More suitable for math.stackexchange.com, also. – Robert Dodier Aug 20 '20 at 21:27

1 Answers1

0

The parameter Pr(Cii(0)|G) that you are computing can be treated as a special case of the general Pr(Cif(0)|G) for which an algorithm is given in the answer you linked.

The case of a loop can be handled by exactly the same code since the removal of 'successor' paths in each step prevent the loop continuing.

jds210
  • 101
  • 1
  • 4