Random walks on highly symmetric graphs (Q923511)

The author considers uniform random walks on finite graphs with n nodes. (For a finite Markov chain, let the covering time T be the time taken to visit all the states. D. J. Aldous showed that \({\mathbb{E}}(T)\) is approximately Rn log n, where n is the cardinality of a finite group and R is the mean number of visits to the initial state in a short time.) If a finite connected graph with n vertices is given, the nearest neighbor random walk on this graph is considered: for a vertex i, if \(v_ i\) is the number of edges connected to i, the probability that a particle moves from i to a neighboring vertex j is \(1/v_ i\). Several results have been obtained for the nearest neighbor random walk on graphs (D. J. Aldous), foremost among which is a general lower bound \({\mathbb{E}}_ n(T)=\Omega (n \log n)\) for the walk started with the stationary distribution \(\pi\). In the present paper, graphs for which the nearest neighbor random walk has symmetrical mean hitting times, that is \({\mathbb{E}}_ i(T_ j)={\mathbb{E}}_ j(T_ i)\) for all distinct vertices i,j are considered. Bounds for \({\mathbb{E}}(T)\) are provided, and in more detail two classes of graphs are studied, namely vertex-transitive graphs and distance-regular graphs.