Lower bounds for covering times for reversible Markov chains and random walks on graphs
type: Item
instance of: scholarly article
title: Lower bounds for covering times for reversible Markov chains and random walks on graphs
zbMATH Open document ID: 0684.60055
DOI: 10.1007/BF01048272
published in: Journal of Theoretical Probability
publication date: 1989-01-01T00:00:00Z
review text: For simple random walk on an N-vertex graph the mean time to cover all vertices is at least cN log N where c is an absolute constant. This result is deduced from a more general result about a lower bound for the mean coverage time for stationary finite-state reversible Markov chains, starting with the stationary distribution.
Mathematics Subject Classification ID: 60G50
zbMATH DE Number: 4121162
zbMATH Keywords: graph covering
zbMATH Keywords: random walk
zbMATH Keywords: mean coverage time
zbMATH Keywords: reversible Markov chains
zbMATH Keywords: stationary distribution
author: David Aldous
reviewed by: J. L. Teugels
MaRDI profile type: Publication
cites work: Q4153377
cites work: Q4076577
cites work: Q3950588
description: scientific article; zbMATH DE number 4121162