# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Obtain partial probabilities of random walks on a directed graph

Contributed by:
Bradley Klee

ResourceFunction["DirectedGraphTransferMatrix"][ returns a matrix whose elements are partial probabilities describing random walks across directed graph | |

ResourceFunction["DirectedGraphTransferMatrix"][ orders the rows and columns of the output matrix according to vertex lists |

A random walk across directed graph *g* starts at one particular input vertex (VertexInDegree = 0) and ends at one particular output vertex (VertexOutDegree = 0). On all intermediary nodes, the walk chooses a next step at random from the immediate out components. If edge weights are specified, the random choice is weighted by the specified values.

The default ordering of the row and column spaces follows the ordering of VertexList, with output vertices on rows and input vertices on columns. It may be counter-intuitive to have *outs* before *ins* in the argument sequence. The reason behind this convention is that the row index goes before column index in Part specification.

On graphs with loops, intermediary vertices can have matrix elements greater than one. Such values indicate that a random walk can be expected to visit a particular vertex more than once before terminating on an output.

Vertex lists *outs* and *ins* are not only useful for re-ordering, but also for selecting matrix subspaces or particular elements.

ResourceFunction["DirectedGraphTransferMatrix"] accepts one option "Throughput" whose default value is False. When "Throughput" is set to True, the return matrix has extra rows listing partial probabilities on intermediary vertices.

With the setting "Throughput"→False, columns of the transfer matrix must sum to one by conservation of probability. This property does not depend on edge weights, because edge weights are assumed relative and normalized separately on each vertex.

Find the transfer matrix for a simple directed graph with one loop:

In[1]:= |

Out[1]= |

The probability for a random-walk to go from vertex 5 to vertex 3:

In[2]:= |

Out[2]= |

Determine output probabilities from input probabilities using Dot:

In[3]:= |

Out[3]= |

Label a binary tree with its output probabilities:

In[4]:= |

Out[4]= |

Adding edge weights to a graph changes the elements of the transfer matrix:

In[5]:= |

Out[5]= |

Label a binary tree with all of its partial probabilities:

In[6]:= |

Out[6]= |

Columns of the transfer matrix sum to 1:

In[7]:= |

Out[7]= |

The column sum property does not depend on edge weights:

In[8]:= |

Out[8]= |

Check the continuity constraint on each element of the transfer matrix:

In[9]:= |

Out[9]= |

On graphs with cycles, throughput vertices can have partial probabilities greater than one:

In[10]:= |

Out[10]= |

In[11]:= |

Out[11]= |

This means that, on average, the random walk will go through loops to visit the same vertex more than once:

In[12]:= |

Out[12]= |

Calculations may fail due to trapped cycles:

In[13]:= |

Out[13]= |

Adding an extra edge allows a positive result:

In[14]:= |

Out[14]= |

Find the probability of solving a logic maze through a random walk, without hitting a dead end:

In[15]:= |

Out[15]= |

Compare with brute force enumeration of 100,000 random walks:

In[16]:= |

Out[16]= |

Use WeightedAdjacencyGraph and DirectedGraphTransferMatrix to answer a Stack Exchange question:

In[17]:= |

Out[17]= |

- 1.0.0 – 21 August 2023

This work is licensed under a Creative Commons Attribution 4.0 International License