The size of the cover $\tilde x$ is inevitably $N$, because each of the $N$ samples increases the size by 1. Next we bound the coverage.

Fix any element $e\in U$. With each of the $N$ samples, the probability that the sampled set contains $e$ is $\sum _{s\ni e} x_s /|x|$, which, since $x$ has minimum coverage $C$, is at least $C/|x|$. Thus, the expectation of $\tilde x(s)$ is at least $N\cdot C/|x| \ge C/(1-\varepsilon )$.

Consider $\tilde x(s)$ as the sum $\sum _{t=1}^N [e \in s_t]$ of $N$ independent random indicator variables (the $t$th of which is 1 the $t$th sampled set $s_t$ contains $e$, and zero otherwise). By the Chernoff bound, the probability that $\tilde x(e)$ is less than $C=(1-\varepsilon ) C/(1-\varepsilon )$ is less than

(The inequality follows from the assumption on $C$.)

Thus, the expected number of elements $e$ with $\tilde x(e) \lt C$ is less than 1. So, with positive probability, $\tilde x$ has minimum coverage at least $C$.

Say that an element $e$ is “undercovered” (when the rounding scheme finishes) if $\tilde x(e) \lt C$. The algorithm will emulate the rounding scheme, but instead of choosing each set $s$ randomly, it will choose each set so as to keep the conditional expectation of the number of undercovered elements below 1.

Recall that $s_t$ is the $t$th sampled set. In using the Chernoff bound for each element, the analysis of the rounding scheme implicitly bounds the number of undercovered elements by

then shows the expectation of $\Phi$ is at most 1.

(To understand where $\Phi$ comes from requires a good understanding of the proof of the Chernoff bound. Here are the essentials. For each undercovered element $e$, the term for $e$ in the sum is at least 1, so the number of undercovered elements is at most $\Phi$. The proof of the Chernoff bound shows that the expectation of the term for each $e$ in $\Phi$ is less than $\exp (-\varepsilon ^2 (C/(1-\varepsilon ))/ 2)$. By the assumption on $C$ in the analysis of the rounding scheme, this is at most $1/n$, so the expectation of $\Phi$ is less than 1.)

Since $\Phi$ is an upper bound on the number of undercovered elements, to keep the conditional expectation of the number of undercovered elements below 1, it suffices to keep the conditional expectation of $\Phi$ below 1. This is what the algorithm will do.

Fix any $t\in \{ 0,1,\ldots ,N\}$. Recall that, for any element $e$, $\Pr [e\in s_t] \ge C/|x|$. One pessimistic estimator for the conditional expectation of $\Phi$, given the first $t$ elements, is

To reach a successful outcome, it suffices for the algorithm to choose each element to ensure that $\phi _t$ does not increase, so that $\Phi = \phi _N \le \phi _{N-1} \le \cdots \le \phi _0 \lt 1$. How can it choose $e_{t+1}$ to ensure $\phi _{t+1} \le \phi _t$? Letting $\omega ^s_t$ denote the term for $s$ in $\phi _t$ (so $\phi _t = \sum _s \omega ^s_t$) if the algorithm takes some set $s$ to be $s_{t+1}$, then

If $s$ were chosen randomly as in the sampling scheme, then (for any element $e$), $\Pr [e\in s] \ge C/|x|$, so (by inspection above) the expectation of $\phi _{t+1}$ would be at most $\phi _t$.

So, to ensure $\phi _{t+1}\le \phi _t$, it suffices to choose $s$ to minimize $\phi _{t+1}$. Inspecting (\ref{eq:1}), the second product in the numerator, and the denominator, can be ignored (not only are they the same for all elements $e$, they are also independent of all choices so far). By calculation (factoring the irrelevant terms out and simplifying), choosing set $s$ minimizes $\phi '_{t+1}$ if and only if it maximizes

where $\tilde x$ denotes the cover at the start of the iteration. Thus, the algorithm at the top chooses each element to minimize the pessimistic estimator. This keeps the pessimistic estimator from increasing, ensuring a successful outcome.

Finally, note that to do this, the algorithm does not need to know $x$, yet is guaranteed to do as well as the rounding scheme for any $x$. This proves the theorem.