Covering a probability space with a sequence of sets

Question

Let $E_n$ be a sequence of events with $\inf_n {\bf P}(E_n) = \delta > 0$. I need to demonstrate that the lower bound $$\mathop{\bf P}\left( \sum_{n \leq N} 1_{E_n} \geq \delta \frac{N}{2} \right) \geq \delta/2$$ holds for all $N\in\mathbb{N}$.

I have tried several tricks. Intuitively/geometrically, I understand this assertion fully. For instance, if $E_n$ are disjoint, then at least $[1/\delta]$ sets of them ought to intersect somewhere; hence the inequality. I have tried to attack the problem from several angles, for instance

• for the integer $K=[\delta N/2]$ \begin{align} \mathop{\bf P}\left( \sum_{n=1}^{N} 1_{E_n} \geq \delta \frac{N}{2} \right) &= \mathop{\bf P}\left( \sum_{n=1}^{N} 1_{E_n} \geq K \right) = \sum_{k=K}^{N}\mathop{\bf P}\left( \sum_{n=1}^{N} 1_{E_n} = k \right)\\ &= \sum_{k=K}^{N} \sum_{p \in \{P\subseteq\{1,\ldots,N\}\mid|P|=k\}}\mathop{\bf P}\left( \bigcap_{i\in p} \{1_{E_i} = k\} \right) \end{align}
• I also have tried induction, i.e., under the induction hypothesis $$\mathop{\bf P}\left( \sum_{n=1}^{N+1} 1_{E_n} \geq \delta \frac{N+1}{2} \right) =\\ \mathop{\bf P}\left( \sum_{n=1}^{N} 1_{E_n} \geq \delta \frac{N+1}{2} \right) + \mathop{\bf P}\left( \{\sum_{n=1}^{N} 1_{E_n} < \delta \frac{N}{2} \} \text{ and } \{1_{E_{N+1}}=1\} \right)$$

I have tried approaching the problem from several other angles but nothing brings me anywhere.

Answer 1

This is an application of “Reverse Markov Inequality”.

Let $$X_N:=\frac1N\sum_{n\le N}\mathbf1_{E_n}.$$ Then $\mathbf E\,X_N=\delta$ and, because $X_N\le1$, $$\mathbf P\!\left(X_N\le\frac\delta2\right)=\mathbf P\!\left(1-X_N\ge1-\frac\delta2\right)\le\frac{\mathbf E[1-X_N]}{1-\frac\delta2}=\frac{1-\delta}{1-\frac\delta2}=1-\frac{\delta}{2-\delta},$$ where we applied the classical Markov inequality. Hence $$\mathbf P\!\left(X_N>\frac\delta2\right)=1-\mathbf P\!\left(X_N\le\frac\delta2\right)\ge\frac\delta{2-\delta}\ge\frac\delta2.$$

Answer 2

Prove by contradiction. Suppose the contrary that there exists $N\in\mathbb{N}$ such that the proposition is false. Define $X=\sum_{n=1}^{N}1_{E_{n}}$, then $P(X\geq\frac{N\delta}{2})<\frac{\delta}{2}$.

Since $X$ is non-negative, for any $p\geq1$, we have that $$ E\left[X^{p}\right]=\int_{0}^{\infty}px^{p-1}P(X\geq x)dx. $$ The above is known as Robin identity and can be proved by Fubini Theorem. Note that $P(X\geq x)=0$ for any $x>N$ and $P(X\geq x)\leq P(X\geq\frac{N\delta}{2})<\frac{\delta}{2}$ for any $x\in[\frac{N\delta}{2},N]$, so we have \begin{eqnarray*} E[X] & = & \int_{0}^{\infty}P(X\geq x)dx\\ & = & \int_{0}^{N}P(X\geq x)dx\\ & = & \int_{0}^{\frac{N\delta}{2}}P(X\geq x)dx+\int_{\frac{N\delta}{2}}^{N}P(X\geq x)dx\\ & \leq & \frac{N\delta}{2}\cdot1+\frac{\delta}{2}(N-\frac{N\delta}{2})\\ & = & N\delta-\frac{N\delta^{2}}{4}. \end{eqnarray*} On the other hand, $E[X]=\sum_{n=1}^{N}P(E_{n})\geq N\delta$. Hence, we obtain $N\delta\leq E[X]\leq N\delta-\frac{N\delta^{2}}{4}$, which is a contradiction.