Let C denote any cover of minimal size. Let S_{i} denote the contents of S after completing the i th iteration of the loop. Prove that, for all i \geq 0,
\mathbf{E}\left[\left|S_{i} \cap C\right|\right] \geq \mathbf{E}\left[\left|S_{i} \backslash C\right|\right]