Covering with blocks in the non-symmetric case
type: Item
instance of: scholarly article
title: Covering with blocks in the non-symmetric case
zbMATH Open document ID: 0814.60008
DOI: 10.1007/BF02213458
author: Tamás F. Móri
published in: Journal of Theoretical Probability
publication date: 1995-02-26T00:00:00Z
review text: Let \(T(a)\) be the first occurrence time of the run \(a \in X^ n\) in an infinite sequence of letters drawn from the alphabet \(X\) whose letters have probabilities \(0<p_ 1\leq p_ 2 \leq \cdots \leq p_ d\). The covering time \(W_ n\) is the first time at which all runs of length \(n\) have appeared at least once. In the uniform case \((p_ 1 = p_ d)\) the limit distribution of \(W_ n\) as \(n \to \infty\) is known to be a renormalized Gumbel distribution \(F(t) = \exp (-e^{-t})\). The author shows that also in the nonuniform case \(\lim_{n \to \infty} P(\Phi_ n (W_ n) \leq t) = F(t)\) holds and computes the normalization \(\Phi_ n\) explicitly. If \(p_ 1 < p_ 2\), then \(\Phi_ n\) depends on the ratio \(p_ 2/p_ 1\), otherwise \(\Phi_ n\) depends only on \(p_ 1\) and its multiplicity. This result is a consequence of a more general weak convergence result for the associated point processes to certain homogeneous Poisson processes. The proofs do not use techniques for random walks on graphs, but rely on `classical' estimates for the (tail) probabilities of overlapping long runs and their approximate independence.
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60F05
zbMATH DE Number: 727279
zbMATH Keywords: random walks on graphs
zbMATH Keywords: cover time
zbMATH Keywords: Poisson process
zbMATH Keywords: Gumbel distribution
zbMATH Keywords: approximate independence
reviewed by: R. L. Schilling
MaRDI profile type: Publication
cites work: On the time taken by random walks on finite groups to visit every state
cites work: An introduction to covering problems for random walks on graphs
cites work: Lower bounds for covering times for reversible Markov chains and random walks on graphs
cites work: Threshold limits for cover times
cites work: Random walk covering of some special trees
cites work: Q4183968
cites work: Random walks on highly symmetric graphs
cites work: Random walks on \(Z^n_2\)
cites work: On the cover time of random walks on graphs
cites work: A martingale approach to the study of occurrence of sequence patterns in repeated experiments
cites work: Covering problems for Markov chains
cites work: Some sample path properties of a random walk on the cube
cites work: Large deviation results for waiting times in repeated experiments
cites work: Q3808939
cites work: Q3757048
cites work: More on the Waiting Time Till Each of Some Given Patterns Occurs as a Run
cites work: On the waiting time till each of some given patterns occurs as a run
cites work: Maximum Waiting Times are Asymptotically Independent
cites work: Q4850695
cites work: Expected cover times of random walks on symmetric graphs
cites work: A bound for the covering time of random walks on graphs
cites work: Q3771297
cites work: Covering times of random walks on bounded degree trees and other graphs
full work available at URL: https://doi.org/10.1007/bf02213458
OpenAlex ID: W1966244536
description: scientific article; zbMATH DE number 727279