UC Berkeley

Simple random coverage models, well studied in Euclidean space, can also be defined on a general compact metric space S. In one specific model, “seeds" arrive as a Poisson process (in time) at random positions with some distribution θ on S, and create balls whose radius increases at constant rate. By standardizing rates, the cover time C depends only on θ. The value x (S) = minθ (Formula presented)θ C is a numerical characteristic of the compact space S, and we give weak general upper and lower bounds in terms of the covering numbers of S. This suggests a future research program of improving such general bounds, and estimating x(S) for familiar examples of compact spaces. We treat one example, infinite product space [0,1]∞ with the product topology. On a different theme, 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 C to hold under minimal assumptions. We prove this as a simple consequence of a general result for increasing set-valued Markov processes.