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 every one. I got the steps.2012-08-24