2
$\begingroup$

I know that the stationary distribution of a random walk on the graph is given by, (degree of the node)/($2\times$ total number of links in graph). My question is, how do we get this solution?

1 Answers 1

1

I you start out in a distribution where the probability of being at a given node is proportional to the degree of the node, and you take one step (choosing at random a link from the current node), each link has equal probability of being the one taken, and moreover with equal probabilities in both directions. So the probability of the result of that step taking you to a given node is proportional to the number of links going to that node, i.e. the degree of the node. Thus this distribution is stationary.

  • 0
    Thank you Robert for your time. I understand that one knows the distribution, it can be shown if it is stationary. but the question is other way round. Think about a biased random walk where weights are not equal over all the links, even more wights are not same in both the directions of the link. Thank you again2012-08-14
  • 0
    vimal: Are you in fact asking about the system of equations defining stationarity of a distribution for a Markov chain on some graph?2012-08-14
  • 0
    @vimal: in general what you have is a Markov chain with a certain transition matrix $P$, and the stationary distribution is obtained by solving the linear system $v^T P = v^T$.2012-08-14
  • 0
    Thank you every one. I got the steps.2012-08-24