If G = (V, E) is a connected, undirected, non-bipartite with n vertices and
m edges we can define a Markov chain, MG, on G by defining
the transition probability from vertex u to vertex v to be
Puv = 1/d(u) when (u,v) is an edge of G and 0 otherwise.
(A graph is bipartite if its vertices can be partitioned into two non-empty
sets so that no edge connects vertices within the same set.)
- Hitting time
- huv = expected time for a random walk starting
at u to first reach v
- Commute time
- Cuv = huv + hvu
- Cover time
- If Cu(G) is the expected amount of time for a random
walk starting at u to visit every vertex of G, the cover time is the
maximum of this over all starting vertices
Reference:
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan,
Cambridge University Press, 1995