Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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 again –  vimal Aug 14 '12 at 8:06
    
vimal: Are you in fact asking about the system of equations defining stationarity of a distribution for a Markov chain on some graph? –  Did Aug 14 '12 at 8:27
    
@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$. –  Robert Israel Aug 14 '12 at 18:02
    
Thank you every one. I got the steps. –  vimal Aug 24 '12 at 13:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.