How random is a random walker on a graph

Question

First of all, I should mention that I'm not a mathematician but I'm coming from a biological background.

Last months I'm trying to understand the basic ideas under the random walker on a graph and some basics of Markov chains.

For simplicity's sake, let's say that we release a random walker on the following transition matrix that describes a weighted graph. Our final target could be the calculation of the edge relevance based on the times that a random walker visited each specific edge of the graph. Let's, for now, don't stay on that calculation of the edge relevance (could be calculated using some Markov chains properties).

So the first thing that we should do is to run the random walker on that transition matrix. The thing that concerns me know, is how much random this walk is gonna be? Will the decision of the random walker - on what his next step is going to be - be, affected by the weights of the graph (values in the transition matrix)?

If yes, why we call it random? I mean, I would expect a random walker to have equal probabilities to move from one node to the other and not be based on pre-specified probabilities like the initial probability distribution described by the transmission matrix.

Doesn't this initial distribution destroy the randomness?

    A   C   E   F   D   B
A 0.2 0.1 0.1 0.1 0.2 0.3
C 0.0 0.4 0.2 0.1 0.1 0.2
E 0.2 0.1 0.1 0.2 0.2 0.2
F 0.3 0.4 0.0 0.0 0.1 0.2
D 0.0 0.0 0.0 0.0 1.0 0.0
B 0.0 0.0 0.0 0.0 0.0 1.0

If no, then the randomness is saved, but then why do we need those weights to describe the relationships between the nodes of the graph? Just for the Markov chain calculations?

My question might look like very noobish and that's why I'm asking to excuse me. Of course, any intuitive explanation or external resources that you think will help me understand it more clearly that subject, are welcomed.

Answer 1

I think you are confusing the tool and the target.

A random walk is an algorithm used to detect most probable flows or behaviours in a situation in one or more dimensions. But the final output may not be random at all.

Think about it as a disoriented person lost in the forest that starts to walk. He is less likely to go up the hills (it's tiring and not probable to find towns there) and more likely to go down, but since he is disoriented he sometimes may do things which are counterintuitive. His walk is random in the sense that, if he starts again, he would do something completely different. However, over one million tries, surely he finishes most of the times in one of the towns, and only a few times in top of a hill

And, coming back again to your example, B and D are sinks (you cannot leave those states), so the walker will end there eventually. The algorithm may help you to see with which probability it end there

---

Example of pseudo-algorithm, being M the matrix of probabilities

for i in 1 to n_runs:
   S=initial_state(i) # returns a random initial state A/B/C/D/E/F
   for j=1...n_changes_state
        S=change_state(S,M) # returns the new state using M
   end for
   final_state(i)=S # vector of final outputs for each run
end for

And with this you will have after n_runs, a vector of final states, where most likely all are Bs and Ds if n_changes_state is big enough