Record times for coverage thresholds and maximal spacings

Abstract

Let $X_1,X_2,\dots$ be independent uniform random points in a bounded region $A\subset {\mathbf{R}}^d$ having a smooth boundary, $d\ge 1$. Let $B\subset A$ be compact. The _coverage threshold_ of $B$, $R_n$, is the smallest $r$ such that $B$ is covered by the balls of radius $r$ centred on $X_1,\dots ,X_n$. The _maximal spacing_ ${\tilde{R}}_n$ is the volume of the largest ball contained in $A\setminus \{X_1,\dots ,X_n\}$. We investigate the asymptotic frequency of _record times_ in the sequence $(R_n)$, that is times $n$ for which $R_n<R_{n-1}$. Let $N_m$ denote the number of records in the sequence $(R_n)$ up to time $m$, and let ${\nu }_m$ be the time at which the $m$th record value of the sequence $(R_n)$ occurs. For $B\subset A^o$, we show that almost surely, $N_n\sim \frac{1}{2}(\log n{)}^2$ and ${\nu }_n^{1/\sqrt{n}}\to \exp \left(\sqrt{2}\right)$ as $n\to \infty$, and likewise for ${\tilde{N}}_n$ and ${\tilde{\nu }}_n$, defined analogously in terms of $({\tilde{R}}_n)$. But if $B=A$ and $d\ge 3$, then $N_n\sim \frac{1}{2}(1-\frac{1}{d})(\log n{)}^2$ and ${\nu }_n^{1/\sqrt{n}}\to \exp \left(\sqrt{2d/(d-1)}\right)$. We also discuss the generalization (for fixed $k\in \mathbf{N}$) to $k$-coverage thresholds, maximal $k$-spacings and non-uniformly distributed points $X_i$ in $A$.

32 page1, 1 figure