Threshold limits for cover times (Q2638665): Difference between revisions

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.