Threshold limits for cover times
type: Item
instance of: scholarly article
title: Threshold limits for cover times
zbMATH Open document ID: 0717.60082
DOI: 10.1007/BF01047002
published in: Journal of Theoretical Probability
publication date: 1991-01-01T00:00:00Z
review text: Let \({\mathcal S}_ 1,{\mathcal S}_ 2,..\). be a sequence of i.i.d. random subsets of a finite set S. Let \({\mathcal R}_ n={\mathcal S}_ 1\cup {\mathcal S}_ 2\cup...\cup {\mathcal S}_ n,\) the range of the process. For any \(B\subseteq S\) let C(B) denote the cover time of B, i.e., \(C(B)=\min \{n:\;{\mathcal R}_ n\supseteq B\},\) and \(c(B)=E C(B)\). Particularly, let \(C=C(S)\). Suppose S and the distribution of \({\mathcal S}_ 1\) vary in such a way that E \(C\to \infty\). Then C/E \(C\to 1\) in probability, E(C/E C)\({}^ m\to 1\) for each \(m<\infty\) and E exp(\(\alpha\) C/E C)\(\to \exp (\alpha)\) for each \(\alpha <\infty\) if and only if E c(\({\mathcal T})/E C\to 0\), where \({\mathcal T}=S\setminus {\mathcal R}_{C-1}\), the last uncovered portion of S (Corollary 1). This general result is applied to the cover time for finite Markov chains such as random walks on graphs.
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60D05
zbMATH DE Number: 4182543
zbMATH Keywords: threshold limit
zbMATH Keywords: cover time for finite Markov chains
zbMATH Keywords: random walks on graphs
author: David Aldous
reviewed by: Tamás F. Móri
MaRDI profile type: Publication
cites work: Hitting times for random walks on vertex-transitive graphs
cites work: An introduction to covering problems for random walks on graphs
cites work: Probability approximations via the Poisson clumping heuristic
cites work: Random walk covering of some special trees
cites work: Q4697452
cites work: Deviations from uniformity in random strings
cites work: Q4040734
cites work: Covering problems for Markov chains
cites work: Martingale Inequalities and NP-Complete Problems
cites work: Covering times of random walks on bounded degree trees and other graphs
cites work: A Technique for Lower Bounding the Cover Time
description: scientific article