Expected cover times of random walks on symmetric graphs
A simple random walk on a finite connected undirected graph, \(G=(V,E)\), is the Markov chain \(X_ n\), \(n\geq 0\), that from its current vertex \(v\) jumps to one of the \(d(v)\) neighboring vertices with uniform probability. The hitting time \(T_ v\) of the vertex \(v\) is the minimum number of steps the random walk takes to reach that vertex, and the cover time \(C\) is the minimum number of steps the random walk takes to visit all vertices in the graph, i.e.: \(C=\max_ v T_ v\). It is proved that if \(v\) is any vertex of a symmetric graph (symmetric here is understood as both vertex- and edge-symmetric), the expected cover time \(E_ v C\) is bounded below by \((N-1)H_{N-1}\) and is bounded above by \(2(N-1)^ 2\). The lower bound is an extension of similar results obtained by \textit{L. Devroye} and \textit{A. Sbihi} [J. Theor. Probab. 3, No. 4, 497-514 (1990; Zbl 0711.60068)]. The upper bound is a weak version of a result proved by \textit{J. D. Kahn, N. Linial, N. Nisan} and \textit{M. E. Saks} [ibid. 2, No. 1, 121-128 (1989; Zbl 0681.60064)]. A (nonessential) error in this latter paper and the way to fix it are also pointed out.
- An introduction to covering problems for random walks on graphs
- Covering problems for Markov chains
- scientific article; zbMATH DE number 194437 (Why is no real title available?)
- On a Result of Aleliunas et al. Concerning Random Walks on Graphs
- On the cover time of random walks on graphs
- Random walks on highly symmetric graphs
- The electrical resistance of a graph captures its commute and cover times
- Covering with blocks in the non-symmetric case
- Random walks on edge transitive graphs
- On hitting and cover times via electric networks
- On the cover time of random walks on graphs
- On a Result of Aleliunas et al. Concerning Random Walks on Graphs
- How to Design a Linear Cover Time Random Walk on a Finite Graph
- A Technique for Lower Bounding the Cover Time
- A note on the last new vertex visited by a random walk
- Expected hitting and cover times of random walks on some special graphs
- Random Walks on Regular and Irregular Graphs
- On the Last New Vertex Visited by a Random Walk in a Directed Graph
- Bounds on expected hitting times for a random walk on a connected graph
This page was built for publication: Expected cover times of random walks on symmetric graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1194485)
