Expected cover times of random walks on symmetric graphs (Q1194485): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: An introduction to covering problems for random walks on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4692391 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The electrical resistance of a graph captures its commute and cover times / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Random walks on highly symmetric graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the cover time of random walks on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Covering problems for Markov chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a Result of Aleliunas <i>et al.</i> Concerning Random Walks on Graphs / rank | |||
Normal rank |
Revision as of 14:13, 16 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Expected cover times of random walks on symmetric graphs |
scientific article |
Statements
Expected cover times of random walks on symmetric graphs (English)
0 references
27 September 1992
0 references
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.
0 references
random walk
0 references
symmetric graph
0 references
cover time
0 references