# How random is a random walker on a graph

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.

• Randomness does not imply uniformity, just some level of uncontrolled statistical variation. The weights just imply some bias, very similar to flipping an unfair coin or anything.
– Ian
Mar 21, 2018 at 16:29
• So this so-called bias you said, should be taken into account by the random walker. Shouldn't it? (Mr. Ripstein just answered). Also, I liked your first sentence about uniformity. Can you provide me with some more info on that subject? Because I cannot understand how something biased, could be called random too. Mar 21, 2018 at 16:37
• The walker does take into account the bias in how they select sites to visit. As for bias in general, this is everywhere in probability, so I don't really know what to tell you.
– Ian
Mar 21, 2018 at 17:02
• Ok. I'll take some time to think about it. Thank you. Mar 21, 2018 at 17:04

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

• So, can we say that the decision of the next step is affected by the probabilities stored in the transmission matrix or it is random at all? Could you describe the process with a pseudo-algorithm? Mar 21, 2018 at 15:48
• In a Markov chain or a random walk, the next step is determined only by your current state and not by the way you reached it. That means that, for your example, the probability to go from A to B is 0.3 no matter where you were before Mar 21, 2018 at 16:15
• Yeah, I know that. You probably misunderstood the question or I didn't ask it properly. Ok. We agree that 0.3 is the probability to go from A to B is 0.3 but how the decision to go from A to B is taken? Is it taken randomly or probabilistically based? In other words and according to your pseudo-algorithm, how the change_state() function decides the next step? Just picks one randomly with non zero probability or not? Mar 21, 2018 at 16:34
• It is taking by rolling a 10 faces dice where 3 faces say B, 2 are As and 2 are Ds and finally 1C, 1E and 1F Mar 21, 2018 at 16:37
• Wow! Thank you very much. That was the answer, that cleared everything. So. It is a biased dice. Now how can we call something bias and random at the same time I cannot fully understand, as I wrote to the @lan's comment. Mar 21, 2018 at 16:42