Answer Happy

Consider a finite, connected, undirected graph G(N, E), where N is the set of nodes, and E is the set of edges. |N| and |E| denotes the number of nodes and edges respectively. Let d(i) denote the degree of node i, where i EN. Now, consider a particle making a random walk over the nodes of this graph, where at each time step, the particle moves from the previous node to one of its neighbors, chosen uniformly at random. Note that the position of the particle evolves as a Markov chain over the set of nodes N. What is the stationary distribution corresponding to the above Markov Chain? Hint: For each i EN,Ti, i.e., the term in the stationary distribution corresponding to state i, is proportional to the degree d(i).