Hi, I'm having trouble solving this problem. I was thinking of applying a Markov sequence property ( The average length of the cycle path of a node is the inverse of the probability of being in this node ), so the problem is reduced to an equation system. However, it's a 105 x 105 sparse matrix (at most 105 non-zero elements). I don't know if there is a gaussian elimination method for this kind of matrix or if the approach is incorrect. Thanks.
Omg, I just got accepted and I proved my solution, but I still don't believe it can be that simple. Code is like extremely short, that may be a hint.
Still, why does that work? What are your starting ideas on proving the correctness of the solution?
Spoilers. Revert to see them.
Yes, it is rather a well-known fact (I remember it being mentioned on my university probability course, but probably I have seen also somewhere else) and OP also mentioned it. Imagine an infinite random walk. What can you say about occurrences of v in that walk? How does it relate to average time of coming back from v to v?
can you please tell why the answer is not for any vertex i 1/(wi) where w is a vector such that w=wp where p=transition matrix . Swistakk update- problem done.
It's a classic property of random walks on graphs. A more strong fact for any irreducible markov chain it's explained here http://research.microsoft.com/en-us/um/people/peres/markovmixing.pdf , sections 1.4 and 1.5