Expected cover times of random walks on symmetric graphs (Q1194485): Difference between revisions

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.