The probability of visiting nodes in a random walk on a schedule

Question

I have a finite undirected graph in which a node is marked as "start" and the other is marked as "target".

The agent is first placed at the beginning of the node, and it moves around the chart arbitrarily, that is, at each step, it selects a neighboring node evenly randomly and moves to it. When it reaches the node target, it stops.

I am looking for an algorithm that, for each node, gives an indication of the likelihood that an agent visits it while traveling from start to target. Thanks.

Answer 1

As is often the case with charts, it is simply a question of how to properly describe the problem.

One way to write a graph is through an adjacency matrix . If your graph G = (V, E) has | V | nodes (where | V | is the number of vertices), this matrix will be | V | x | V |. If an edge exists between a pair of vertices, you set the element in the adjacency matrix to 1 or 0 if it is not.

A natural continuation of this is weighted graphs . Here, and not 0 or 1, the adjacency matrix has some idea of ​​weight.

In the case that you are describing, you have a weighted graph where the weights are the probability of moving from one node to another. This type of matrix has a special name, it is a stochastic matrix. Depending on how you ordered your matrix, this matrix will have either rows or columns that add up to 1, right and left stochastic matrices, respectively.

One connection between stochastic matrices and graphs Markov chains . In the Markov chain literature, the critical thing you need to have is a transition matrix (an adjacency matrix with weights equal to the probability of a transition after one time step). We call the transition matrix P.

The development of the probability of transition from one state to another after k timestamps is given by P ^ k. If you have a known initial state i, then the ith line P ^ k will give you the probability of transition to any other state. This gives you an estimate of the likelihood of being in a given state in the short term.

Depending on your source, the graph may be that P ^ k reaches a steady state distribution, i.e. P ^ k = P ^ (k + 1) for some value of k. This gives you an estimate of the likelihood of being in a given condition in the long run.

Aside, before doing any of this, you should be able to look at your schedule and say some things about how likely it is to be in a certain state at some time.

• If your chart has disjoint components, the probability of being in a component that you did not run is zero.
• If your graph has several absorbing states, that is, some states (or groups of states) are inevitable after you enter them, then you need to consider this. This can happen if your graph looks like a tree.