Threshold limits for cover times (Q2638665)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Threshold limits for cover times
scientific article

    Statements

    Threshold limits for cover times (English)
    0 references
    1991
    0 references
    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.
    0 references
    threshold limit
    0 references
    cover time for finite Markov chains
    0 references
    random walks on graphs
    0 references
    0 references

    Identifiers