2021/01/29 by David Aldous, Aldous, David J. · 2 citations
Mathematics · #60G99 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Metric Geometry (math.MG) #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2101.12671
openalex publication_date 2021/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Simple random coverage models, well studied in Euclidean space, can also be defined on a general compact metric space. By analogy with the geometric models, and with the discrete coupon collector's problem and with cover times for finite Markov chains, one expects a "weak concentration" bound for the distribution of the cover time to hold under minimal assumptions. We give two such results, one for random fixed-radius balls and the other for sequentially arriving randomly-centered and deterministically growing balls. Each is in fact a simple application of a different more general bound, the former concerning coverage by i.i.d. random sets with arbitrary distribution, and the latter concerning hitting times for Markov chains with a strong monotonicity property. The growth model seems generally more tractable, and we record some basic results and open problems for that model.