2.1. Coarse threshold

It follows from a simple application of the Bollobás–Thomason threshold theorem [Reference Bollobás and Thomason7] that a covering process as we have defined it will always have a coarse threshold:

Proposition 1. (Coarse threshold.) Let X be a random covering variable for a set V. Then

\begin{align*} \mathbb{P}(C_t=V) &=\left\{\begin{array}{l@{\quad}l@{\quad}l} o(1) & if & \textrm{$t\ll T_{\frac{1}{2}}$,}\\[5pt] 1-o(1) & if & \textrm{$t\gg T_{\frac{1}{2}}$.} \end{array} \right. \end{align*}

Thus the covering time T is w.h.p. of the same order as $T_{\frac{1}{2}}$ . In the present work, however, we are interested in a much sharper form of concentration than the one guaranteed by Proposition 1: we want the covering time T to be sharply concentrated, i.e. we want that $T/T_{\frac{1}{2}} \rightarrow 1$ in probability. As we shall see in the next subsection, we cannot in general guarantee this kind of sharp concentration. A question of crucial interest is then what conditions are necessary or sufficient to have sharp concentration for T — and how the value of $\mathbb{E}T$ may be computed in such cases.

2.2. Elementary bounds

Let X be a random covering variable for an n-set V. For each $v\in V$ , let $q_v=\mathbb{P}(v\in X)$ , and set $q_{\star}=\min_v q_v$ . We have the following elementary bounds on the location of $T_{\frac{1}{2}}$ and probable location of T.

Proposition 2.

\begin{equation*} \frac{\log (2)}{-\log (1-q_{\star})} \leq T_{\frac{1}{2}} \leq \frac{\log (2n)}{-\log (1-q_{\star})}.\end{equation*}

What is more, for any fixed $\varepsilon>0$

\begin{equation*} \mathbb{P}\left(T\leq (1+\varepsilon) \frac{\log n}{-\log\left(1-q_{\star}\right)}\right) \geq 1-n^{-\varepsilon}.\end{equation*}

Proof. For $t\geq T_{\frac{1}{2}}$ we have

\begin{align*}\frac{1}{2}\leq \mathbb{P}(C_t=V)&\leq \inf_{v\in V}\mathbb{P}(v \in C_t)=1-\left(1- q_{\star}\right)^t,\end{align*}

from which the claimed lower bound on $T_{\frac{1}{2}}$ follows. For the upper bound, $t\leq T_{\frac{1}{2}}$ implies

\begin{align*}\frac{1}{2}\leq \mathbb{P}(C_t\neq V)\leq \sum_{v\in V}\mathbb{P}(v \notin C_t)&=\sum_{v\in V}(1-q_v)^t \leq n (1-q_{\star})^t.\end{align*}

Finally, for the ‘what is more’ statement, note that for $t\geq {(1+\varepsilon)}\cdot { \frac{\log n}{-\log \left(1-q_{\star}\right)}}$ , the expected number of vertices not yet collected is

\begin{align*}\mathbb{E}\vert V\setminus C_t \vert &=n (1-q_{\star})^t\leq n^{-\varepsilon},\end{align*}

whence by Markov’s inequality with probability at least $1-n^{-\varepsilon}$ we have $C_t=V$ and $T\leq t$ .

Note that if X is balanced then $q_v=\frac{\mu}{n}$ for all $v\in V$ , where $\mu\,:\!=\mathbb{E} \vert X\vert$ . In particular if $\mu=o(n)$ then the bounds above can be rewritten as

\begin{equation*}\frac{n\log 2}{(1+o(1))\mu}= \frac{\log 2}{-\log \left(1-\frac{\mu}{n}\right)} \leq T_{\frac{1}{2}}\leq \frac{\log (2n)}{-\log \left(1-\frac{\mu}{n}\right)} = \frac{n\log n}{(1+o(1))\mu}.\end{equation*}

Perhaps surprisingly, these elementary bounds are essentially sharp. As we shall show in the next section, the covering time T for the exchangeable k-uniform coupon collector (Example 1) is sharply concentrated around the value $\tfrac{\log n}{-\log \left(1-\frac{k}{n}\right)}$ ; in particular if $k=o(n)$ , $T_{\frac{1}{2}}=(1+o(1))\frac{n \log n}{k}$ . We think of this as ‘slow coverage’. On the other hand, there are instances of ‘fast coverage’, discussed in greater detail in Section 4. We give here a simple example.

Note that X is an exchangeable random covering variable, with expected size

\begin{equation*}\mathbb{E}\vert X\vert = (1-p)+pn=1 +c -\frac{c}{n}.\end{equation*}

Proof. By Theorem 1, w.h.p. the 1-uniform exchangeable coupon collector does not cover [n] in time less than $\frac{1}{2}n \log n$ . Thus for time $t<\frac{1}{2}n\log n$ , w.h.p. $T\leq t$ if and only if we have ‘won the lottery’ by time T, that is, if $X_i=[n]$ for some $i\leq t$ . This event occurs with probability $1-(1-p)^t$ .

To obtain Part 1 of the proposition, we observe that if $t\geq T_{\frac{1}{2}}$ then

\begin{equation*}\frac{1}{2}+o(1) \leq 1-(1-p)^t,\end{equation*}

yielding $t\geq (1+o(1))\frac{\log 2}{\log (1-p)}=(1+o(1))\frac{n\log 2}{c}$ , and we show similarly that if $t\leq T_{\frac{1}{2}}$ then $t\leq (1+o(1))\frac{n \log 2}{c}$ to conclude.

For Part 2, let Tʹ be the time at which we first ‘win the lottery’ by receiving all of V as our coupon. We have

\begin{equation*}\mathbb{E}T'=\sum_t tp(1-p)^{(t-1)}= \frac{1}{p}=\frac{n}{c}.\end{equation*}

Since $T\leq T'$ , we have that $\mathbb{E}T\leq \mathbb{E}T'$ . Now from our estimates for the probability of winning the lottery by time t above, w.h.p. we have $T'=o(n\log n)$ . Thus by Theorem 1, w.h.p. $T = T'$ , and

\begin{align*}\mathbb{E}T&\geq \sum_t t\mathbb{P}(T'=t\vert T'=T) \mathbb{P}(T'=T)\\&\geq \sum_t t \left(\mathbb{P}(T'=t)-o(1)\right)\\&=(1+o(1))\mathbb{E}(T'),\end{align*}

whence we are done.

Finally, for Part 3, we simply note that w.h.p. $T=T'$ , and that $\mathbb{P}(T'> \frac{xn}{c})=(1-p)^{\frac{xn}{c}}=e^{-x(1+O(n^{-1}))}\rightarrow e^{-x}.$

Propositon 3 shows two things. First of all, the lower bound on $T_{\frac{1}{2}}$ in Proposition 2 is essentially sharp; indeed taking $c=c(n)$ tending to infinity slowly, we have in Example 5 that $\mu=\mathbb{E}\vert X\vert= c(1+o(1))$ , and $T_{\frac{1}{2}}=(1+o(1))\frac{n\log 2}{\mu}$ . Further, by varying the value of $c=c(n)$ from $\Omega(\frac{1}{\log n})$ to o(n), we can get $T_{\frac{1}{2}}$ to take asymptotically any value between the bounds from Proposition 2.

Secondly, we cannot in general expect T to be sharply concentrated: Part 3 of Proposition 3 shows that we do not get sharper concentration than the Bollobás–Thomason-type concentration guaranteed by Proposition 1. With this in mind, we next focus on conditions on X which guarantee sharp concentration of the covering time T and/or ‘slow coverage’.

3.2 Continuous-time approximation of the coupon collector

In this subsection, we formalize our approximation of the discrete-time coupon collector by a continuous-time process. As described above, for every subset $S\subseteq V$ with $h(S)=\mathbb{P}(X=S)>0$ , we start at time $t=0$ a Poisson process $\mathcal{P}_S$ with intensity h(S). Our continuous coupon collector receives S as a coupon each time an event occurs in $\mathcal{P}_S$ . List the coupons in the order they are received by the continuous collector as $S_1, S_2, S_3, \ldots$ . The distribution of the sequence $\mathbf{S}=(S_n)_{n\in \mathbb{N}}$ is identical to that of the sequence of coupons $\mathbf{X}$ received by the (discrete-time) X-coupon collector. Furthermore, the time $t_m$ at which the continuous coupon collector receives his mth coupon is sharply concentrated around m for $m=\omega(1)$ . Indeed, by a standard bound on the Poisson distribution, for any $\varepsilon>0$ ,

\begin{equation*}\mathbb{P}\left(\vert t_m-m\vert\geq \varepsilon m \right)=O\left(\frac{1}{\sqrt{m\varepsilon^2}}e^{-\frac{m\varepsilon^2}{2}} \right).\end{equation*}

In particular, provided the covering time for the continuous coupon collector $t_T$ is large (grows with n), we have that w.h.p. $t_T=(1+o(1))T$ . Thus it is enough to prove w.h.p. bounds on $t_T$ to establish w.h.p. bounds on T. We shall thus in a slight abuse of notation identify $t_T$ with T in the rest of the paper, and prove bounds for the covering time via the continuous coupon collector. In particular we shall set $T=\inf\{t\,:\, Z_t=0\}$ .

3.3. Proofs: concentration of the covering time

It will be useful to consider the function $f(t) = \log( \mathbb{E}Z_t )$ . The first two derivatives of f are

\begin{equation*}f'(t) = - \frac{\sum_{x} q_x e^{-q_x t}}{\sum_{x} e^{-q_x t}}\leq 0, \quad f''(t) =\frac{1}{2} \cdot \frac{\sum_{x,y} (q_x-q_y)^2 e^{-(q_x+q_y) t}}{\sum_{x,y} e^{-(q_x+q_y) t}}\geq 0,\end{equation*}

from which we can see that f is a decreasing convex function. In particular for any $t\geq 0$ ,

(1) \begin{equation}f(t)-tf'(t) \leq f(0)=\log n.\end{equation}

Similarly, for any $t>0$ and $\Delta<t$ ,

(2) \begin{equation}f(t-\Delta)-f(t)\geq -\Delta f'(t) \qquad \textrm{ and } \qquad f(t)-f(t+\Delta)\geq -\Delta f'(t).\end{equation}

Finally, note that ${f'(t) = -\mathbb{E}[q_\theta | \theta \textrm{ not covered at time } t]}$ , where $\theta$ is chosen uniformly at random from V. The following lemma gives the basic first and second moment bounds on the covering time.

Proof. We divide the proof into two parts.

Proof of Part 1. Suppose $t=t(n)$ satisfies the lemma’s assumption. By Markov’s inequality $\mathbb{P}(t \geq T) = \mathbb{P}(Z_t >0) \leq \mathbb{E}Z_t = \sum_x e^{-q_x t} \to 0$ , so $t<T$ w.h.p.

Proof of Part 2. Suppose $t=t(n)$ satisfies our assumption. Then $\mathbb{E}Z_t \to \infty$ , and

\begin{align*} \frac{\text{Var}[Z_t]}{\mathbb{E}[Z_t]^2} &=\frac{\sum_{x,y} (e^{q_{xy} t}-1)\cdot e^{-(q_x+q_y) t}}{\sum_{x,y} e^{-(q_x+q_y) t}} \\ & < \frac{\sum_{x\neq y} (e^{q_{xy} t}-1)\cdot e^{-(q_x+q_y) t}}{\sum_{x,y} e^{-(q_x+q_y) t}} + \frac{1}{\sum_{x} e^{-q_x t}} = o(1) + o(1), \end{align*}

so by Chebyshev’s inequality $Z_t = (1+o(1))\mathbb{E}Z_t \to \infty$ w.h.p., so that w.h.p. $Z_t>0$ and $T>t$ .

Proof of Theorem 4. By the first moment property, $\mathbb{E}Z_{T^+} \to 0$ , from which it is immediate by Lemma 1 Part 1 that w.h.p. $T \leq T^+$ . To establish the lower bound on T, we shall consider the set of ‘rare’ coupons ${U = \{x \in V\,:\, q_x \leq 2 {\bar q} \}}$ . Let $Y_t$ be the number of $ x\in U$ for which x is uncovered at time t.

Proof. We bound ${\bar q}$ from below to get

\begin{equation*} {\bar q} \geq \frac{\sum_{x\in V \backslash U} q_x e^{-q_x {T^-}}}{\sum_{x \in V} e^{-q_x {T^-}}} \geq 2{\bar q} \frac{\sum_{x\in V \backslash U} e^{-q_x {T^-}}}{\sum_{x\in V} e^{-q_x {T^-}}} = 2{\bar q} \cdot \left(1-\frac{\mathbb{E}Y_{T^-}}{\mathbb{E}Z_{T^-}}\right). \end{equation*}

Dividing both sides by ${\bar q}$ gives us $1 \geq 2\big(1-\frac{\mathbb{E}Y_{T^-}}{\mathbb{E}Z_{T^-}}\big)$ , which implies $\mathbb{E}Y_{T^-} \geq \frac{1}{2}\mathbb{E}Z_{T^-}$ . Since by Assumption 1 $\mathbb{E}Z_{T^-} \to \infty$ , and since $\mathbb{E}Y_t$ is decreasing in t, we must have that $\mathbb{E}Y_{t} \to \infty$ for any $t \leq T^-$ , as claimed.

Now, as observed after Inequality (2),

\begin{equation*}f'(t) = -\mathbb{E}[q_\theta | \theta \textrm{ not covered at time } t],\end{equation*}

and in particular $f'(T^-) = -{\bar q}$ . By Assumption 1 $f(T^-)\to \infty$ , so Inequality (1) gives

(3) \begin{equation}T^-\cdot {\bar q} \leq f(T^-)-T^-f'(T^-)\leq \log n. \end{equation}

We are now in a position to apply Part 2 of Lemma 1 to the restriction of the coupon collector to the set of rare coupons U (i.e. to the coupon collector with covering variable $X\cap U$ ). For any $x\neq y$ , we have that ${q_{xy}t \leq C q_x q_y t}$ by Assumption 1. If $x,y\in U$ this quantity is at most ${4C ({\bar q})^2 T^-}$ . By Inequality (3) and Assumption 2, ${4C ({\bar q})^2 T^- \leq 4C {\bar q} \log n = o(1)}$ . Thus

\begin{align*} \frac{\sum_{x,y \in U\,:\, x \neq y } (e^{q_{xy} {t}}-1)\cdot e^{-(q_x+q_y) {t}}}{\sum_{x,y \in U} e^{-(q_x+q_y) {t}}} \\ \leq (e^{4C {\bar q} \log n}-1) \cdot \frac{ \sum_{x,y \in U\,:\, x \neq y} e^{-(q_x+q_y) {t}}}{\sum_{x,y \in U} e^{-(q_x+q_y) {t}}} = o(1). \end{align*}

Since by Claim 1 $\mathbb{E}Y_t \to \infty$ , we have by Lemma 1 Part 2 that $T^- \leq \inf \{ t\,:\, Y_t = 0\}$ w.h.p. Since by construction $Y_t\leq Z_t$ , this gives $T^-\leq T$ w.h.p., as required.

3.4. Proofs: sharp transition for $\mathbb{E}Z_t$

Proof of Theorem 3. Let $T^* = T^*(n) $ be the unique real for which $\mathbb{E}Z_{T^*} = 1$ .

1. 1. By our assumption, we can find $\Delta=\Delta(n)$ such that ${T^*\gg \Delta \gg \frac{1}{\min_x q_x}}$ . We will show that ${T^- \,:\!= T^*-\Delta}$ and $T^+ \,:\!= T^*+\Delta$ have the desired properties. By definition of $\Delta$ , we have $T^-=(1+o(1))T^+$ . Now $-\Delta f'(T^*)\geq \Delta \min_x q_x\gg 1$ , so by Inequality (2) we have $f(T^*-\Delta)-f(T^*)$ and $f(T^*)-f(T^*+\Delta)$ both tending to infinity. Since $f(T^*) = 0$ , this implies that $\mathbb{E}Z_{T^*-\Delta} \to \infty$ and $\mathbb{E}Z_{T^*+\Delta} \to 0$ , as required.

2. 2. Let $\alpha(n)=o(\log n)$ be as in the assumption. Pick $1\ll c \ll {\log n/(\alpha+2)}$ , and set $t^* = (\log n - c)/\|\mathbf{q}\|_{-\alpha}$ . By assumption, $t^*\gg \min_x q_x$ .

   For any $x\in V$ , we have

   \begin{equation*} q_x t^* \geq \frac{ (\alpha+2)\|\mathbf{q}\|_{-\alpha}t^*}{\log n} = \alpha +2-\frac{(\alpha+2)c}{\log n} = \alpha+2-o(1). \end{equation*}
   Now the function $z \mapsto e^{-z^{-1/\alpha}}$ is convex over those z satisfying $z^{-1/\alpha} \geq \alpha+1$ . We can therefore apply Jensen’s inequality as follows:
   \begin{equation*} \mathbb{E}Z_{t^*}=\sum_{x\in V} e^{-q_x t^*} =\sum_{x\in V} e^{-\left(q_x t_*\right)^{-\alpha \cdot (-1/\alpha)}} \geq n \exp(-\|\mathbf{q}\|_{-\alpha} t^*) = e^c. \end{equation*}
   But $ e^c \to \infty$ , so this gives us a $t^*\gg \min_x q_x$ such that $\mathbb{E}Z_{t^*} \gg 1$ . We are then done by Part 1.

3. 3. Let the function $A_r$ be as in the assumption. Let $R = R(n)$ be the largest r such that there are at least $A_r$ elements y with $q_y \leq r\min_x q_x$ ; R is finite for every n, but by assumption tends to infinity as $n\rightarrow \infty$ . We can therefore find $t^*=t^*(n)$ satisfying

   \begin{equation*}\frac{1}{\min_x q_x} \ll t^* \ll \frac{\log A_{R}}{R\min_x q_x }.\end{equation*}
   We now bound $\mathbb{E}Z_{t^*}$ from below:
   \begin{equation*}\mathbb{E}Z_{t^*} \geq \!\!\!\!\sum_{\substack{y \in V: \\ q_y \leq R \min_x q_x}} \!\!\!\!e^{-q_y t^*} \geq A_{R} e^{-R \min_x q_x t^*}\gg 1,\end{equation*}
   by the choice of $t^*$ . We are then done by Part 1.

3.5. Proofs: balanced coupons

Proof of Theorem 5. Since X is balanced, $q_x =\mu/n$ for all $x\in V$ . We will show that we can apply Part 2 of Lemma 1 provided 1 holds, and then that each of Conditions 2–4 implies 1. The ‘in particular’ statements in 2–4 combine the lower bound given by those special cases with the upper bound on T from Proposition 2.

1. 1. Since $q_x = q_y$ for all x, y, we have

   \begin{equation*} \frac{\sum_{x,y} (e^{q_{xy} t}-1)\cdot e^{-(q_x+q_y) t}}{\sum_{x,y} e^{-(q_x+q_y) t}} = \frac{\sum_{x,y} (e^{q_{xy} t}-1) }{n^2} = \frac{o(n^2)}{n^2}=o(1). \end{equation*}
   We can therefore apply Part 2 of Lemma 1 to conclude that $T(\mathbf{X})\geq T^-$ .

2. 2. Set $t={n (\log \beta -\omega(1))}/{\mu}$ for some $\omega(1)$ tending to infinity arbitrarily slowly. Note

   \begin{equation*} Z_t= ne^{-\log \beta +\omega(1)}\geq e^{\omega(1)} \rightarrow +\infty. \end{equation*}
   Let E be the set of exceptional pairs (x, y) with $q_{xy}>q$ . Since $q_{xy} \leq q_x=\frac{\mu}{n}$ for any x, y, we have
   \begin{align*} \sum_{(x,y)\notin E} e^{q_{xy} t} &\leq n^2 e^{qt} \leq n^2 + o(n^2) \qquad \textrm{and}\\ \sum_{(x,y)\in E} e^{q_{xy} t} & \leq \frac{n^2}{\beta} \cdot e^{\frac{\mu t}{n}} = \frac{n^2}{\beta} \cdot e^{\log \beta - \omega(1)} = o(n^2). \end{align*}
   Together, these bounds give that $\sum_{x,y} e^{q_{xy} t} = n^2+o(n^2)$ .

3. 3. Fix $x\in V$ , and consider the sum $\sum_{y\in V} q_{xy}$ . Each subset $X\subseteq V$ containing x contributes h(X) to $\vert X\vert$ terms of the sum. Thus

   \begin{equation*} \sum_{y\in V} q_{xy} = \sum_{X\ni x} \vert X\vert h(X) \leq M \sum_{X\ni x} h(X)=Mq_x. \end{equation*}
   Furthermore, for every y, $q_{xy}\leq q_x=\frac{\mu}{n}$ . We ask therefore: which choices of $\tilde q_{xy}$ , subject to the constraints $\sum_{y\in V} \tilde q_{xy}\leq M\frac{\mu}{n}$ and $0\leq \tilde q_{xy}\leq \frac{\mu}{n}$ , maximize the expression $\sum_{y\in V} e^{\tilde q_{xy}t}-1$ ? Since $z\mapsto e^{zt}-1$ is an increasing function for $t>0$ , the optimal $\tilde q_{xy}$ must satisfy ${\sum_{y\in V} \tilde q_{xy}=M\frac{\mu}{n}}$ . By the Karamata inequality the maximum of the sum is then attained when M of the $\tilde{q}_{xy}$ are equal to $\frac{\mu}{n}$ and the rest are equal to 0. Thus
   \begin{equation*} \sum_{y\in V} (e^{q_{xy}t}-1) \leq \sum_{y\in V} (e^{\tilde q_{xy}t}-1) < M \cdot e^{\frac{\mu t}{n}}. \end{equation*}
   Setting $t = \frac{n(\log n - \log M - \omega(1))}{\mu}$ for an arbitrary $\omega(1)$ tending to infinity, and summing over all x, we get
   \begin{equation*} \sum_{x,y\in V} (e^{q_{xy} t}-1) < Mn\cdot e^{\frac{\mu t}{n}} = Mn \cdot e^{\log n - \log M - \omega(1)} = o(n^2). \end{equation*}
   In addition our choice of t ensures $\mathbb{E}Z_t=M e^{\omega(1)}\rightarrow +\infty$ .

4. 4. If $q_{xy}=q$ for all $x\neq y$ and some q, then

   \begin{equation*} M\mu \geq \sum_{x,y} q_{xy} = \mu+\sum_{x\neq y} q_{xy} = \mu+ n(n-1) q, \end{equation*}
   so $q \leq \frac{(M-1)\mu}{(n-1)n}$ . For $t \leq \frac{n(\log n - \omega (1))}{\mu}$ with $t = o\big(\frac{n^2}{M \mu}\big)$ , we have that $qt =o(1)$ and ${q_x t \leq \log n - \omega (1)}$ , whence $Z_t\rightarrow \infty$ and
   \begin{align*} \sum_{(x,y)\,:\, x\neq y} (e^{q_{xy}t}-1) +\sum_{x} (e^{q_{x}t}-1) \\[3pt] < n^2 (e^{o(1)}-1)+ ne^{\log n - \omega (1)} =o(n^2). \end{align*}

In all cases, Condition 1 is satisfied.

Proof of Theorem 6. Since X is balanced, we have that $t_0=\frac{\log n}{-\log(1-c)}$ is a first moment threshold for the expected number of uncovered vertices $\mathbb{E}Z_t= n(1-c)^t$ . In particular we have that for any fixed $\varepsilon>0$ the covering time $T=T(\mathbf{X})$ satisfies $T<(1+\varepsilon)\frac{\log n}{-\log(1-c)}$ w.h.p. We turn our attention to the variance of $Z_t$ to show concentration of its value just below the first moment threshold $t_0$ :

\begin{align*}\mathbb{E}[Z_t^2]=&\sum_{x,y} \mathbb{P} (x,y \notin C_t)=\sum_{x,y} (1-\mathbb{P}(x,y \in X))^t \\[5pt] &\leq n\bigl((1-c)^{2t}(1+\eta)^t(n-b)+ (1-c)^tb\bigr)\\[5pt] & < n^2(1-c)^{2t}\left( (1+\eta)^t + b\left(\frac{1}{n(1-c)^{t}}\right) \right).\end{align*}

Now for $\varepsilon>0$ fixed and $t\leq (1-\varepsilon)\frac{\log n}{-\log(1-c)}$ , our assumptions on b and $\eta$ tell us that the above is at most

\begin{align*}\left(\mathbb{E}Z_t \right)^2\left( e^{\frac{\eta \log n}{-\log (1-c)}} + \frac{b}{n^{\varepsilon}} \right)=\left(\mathbb{E}Z_t \right)^2 (1+o(1)).\end{align*}

Chebyshev’s inequality is then enough to give us concentration of $Z_t$ about its (large, nonzero) mean for these values of t. In particular w.h.p. $T>(1-\varepsilon)\frac{\log n}{-\log(1-c)}$ . Thus w.h.p. $T=(1+o(1))\frac{\log n}{-\log(1-c)}$ , as required.

3.6. Proofs: exchangeable coupons

In the case where X it a (natural) coupling between the process of covering V by X with the classical coupon collector problem (covering by singletons chosen uniformly at random), which allows us to determine (up to a small error) the expectation of the covering time T as well as, in the case where $\vert X\vert =o(n)$ holds w.h.p., to prove that T is concentrated around its mean. We note that a similar coupling appears in a work of Sellke [Reference Sellke55], though it is used for a different purpose.

We begin by proving Theorem 8. Let $k=k(n)$ be a sequence of natural numbers. Set $V=V(n)=[n]$ , and let $X=X(n)$ be the random covering variable for V obtained by selecting a k-set from V uniformly at random. Let also $Y=Y(n)$ be the classical random coupon variable for V, namely the random covering variable obtained by selecting a singleton from V uniformly at random.

Proof of Theorem 8. We couple the k-uniform coupon sequence $\mathbf{X}$ to the sequence of coupons received by the Y-coupon collector, $\mathbf{Y} = (Y_i)_{i=1}^\infty$ . For natural numbers $a\leq b$ , set $C_Y[a,b]\,:\!=\bigcup_{i \in [a,b]} Y_i$ . Let $a_0 = 0$ , and define $a_i$ , $i\geq 1$ , recursively to be the least integer such that ${\left\vert C_Y[a_{i-1}\!+\!1,a_i]\right\vert = k}$ . Next, let ${X_i = C_Y[a_{i-1}\!+\!1,a_i]}$ . Clearly, the $X_i$ obtained are independent random sets, uniformly distributed among the k-sets in V, so $(X_i)_{i=1}^\infty \sim \mathbf{X}$ . Furthermore, the integers $\ell_i \,:\!= a_i-a_{i-1}$ are i.i.d. random variables.

This coupling between the coupon collectors enables us to relate $T(\mathbf{X})$ to $T(\mathbf{Y})$ . For any natural number t, we have that

\begin{equation*}\bigcup_{j=1}^{t} X_j= \bigcup_{i=1}^{a_t}Y_i,\end{equation*}

so $T(\mathbf{X})\leq t$ if and only if $T(\mathbf{Y})\leq {a_{t}}$ . Conversely, $T(\mathbf{X})> t$ if and only if $T(\mathbf{Y}) > {a_{t}}$ . In other words,

(4) \begin{equation}\sum_{i=1}^{T(\mathbf{X})-1} \ell_i = a_{T(\mathbf{X})-1} < T(\mathbf{Y}) \leq a_{T(\mathbf{X})} = \sum_{i=1}^{T(\mathbf{X})} \ell_i.\end{equation}

At this point, it is straightforward to get an estimate for $\mathbb{E}T(\mathbf{X})$ in terms of the (well-known) expectations of $T(\mathbf{Y})$ and $\ell_1$ , via an application of Wald’s inequality. To obtain sharp concentration for $T(\mathbf{X})$ we need only do a little more work. Let $S_m\,:\!= \sum_{i=1}^m \ell_i$ . We shall use the following lemma, establishing sharp concentration for $S_m$ , together with the Erdős–Rényi sharp concentration theorem for $T(\mathbf{Y})$ to deduce we have the desired sharp concentration for $T(\mathbf{X})$ .

Lemma 2. If $k=o(n)$ , then for all $c>0$ and $m>\frac{n}{k}$ the following inequality holds:

\begin{equation*}\mathbb{P}\left(\vert S_m-\mathbb{E}S_m\vert >c\cdot k\sqrt{\frac{m}{n}} \right)<4\cdot e^{-c}.\end{equation*}

Proof of Lemma 2. For $0\leq i \leq k-1$ , let $\tau_i$ be the time it takes for the singleton collector to draw the $(i+1)$ th distinct coupon after she has collected i distinct coupons. Clearly, $\tau_i \sim \text{Geom}(\frac{n-i}{n})$ and has moment-generating function

\begin{equation*}M_{\tau_i}(\lambda) \,:\!=\mathbb{E}[e^{\lambda \tau_i}] = \frac{(1-\frac{i}{n})e^\lambda}{1-\frac{i}{n}e^\lambda}.\end{equation*}

Note that $\ell_1 = \sum_{i=0}^{k-1} \tau_i$ . Since $S_m = \sum_{i=1}^m \ell_i$ is the sum of m independent copies of $\ell_1$ , its moment-generating function is given by

\begin{equation*}M_{S_m}(\lambda)= \left(\prod_{i=0}^{k-1} \frac{(1-\frac{i}{n})e^\lambda}{1-\frac{i}{n}e^\lambda}\right)^m.\end{equation*}

Applying Markov’s inequality to the random variable $\exp{(\lambda {S_m})}$ , for some $\lambda$ : $\lambda\neq 0, \ \lambda =o(1)$ to be specified later, gives

(5) \begin{align}&\mathbb{P}\left(e^{\lambda S_m} > e^{\lambda\mathbb{E}S_m+c}\right) \nonumber<\frac{M_{S_m}(\lambda)}{\exp\left(\lambda\mathbb{E}S_m+c\right)} \nonumber\\[5pt] &\quad =\frac{\exp\left(m \sum_{i=0}^{k-1} (\lambda+\log(1-\frac i n)-\log(1-\frac i n e^\lambda))\right)}{\exp\left(m\left(\sum_{i=0}^{k-1} \frac{\lambda}{1-\frac i n}\right)+c\right)} \nonumber\\ &\quad =\exp\left(m \sum_{i=0}^{k-1} \Big(\lambda+\log\Big(1-\frac i n\Big)-\log\Big(1-\frac i n e^\lambda\Big)-\frac{\lambda}{1-\frac i n}\Big)\right)\nonumber\\[5pt] &\quad \leq \exp\left(m k \Big[\lambda+\log\Big(1-\frac k n\Big)-\log\Big(1-\frac k n e^\lambda\Big)-\frac{\lambda}{1-\frac k n}\Big]+c\right),\end{align}

where the last inequality holds since the summands are non-decreasing in i (this can be checked e.g. by computing the derivative of a summand with respect to i). We use a Taylor expansion of degree $d=\lceil-\log |\lambda|\rceil$ to estimate the quantity inside the square brackets:

(6) \begin{align}&\lambda + \log\left(1-\frac k n\right)-\log\left(1-\frac k n e^\lambda\right)-\frac{\lambda}{1-\frac k n} \nonumber\\ & \leq \sum_{j=1}^{d} (e^{\,j\lambda}-j\lambda-1)\frac{k^j}{jn^{\,j}}+\frac{k^{d+1}}{(d+1)(n-k)^{d+1}}.\end{align}

Note that $(e^{\,j\lambda}-j\lambda-1) =(\frac{1}{2}+o(1)) \cdot (j\lambda)^2$ , since $j\lambda =o(1)$ , whereas $\frac{k^{d+1}}{(n-k)^{d+1}} \ll (e^{-2})^d\cdot \frac{k}{n} \leq \frac{\lambda^2 k}{n}$ , since $\frac{k}{n-k} =o(1)$ by assumption. The right-hand side of Inequality (6) can thus be bounded by

\begin{equation*}\left(\frac{1}{2}+o(1)\right)\cdot \lambda^2 \sum_{j=1}^d \frac{jk^j}{n^{\,j}} + o\left(\frac{\lambda^2k}{n}\right)= \frac{(1+o(1))\lambda^2k}{2n}.\end{equation*}

Applying this bound to the right-hand side of Inequality (5) gives us the following:

\begin{align}\mathbb{P}\left(e^{\lambda S_m} > e^{\lambda\mathbb{E}S_m+c}\right)& < \exp\left( \frac{(1+o(1))m\lambda^2k^2}{2n}+c \right). \nonumber\end{align}

Letting $\lambda = \pm\frac{1}{k}\sqrt{\frac n m}$ we obtain

\begin{align*}\mathbb{P}\left( S_m - \mathbb{E}S_m> \,\,\,\,\,ck\sqrt{\frac m n}\right)&< e^{\frac{1}{2}+o(1)-c}, \textrm{ and }\\\mathbb{P}\left( S_m - \mathbb{E}S_m < -ck\sqrt{\frac m n}\right)&<e^{\frac{1}{2}+o(1)-c}. \nonumber\end{align*}

Thus for n sufficiently large, the probability that $S_m$ diverges from its expectation by more than $ck\sqrt{\frac{m}{n}}$ is at most $2e^{(\frac{1}{2}+o(1)) -c}<4e^{-c}$ .

Inequality (4) can also be formulated as

(7) \begin{align} S_{T(\mathbf{X})-1} < T(\mathbf{Y}) \leq S_{T(\mathbf{X})} .\end{align}

Lemma 2 gives us that $\vert S_{m} - \mathbb{E}S_{m}\vert < \sqrt{mk}$ with probability $1- O(e^{-\sqrt{n/k}})=1-o(1)$ . Since each $\ell_i$ is independent from $T(\mathbf{X})$ (how long it takes to collect one k-set tells us nothing about how many k-sets are needed to cover the entire set of coupons), we can use the lemma with $m=T(\mathbf{X})$ to bound the right-hand side of Inequality (7), and $m=T(\mathbf{X})-1$ for the left-hand side. (The lemma requires that $T(\mathbf{X}) > \frac{n}{k}$ , which holds w.h.p. by the first moment method.) This gives us that, w.h.p.,

\begin{equation*} k(T(\mathbf{X})-1) -\sqrt{k(T(\mathbf{X})-1)} < T(\mathbf{Y}) \leq kT(\mathbf{X}) +\sqrt{kT(\mathbf{X})}.\end{equation*}

By Theorem 1, $T(\mathbf{X})< \frac{2n \log n}{k} $ holds w.h.p., and ${\vert T(\mathbf{Y}) - n\log n\vert} < cn$ holds with probability at least $1-e^{-c}+o(1)$ . Applying the triangle inequality, we see that

\begin{align*} \left\vert T(\mathbf{X})-\frac{n\log n }{k}\right\vert &\leq \left\vert \frac{T(\mathbf{Y})}{k}-\frac{n\log n }{k}\right\vert+\left\vert T(\mathbf{X})-\frac{T(\mathbf{Y})}{k}\right\vert \\[5pt] &\leq c\cdot \frac{n}{k}+\frac{\sqrt{T(\mathbf{X})}}{k}+1\leq c\cdot \frac{n}{k} + \frac{\sqrt{2n \log n}}{k\sqrt{k}}\\[5pt] &= (c+o(1))\cdot \frac{n}{k} \end{align*}

holds with probability at least $1-e^{-c}+o(1)$ . The theorem follows.

We now turn our attention to Theorem 7. Suppose that we have an exchangeable random covering variable W for the set $V=[n]$ . Let $\mu=\mathbb{E}\vert W\vert$ , let M be the maximum value that $\vert W \vert $ takes with strictly positive probability, and let $\chi=\mathbb{E} [\vert W\vert^2]$ .

Coupling the W-coupon sequence $\mathbf{W} = (W_1, W_2, \ldots)$ with the singleton coupon sequence $Y_1, Y_2, \ldots$ as in the proof of Theorem 8, we get the following analogue of Inequality (4):

(8) \begin{equation}\sum_{i=1}^{T(\mathbf{W})-1} \ell_i < T(\mathbf{Y}) \leq \sum_{i=1}^{T(\mathbf{W})} \ell_i,\end{equation}

where $\ell_i$ is the least integer such that $C_{Y}[\ell_1+\cdots+\ell_{i-1}+1, \ell_{1}+\cdots+\ell_i]= \vert W_i\vert$ . Applying Wald’s inequality, we get that

(9) \begin{align} \frac{\mathbb{E}T(\mathbf{Y})}{\mathbb{E}\ell_1}\leq \mathbb{E}T(\mathbf{W}) <1+\frac{\mathbb{E}T(\mathbf{Y})}{\mathbb{E}\ell_1}.\end{align}

In particular if $\mathbb{E}\ell_1=o(n\log n)$ , we have $\mathbb{E}T(\mathbf{W})=(1+o(1))\frac{n\log n}{\mathbb{E}\ell_1}$ . An inconvenient aspect of this expression is that it remains in terms of $\mathbb{E}\ell_1$ , the expected number of single coupons we need to draw in order to see $\vert W\vert$ distinct coupons. However if $M=o(n)$ , note that for any $m\leq M$ the expected number of single coupons we need to draw in order to see m distinct coupons is

(10) \begin{align}\sum_{i=0}^{m-1}\frac{n}{n-i}=(1+o(1))n \log \left(\frac{n}{n-m}\right)= (1+o(1))m,\end{align}

and thus $\mathbb{E}\ell_1=(1+o(1))\mathbb{E} \vert W\vert$ . Together with (9), (10) establishes the following.

Theorem 7, which we now prove, gives conditions for the covering time $T(\mathbf{W})$ to be sharply concentrated around its expected value.

Proof of Theorem 7. We first prove that if any of Conditions 1–3 holds, then w.h.p. $T(\mathbf{W})=(1+o(1)) \frac{n\log n}{\mu}$ . Note that Conditions 1–3 give us $M=o(n)$ , whence $\mathbb{E}\ell_1\leq (1+o(1))M=o(n\log n)$ . As in Theorem 8, having sandwiched $T(\mathbf{Y})$ between two sums of i.i.d. random variables $S_{T(\mathbf{W})-1}\,:\!=\sum_{i=1}^{T(\mathbf{W})-1}t_i$ and $S_{T(\mathbf{W})}\,:\!=\sum_{i=1}^{T(\mathbf{W})}t_i$ , the crux of the proof lies in showing these two (random) sums are concentrated around their respective means. Indeed, provided we can show that w.h.p. $S_{T(\mathbf{W})}=(1+o(1)) T(\mathbf{W}) \mathbb{E}\ell_1$ and $S_{T(\mathbf{W}) -1}=(1+o(1))(T(\mathbf{W})-1) \mathbb{E}\ell_1$ , we have that w.h.p.

\begin{align*}(1+o(1))\frac{n\log n}{\mathbb{E} \ell_1}=(1+o(1))\frac{T(\mathbf{Y})}{\mathbb{E}\ell_1} \leq T(\mathbf{W}) \textrm{ and }\\ T(\mathbf{W}) \leq (1+o(1))\frac{T(\mathbf{Y})}{\mathbb{E} \ell_1}+1 = (1+o(1))\frac{n\log n}{\mathbb{E}\ell_1}\end{align*}

by appealing to Theorem 1 (and the fact that $\mathbb{E}\ell_1=o(n\log n)$ by (10)). Let us therefore establish the concentration we require.

We use the following generalized Chernoff bound; see e.g. Theorems 2.8 and 2.9 in [Reference Chung and Lu9].

Lemma 3. (Generalized Chernoff bound.) Let $(U_i)_{i=1}^t$ be a sequence of i.i.d. nonnegative integer-valued random variables, with $U\,:\!=U_1 \leq M$ with probability 1. Let $\varepsilon>0$ be fixed. Then

\begin{equation*}\mathbb{P}\left(\bigg\vert \sum_{i=1}^t U_i - t\mathbb{E}U\bigg\vert\geq \varepsilon \mathbb{E}U \right) \leq 2 \exp\left({-\frac{\varepsilon^2 t^2 (\mathbb{E}U)^2} {2 t\mathbb{E}[U^2]+2Mt\mathbb{E}U /3}}\right).\end{equation*}

We apply the Lemma to $\vert W\vert$ . Suppose Condition 2 of Theorem 7 holds. Then $M=o(n)$ and thus $\mathbb{E}\ell_1=(1+o(1))\mu$ . For any fixed $\varepsilon>0$ and $t=(1+o(1)) \frac{n\log n}{\mu}$ we have that

\begin{align*} \mathbb{P}\left(\bigg\vert \sum_{i=1}^t \vert W_i\vert - t\mu\bigg\vert \geq \varepsilon t \mu \right) &\leq 2 \exp\left({-\frac{\varepsilon^2 t \mu^2} {2 \chi +2M \mu/3}}\right) \\[3pt] &\leq 2\exp\left({ -\varepsilon^2 (1+o(1))\frac{ n\log n \mu}{2 M^2+ 2M\mu /3}}\right) \\[5pt] &=\exp\left({-\varepsilon^2 (1+o(1))\frac{ n\log n \mu}{2M^2}}\right)=o(1), \end{align*}

where the last equality used the fact that $M=o(n\log n)$ . Thus for t around the expected value of $T(\mathbf{W})$ , the sum $S_t=\sum_{i=1}^{t}\ell_i$ is w.h.p. concentrated around its mean $(1+o(1))\mu t$ . It follows that if Condition 2 is satisfied then w.h.p. $T(\mathbf{W})= (1+o(1))\frac{T(\mathbf{Y})}{\mu}$ , as desired. Since Condition 2 implies Condition 1 this also establishes that Condition 1 is sufficient for $T(\mathbf{W})$ to be sharply concentrated around $\frac{n \log n}{\mu}$ . For Condition 3, we use the same argument as for Condition 2 but use the assumption $\chi= o(n\log n\mu)$ to bound $\chi$ instead of the bound $\chi \leq M^2$ .

For Condition 4, we show that we can truncate W; for $\varepsilon>0$ fixed, Chebyshev’s inequality implies

\begin{equation*}\mathbb{P}\left(\bigl\vert \vert W\vert -\mu \bigr \vert> \varepsilon \mu \right) \leq \frac{\chi -\mu^2}{\varepsilon^2 \mu^2}=o\left(\frac{1}{n\log n\mu}\right).\end{equation*}

Thus the expected number of coupons with size differing from $\mu$ by more than $\varepsilon \mu$ which occur by time $t=(1+o(1))\frac{n\log n}{\mathbb{E}\ell_1}\leq (1+o(1))\frac{n\log n}{\mu}$ is o(1). By Markov’s inequality w.h.p. no such coupon is seen by that time, and we can couple/sandwich the W-coupon collectors between two k-uniform exchangeable coupon collectors $X^-$ and $X^+$ , collecting coupons of size $k_-=(1-\varepsilon)\mu$ and $k_+=(1+\varepsilon)\mu$ respectively, in such a way as to have $T(\mathbf{X^-})\leq T(\mathbf{W})\leq T(\mathbf{X^+})$ .

We then split into two cases. If $\mu=o(n)$ , then by Theorem 8 w.h.p. these two sandwiching coupon collectors finish at times $T(\mathbf{X^-})=(1+o(1))\frac{n\log n}{(1-\varepsilon) \mu}$ and $T(\mathbf{X^+})=(1+o(1))\frac{n\log n}{(1+\varepsilon) \mu}$ respectively. Since $\varepsilon>0$ was arbitrary we deduce that $T(\mathbf{W})=(1+o(1))\frac{n\log n}{\mu}$ as desired. If on the other hand $\mu=cn$ for some $c\in(0,1)$ , then by Corollary 1 w.h.p. these two sandwiching coupon collectors finish at times $T(\mathbf{X^-})=(1+o(1))\frac{\log n}{-\log \left(1-c(1-\varepsilon)\right)}$ and $T(\mathbf{X^+})=(1+o(1))\frac{\log n}{-\log \left(1-c(1+\varepsilon)\right)}$ respectively (provided we picked $\varepsilon$ sufficiently small so that $c(1+\varepsilon)<1$ and $c(1-\varepsilon)>0$ ). Since $\varepsilon>0$ was arbitrary we deduce that $T(\mathbf{W})=(1+o(1))\frac{\log n}{-\log(1-c)}$ as desired.

4.1. Sufficient conditions for fast coverage

We have given two instances of fast coverage so far. In Example 5, fast coverage occurred because though the average coupon size was small, there was a small chance of ‘winning the lottery’ and receiving a very large coupon. In Example 5, fast coverage occurred because X was structured in such a way that the problem of covering $V=[kn]$ with k-sets was actually equivalent to the problem of covering a much smaller set $V'=[n]$ , which could be achieved more rapidly (and also entailed having some very large pairwise correlations $q_{xy}$ ).

We can restate these two ‘speeding up’ properties in a formal way.

Proof. Suppose Condition 1 is satisfied. Let $\eta>0$ be a fixed positive number to be fixed later. We say that coupons of size at least $C\mu$ are large, and we call other coupons small. We couple X with a transitive $C\mu$ -uniform covering variable Y, by setting Y to be a $C\mu$ -subset of X chosen uniformly at random if X is large, and to be the empty set otherwise. By Proposition 2, w.h.p. the Y-collector will need at most $(1+\eta) \tfrac{\log n}{-\log \left(1- \frac{C\mu}{n}\right)}$ non-empty coupons to cover V. Set $p =\frac{1+\varepsilon}{C}$ . Let t be an integer with

\begin{equation*}\left(\frac{1+\eta}{1-\eta}\right) \left(\frac{1}{p}\right) \frac{\log n}{- \log \left(1 -\frac{C\mu}{n}\right) } \leq t \leq \left( 1-\eta\right) \frac{\log n}{- \log\left( 1-\frac{\mu}{n}\right)}.\end{equation*}

Since the left-hand side is at most $\frac{1+\eta}{1-\eta}\frac{1+o(1)}{1+\varepsilon}\frac{\log n}{-\log\left(1-\frac{\mu}{n}\right)}$ , by picking $\eta$ sufficiently small relative to $\varepsilon$ and n sufficiently large we can always do this. We claim that w.h.p. the Y-collector will have covered all of V by time t. Indeed, the probability that $Y\neq\emptyset$ is, by assumption, at least p. By a standard Chernoff bound, the probability that at least $(1-\eta)pt$ of the first t coupons of the Y-coupon collectors are non-empty is at least $1- e^{-\frac{\eta^2 pt}{3}}=1-o(1)$ . (Here we use the fact that $pt=\Omega\Big(\frac{\log n}{-\log\left(1-\tfrac{C\mu}{n}\right)}\Big)\rightarrow \infty$ as $n\rightarrow \infty$ .) Thus w.h.p. by time t we have seen at least $(1-\eta)pt$ non-empty Y-coupons; by our choice of t, this is at least $(1+\eta)\frac{\log n}{ - \log \left(1 -\frac{C\mu}{n}\right) }$ , whence w.h.p. these non-empty Y-coupons cover all of V. Our coupling of Y with X then implies that w.h.p. $T(\mathbf{X})\leq t$ . Since by definition $t\leq \left( 1-\eta\right) \frac{\log n}{- \log\left( 1-\frac{\mu}{n}\right)}$ , we conclude that X is fast.

For the second part of the theorem, suppose Condition 2 is satisfied. We define a random covering variable Z for [nʹ] as follows: set $Y=\{i\,:\, V_i \subseteq X\}$ . Set $p =(1+\varepsilon)\frac{\log n'}{ \log n}\break\left({-}\log \left(1-\frac{\mu}{n}\right)\right)$ . Let $\eta>0$ be chosen sufficiently small so that $1+\varepsilon> \frac{1+\eta}{1-\eta}$ . Let t be an integer with

\begin{equation*} \frac{(1+\eta)\log n'}{p} \leq t \leq (1-\eta) \frac{\log n}{-\log \left(1-\frac{\mu}{n}\right)} .\end{equation*}

By our choice of $\eta$ , and for n sufficiently large, we can always pick such a t. We claim that w.h.p. the Y-collector will have covered all of [nʹ] by time t. Indeed by Condition 2 the expected number of $i\in[n']$ not covered by the Y-coupon collector by time t is

\begin{align*}\sum_{i\in [n']} (1-\mathbb{P}(i\in Y))^t&\leq n' (1-p)^t\leq e^{-\eta \log (n')}=o(1),\end{align*}

so that by Markov’s inequality w.h.p. the Y-coupon collector has covered [nʹ] by time t. By the coupling of Y with X, and the fact that $\bigcup_i V_i =V$ , it follows that w.h.p. $T(\mathbf{X})\leq t$ . Since we chose $t \leq (1-\eta) \frac{\log n}{-\log \left(1-\frac{\mu}{n}\right)}$ , we conclude that X is fast.

Theorem 9 leaves a number of interesting questions open. To begin with, are there other, subtler ways of being fast than either winning the lottery or collecting a smaller coupon set? In particular, are there conditions on the pairwise intensities $(q_{xy})_{x,y \in V}$ which imply fast coverage? Furthermore, Theorem 9 says nothing on what the probable value of $T(\mathbf{X})$ actually is. In cases where X is fast, can we determine good bounds for $\mathbb{E}T$ ? With its ties to the k-SAT problem (see the next section), this is one of the most important open problems related to this paper.

5.1. Connectivity in random graphs

We consider the discrete time multigraph process $(G_t)_{t\geq 0}$ obtained by starting with the empty graph $G_0$ on $V=[n]$ and at each time step $t\geq 1$ selecting an edge uv uniformly at random and adding it to $G_{t-1}$ to form $G_t$ . We associate $n/2$ coupon collectors $\mathbf{X}^i$ to this process, $1\leq i \leq \frac{n}{2}$ . The ith such collector aims to cover each i-set A with an edge from A to $V\setminus A$ . Since each edge uv connects $2\binom{n-2}{i-1}$ i-sets to their complements in V, the ith collector is $2\binom{n-2}{i-1}$ -uniform and balanced, and aims to cover a set of size $\binom{n}{i}$ . By Proposition 2, we thus have that her covering time $T(\mathbf{X}^i)$ will be w.h.p. at most $(1+o(1))t_i$ where

\begin{align*}t_i &= \frac{\log \binom{n}{i}} {-\log\left(1- \frac{2\binom{n-2}{i-1}}{\binom{n}{i}}\right)}= \frac{\log \binom{n}{i}}{-\log\left(1- \frac{i(n-i)}{\binom{n}{2}}\right)}.\end{align*}

For $i=o(n)$ , $t_i=t_1 - \frac{n\log i}{2} +o(n)$ , while for $i=\theta(n)$ $t_i=O(t_1/\log n)$ . Further by Proposition 2 we know that for any fixed $\eta>0$ we have that $T(\mathbf{X}^i)> (1+\eta)t_i$ with probability at most $n^{-\eta}$ . Also in the case $i=1$ the collector’s random coupon variable is in fact exchangeable and 2-uniform. By Theorem 8, for any $x> 0$ ,

\begin{align*}\mathbb{P}\left(T(\mathbf{X}^1)>t_1+\frac{xn}{2}\right)&\leq e^{-x}(1+o(1)) \textrm{, and }\\\mathbb{P}\left(T(\mathbf{X}^1)<t_1-\frac{xn}{2}\right)&\leq e^{-x}(1+o(1)).\end{align*}

Thus by the union bound we have that for any $x=x(n)>0$ ,

\begin{align*}&\mathbb{P}\left(\max_i T(\mathbf{X}^i)>t_1+ \frac{xn}{2}\right)\\[2pt] &\quad\leq \sum_i \mathbb{P}\left(T(\mathbf{X}^i)> t_i\left(1+\frac{\log i +x}{\log n}\right)(1+o(1))\right)\\[2pt] &\quad\leq (1+o(1))\sum_{i\geq 1} e^{-\log i +x}\\ &\quad\leq (1+o(1))e^{-x}\log n.\end{align*}

In particular, setting $x=\varepsilon \log n$ , the inequality above together with our bound on $\mathbb{P}(T(\mathbf{X}^1)<t_1-xn)$ establishes the following.

Theorem 10. Let $\varepsilon>0$ be fixed. Then

\begin{align*} \mathbb{P}\left(G_t \textrm{ is connected} \right)&\leq n^{-\varepsilon+o(1)} \qquad& \textrm{for }t\leq \frac{n \log n}{2}(1-\varepsilon);\\[2pt] \mathbb{P}\left(G_t \textrm{ is connected} \right)&\geq 1-n^{-\varepsilon +o(1)} \qquad & \textrm{for }t\geq \frac{n \log n}{2}(1+\varepsilon).\end{align*}

It is easy to relate $G_t$ to the size model $G_{n,m}$ of random graphs obtained by selecting m distinct edges uniformly at random and adding them to the empty graph on n vertices. Indeed Markov’s inequality shows that for $t=O(n\log n)$ , w.h.p. $G_t$ contains only $O(\frac{t^2}{n^2})=O((\log n)^2)$ repeated edges, so one can couple $G_t$ with $G_{n,m}$ up to the connectivity threshold for $G_t$ in such a way that $G_{n, t-O((\log n)^2)} \subseteq G_t \subseteq G_{n, t}$ . In this way, Theorem 10 allows us to recover (a slightly weaker form of) the classical results of Erdős and Rényi [Reference Erdős and Rényi17] on the connectivity threshold for $G_{n,m}$ : w.h.p. $G_{n,m}$ becomes connected at size $m=(1+o(1))\frac{n \log n}{2}$ .

5.2. Covering a square with random discs

We return to Example 4. Let V be the torus obtained by identifying the opposite sides of the square of area n, $[0, \sqrt{n}]^2\subset \mathbb{R}^2$ , and let X be the intersection of V with the disc of radius $r=r(n)$ about a uniformly chosen random point $x\in V$ . Draw a sequence $\mathbf{X} = (X_1, X_2, \ldots )$ of independent random subsets of V distributed according to X. When does their union w.h.p. cover V? This is known as a coverage problem, and is a continuous analogue of the coupon collector problem. Coverage problems have been widely studied in random geometric graph theory, with motivation coming from applications to wireless networks, especially sensor networks (see the introduction of [Reference Sarkar and Haenggi53] for a history of coverage problems).

We discretise the problem and apply our results to show sharp concentration of the covering time $T=T(\mathbf{X})$ in the case where r(n) is of order $o(\sqrt{n})$ and bounded away from 0 (so the measure of X is $O(\pi r^2)=o(n)$ ). Tile V with squares of side length s, where $s=s(r,n)$ is chosen so that $s=o(r)$ , $s=n^{o(1)}$ , and $\sqrt{n}/s \in \mathbb{N}$ . Let $\mathcal{T}$ denote the collection of all the tiles; by construction, $\vert \mathcal{T}\vert =n/s^2$ . Given a disc D of radius r in V, we define $I_{-}$ to be the collection of tiles wholly contained inside D, and $I_+$ to be the collection of tiles having non-empty intersection with D. The random variable X gives rise, via $I_-$ and $I_+$ , to two random variables $X_-$ and $X_+$ taking values among the subsets of $\mathcal{T}$ .

For any D as above, it is easy to show (see e.g. Lemma 8 of [Reference Falgas-Ravry and Walters18]) that the boundary of D meets at most $\frac{18\pi r} {s}$ tiles; thus $\vert I_-\vert$ and $\vert I_+ \vert$ are both within $\frac{18 \pi r}{s}$ of $\frac{\vert D\vert}{s^2}=\frac{\pi r^2 }{s^2}$ . Both of $X_-$ and $X_+$ are clearly balanced random covering variables for $\mathcal{T}$ .

By Part 3 of main Theorem 5 their covering times $T(\mathbf{X}_-)$ and $T(\mathbf{X}_+)$ are therefore w.h.p. concentrated around $\frac{\log (ns^{-2})}{-\log \left(1- \frac{\pi r^2}{n}\right)}=(1+o(1))\frac{n\log n}{\pi r^2}$ . Since by construction of the random variables $X_-$ and $X_+$ we have that $T(\mathbf{X}_-)\leq T(\mathbf{X}) \leq T(\mathbf{X}_+)$ , we deduce that w.h.p. the covering time for the torus V satisfies $T(\mathbf{X})={(1+o(1))\frac{n\log n}{\pi r^2}}$ .

It is easy to adapt the argument above to show that the covering time does not change significantly if instead of a torus we try to cover a square S of area n with discs of radius r centred at uniformly chosen random points in S. The random covering variables we use are no longer quite balanced: there are $O(\frac{r\sqrt{n}}{s^2})$ tiles within distance r of the boundary of S, each of which is covered with probability at least $\frac{\pi r^2}{2n}(1+o(1))$ , and $O(\frac{r^2}{s^2})$ tiles within distance r of a corner of S, each of which is covered with probability at least $\frac{\pi r^2}{4n}(1+o(1))$ . The first moment method shows both of these sets of ‘boundary tiles’ are w.h.p. covered by the time we have drawn $(1+\varepsilon)\frac{n \log n}{\pi r^2}$ discs, while the ‘central tiles’ at distance at least r from the boundary are w.h.p. covered by that time by our result for the torus. This yields the following well-known result on covering processes (see [Reference Hall25]).

As an example of how to apply Part 2 of Theorem 5, we can instead let the radius be a random variable R satisfying $F(r)\,:\!=\mathbb{P}(R\geq r) =\Theta(r^{-\alpha})$ (as $r\to \infty$ ) for some fixed $\alpha>0$ . We now want to show that for all but $n^{1+o(1)}$ pairs of tiles x, y, $q_{xy}/q_x = o(1/\log n)$ (uniformly in x and y).

A necessary condition for a disc C covering x to also cover y is that its radius is at least $d(x,y)/2$ . The distribution of the area of C, conditional on $x\in C$ , is the size-biased version of $\pi R^2$ . Hence

\begin{equation*}\mathbb{P}(\textrm{radius}(C)\geq r) = \Theta(r^2\mathbb{P}(R\geq r))=\Theta(r^{2-\alpha}),\end{equation*}

and it follows that $q_{xy}/q_x = O(d(x,y)^{2-\alpha})$ . If $\alpha = 2+\varepsilon$ for some $\varepsilon>0$ , then we can apply Part 2 of Theorem 5 with pairs x, y considered ‘bad’ if $d(x,y)<(\log n)^{2/\varepsilon}$ . For each x there are $O((\log n)^{4/\varepsilon})=n^{o(1)}$ y’s within that distance, and for x, y further apart $q_{xy}/q_x = O((\log n)^{-2})=o(1/\log n)$ . So the conditions of Part 2 are satisfied, and the cover time is concentrated around its mean. If on the other hand $\alpha \leq 2$ , the probability that $R>\sqrt{2n}$ (in which case that disc will cover the entire torus) is at least $\Omega(n^{-1})$ . This is analogous to Example 5 (coupon collector with lottery), and the cover time will not be sharply concentrated.

More generally, our argument for Theorem 11 in the torus adapts immediately to any balanced random covering variable X taking values among the compact subsets of V and satisfying with probability 1 the two conditions (1) $\vert X\vert \leq \varepsilon \vert V\vert$ and (2) $\vert \partial X \vert \leq \varepsilon \vert X\vert$ , where $\vert \partial X\vert$ denotes the measure (length) of the boundary of X, and $\varepsilon=o(1)$ . For such X, we again have

\begin{equation*}T(\mathbf{X}) =(1+o(1))\frac{\vert V\vert \log \vert V\vert }{\mathbb{E} \vert X\vert }.\end{equation*}

Thus we may replace ‘disc’ in the results above by e.g. ‘ellipse’, ‘annulus’, ‘square’, or ‘polygon’, or even let X be given by a probability distribution on a finite collection of shapes having the same Lebesgue measure and satisfying the required isoperimetric inequality. These are special cases of a celebrated result of Janson [Reference Janson31].

5.3. Covering the edges of a graph by spanning trees, and matroids by bases

Let G be a connected edge-transitive graph on n vertices, of minimum degree d, and let X be a spanning tree of G drawn uniformly at random from the set of all such trees. Our goal is now to cover the edge set E of G with the edges of trees from X.

It is well known that the random spanning tree is pairwise negatively correlated, with respect to the edges; in fact it satisfies the even stronger negative correlation property of being a Rayleigh measure on E (see [Reference Borcea, Brändén and Liggett8]).

So from Theorem 5 we can conclude that the covering time T is sharply concentrated around $ \frac{(nd/2) \log(nd/2)}{n-1} $ , as long as $d\gg 1$ .

Covering the edge set of a graph is a special case of the problem of covering the ground set of a matroid by randomly drawn bases of the matroid. In [Reference Feder and Mihail19] it was shown that a large class of matroids, the balanced matroids, which contain the class of cycle matroids of a graph, have pairwise negative correlation. In the same way as for trees we can conclude that if a balanced matroid of size n has rank r then the covering time T is sharply concentrated around $n \log(n)/r$ , as long as $\log(r)=o(\log(n))$ .

5.4. Random k-SAT

The random Boolean satisfiability (SAT) problem is the following. Given n Boolean variables $x_1, x_2, \ldots, x_n$ and an integer sequence $k=k(n)$ , we form a random clause $C=l_1\vee l_2 \vee \ldots \vee l_k$ by selecting a k-subset $\{y_1,y_2, \ldots, y_k\}$ of literals uniformly at random, setting $l_i=y_i$ with probability $\frac12$ and $l_i =\lnot y_i$ otherwise, independently for each i, and taking C to be the join of the literals $l_i$ . We now consider a sequence of i.i.d. random clauses $C_1, C_2, \ldots $ , with distribution given by C, and define a sequence of logical formulae in conjunctive normal form: $F_t= \bigwedge_{i=1}^t C_i$ for $t=0,1, \ldots$ . For $n\rightarrow \infty$ , the random k-SAT problem asks whether or not there exists w.h.p. an assignment of truth values to the variables $x_1, \ldots, x_n$ such that the logical formula $F_t$ is satisfied. The random k-SAT problem is of fundamental importance to theoretical computer science and has been extensively studied (see [Reference Coja-Oghlan11]).

Here we note that this problem is equivalent to determining the covering time of a coupon collector problem. The space of satisfying assignments for a formula consisting of t clauses involving n variables can be viewed as the complement of the union of t subcubes of $\{0,1\}^n$ . If each of those t clauses involves exactly k distinct literals (that is, if we are working with an instance of k-SAT), then each of those t subcubes has dimension $n-k$ . In particular, we can couple the sequence of i.i.d. clauses $C_1, C_2, \ldots$ with a sequence of independent coupons $X_1, X_2, \ldots $ , with $X_i \sim X$ , where X is the random coupon given by selecting an $(n-k)$ -dimensional subcube of the n-dimensional discrete hypercube $V=\{0,1\}^n$ uniformly at random. The formula $F_t$ is then satisfiable if and only if the X-coupon collector has failed to cover V by time t.

The random variable X is $2^{n-k}$ -uniform and transitive. Proposition 2 thus gives some elementary upper bounds on the satisfiability threshold $T(\mathbf{X})$ for $F_t$ : for any $\varepsilon>0$ , w.h.p.

\begin{equation*}T(\mathbf{X}) \leq (1+\varepsilon)\frac{\log 2^n }{-\log (1 -2^{-k})}= (1+\varepsilon) n \frac{\log 2}{-\log(1-2^{-k})} .\end{equation*}

For k(n) large enough this bound is in fact an equality, as first proven in [Reference Frieze and Wormald23]. Using Theorem 5 we can obtain the same result.

Proof. Let $N=2^n$ be the number of vertices in the hypercube $Q_n$ , our base set. To deduce the claimed sharp concentration result for $T(\mathbf{X})$ , we shall show that Condition 1 in Theorem 5 is satisfied. Checking that Condition 1 holds is a matter of simple computations. Most of the estimates needed here are standard so we only sketch the argument. We note first of all that in our setting, for any pair of vertices x and y at Hamming distance i in the hypercube $Q_n$ ,

\begin{equation*}q_{xy}=\frac{\binom{n-i}{k}}{2^k\binom{n}{k} }.\end{equation*}

By symmetry, Condition 1 is equivalent to

\begin{equation*}S=\sum_{y\neq 0} (\exp(tq_{0,y})-1) = o(N).\end{equation*}

Now the threshold for k-satisfiability we shall obtain from Theorem 5 (which is the first moment threshold) is $N\log N/ (N/2^k)=2^kn \log 2$ . We therefore let $t = 2^kn\log 2 \cdot(1- \delta_n)$ for some $\delta_n = o(1)$ to be determined later. Now

\begin{align*} S &=\sum_{y} [-1+ \exp(n\log 2 \cdot(1- \delta_n) \cdot 2^k q_{0,y})] \\ &=\sum_{i=1}^{n-k} \binom{n}{i} \left[-1+ \exp \Big(n\log 2 \cdot(1- \delta_n) \cdot \frac{\binom{n-i}{k}}{\binom{n}{k}} \Big) \right]. \end{align*}

Let $a_i$ be the ith term of this sum. We deal separately with the three cases $i\geq\frac{n}{2} - \frac{n}{k}$ , $\frac{n\ln k}{k-1}\leq i<\frac{n}{2} - \frac{n}{k}$ , and $i<\frac{n\ln k}{k-1}$ . In the first case, we change the summation index so that $i = \frac{n}{2}-j$ . Note that

\begin{equation*} \frac{\binom{n-i}{k}}{\binom{n}{k}} \leq \big(1-\frac{i}{n}\big)^k = 2^{-k}\big(1+\frac{2j}{n}\big)^k \leq 2^{-k}\exp\Big(\frac{2jk}{n}\Big). \end{equation*}

Summing over all j such that $-\frac{n}{2}\leq j<\frac{n}{k}$ we get that

\begin{align*} 2^{-n}\sum_{i= \frac{n}{2}-\frac{n}{k}}^{n-k} a_i &=2^{-n}\sum_{j=k-\frac{n}{2}}^{\frac{n}{k}} {\binom{n}{ \frac{n}{2}-j} } \left[-1+ \exp \Big(n\log(2) \cdot \frac{\binom{\frac{n}{2}-j }{k}}{\binom{n}{k}} \Big) \right] \\ &\leq -1+\exp(2^{-\omega(n)}e^{2}) = o(1).\end{align*}

In the second case a convexity argument shows that

\begin{equation*} 2^{-n} \sum_{i=\frac{n \ln k}{k-1}}^{\frac{n}{2}-\frac{n}{k}} a_i \leq \exp\Big(\log n -\frac{2n}{k^2}+o(1) \Big) = o(1). \end{equation*}

Finally, for $i \leq \frac{n\log k}{k-1}$ , coarser bounds suffice: ${\binom{n-i}{k}/\binom{n}{k} \leq 1}$ and $\log \binom{n}{i} \leq 2i \log(n/i)$ . Thus

\begin{align*} 2^{-n} \sum_{i=1}^{\frac{n \log k}{k-1}} a_i &\leq 2^{-n} \sum_{i=1}^{\frac{n \log k}{k-1}} \exp\Big(2i \log\big(\frac{n}{i}\big)+ n \log(2)(1-\delta_n) \Big) \\ &= n\exp\Big(n\Big[\frac{2\log(k)^2}{k}-\log(2)\delta_n\Big]\Big), \end{align*}

which is o(1) provided $\log(2) n\delta_n - \frac{2n\log(k)^2}{k} - \log(n) \to \infty$ ; this is satisfied for instance if we choose $\delta_n = (\log n)^{-\frac{1}{2}}$ .

Together these three cases and the choice of $\delta_n$ above give that $2^{-n}\sum_{i=1}^{n-k} a_i = o(1)$ , or in other words that $S=o(N)$ , and Condition 1 is satisfied (since $S=o(N)$ and $\sum_x e^{-q_x t} =e^{N\delta_n}=\omega(1)$ ). The result is then immediate from Theorem 5.

For constant k the simple first moment bound does not give the correct value for the satisfiability threshold. For $k=3$ our simple upper bound is $T(\mathbf{X})\leq\left(5.190\ldots +o(1)\right)n$ and it has been shown that $T(\mathbf{X})\leq 4.506n$ [Reference Dubois, Boufkhad and Mandler14]. Heuristics based on spin-glass theory have led to the conjecture that the correct threshold is $4.267\ldots n$ ; see [Reference Mézard and Zecchina43]. The well-known satisfiability conjecture states that for each k there exists a constant $c_k$ such that the threshold for random k-SAT is $c_k n$ . Recently a proof of this conjecture for sufficiently large values of k has been announced [Reference Ding, Sly and Sun13]. It is also known [Reference Coja-Oghlan11] that as k increases the threshold location scales as $2^k \ln 2-1/2 (1 + \ln 2) + o_k(1)$ , thus matching to leading order the bound given by the coupon collector.