Need help understanding the last step of the proof of this lemma involving probabilities

Question

Lemma :

Suppose that the events $A_{1}, \ldots, A_{n}$ satisfy $\operatorname{Var}\left(\sum_{i=1}^{n} I_{A_{i}}\right) \leq c \sum_{i=1}^{n} P\left\{A_{i}\right\} .$ Then : $$ \left(1-P\left(\bigcup_{k=1}^{n} A_{k}\right)\right)^{2} \sum_{i=1}^{n} P\left\{A_{i}\right\} \leq c P\left(\bigcup_{k=1}^{n} A_{k}\right)$$

Proof :

First off, set : $$A =\bigcup_{k=1}^{n} A_{k},\,\, \beta=1-P\left(A\right)$$

Without loss of generality, we can assume that $\beta > 0$, if $\beta = 0$ then the inequality holds trivially. Note that $A_i \subset A$ for each $i = 1, ..., n$, so $I_{A_i} I_A = I_A$. Also, $1 - \beta = P(A)$.

\begin{multline*} \sum_{j=1}^{n} P\left(A_{j}\right) =(1-P(A)) \sum_{j=1}^nP(A_j) + P(A)\sum_{j=1}^n P(A_j) \\ = \sum_{j=1}^n \left[P(A_j) - P(A_j)P(A)\right] + P(A)\sum_{j=1}^n P(A_j)\\ = \sum_{j=1}^n E[I_{A_j}I_A - P(A_j)I_A)] + P(A)\sum_{j=1}^n P(A_j)\\ = E\left[\sum_{j=1}^n (I_{A_j} - P(A_j))I_A)\right] + \sum_{j=1}^n P(A_j)(1-\beta) \\ =E\left\{\sum_{j=1}^{n}\left(I_{A_{j}}-P\left(A_{j}\right)\right) I(\bigcup_{i=1}^{n} A_{i})\right\}+\sum_{j=1}^{n} P\left(A_{j}\right)(1-\beta) \\ \leq\left(\operatorname{Var}\left(\sum_{j=1}^{n} I_{A_{j}}\right) P\left(\bigcup_{j=1}^{n} A_{j}\right)\right)^{1 / 2}+\sum_{j=1}^{n} P\left(A_{j}\right)(1-\beta) \\ \leq\left(c\left(\sum_{j=1}^{n} P\left(A_{j}\right)\right) P\left(\bigcup_{j=1}^{n} A_{j}\right)\right)^{1 / 2}+\sum_{j=1}^{n} P\left(A_{j}\right)(1-\beta) \\ \color{red}{\leq \frac{c}{2 \beta} P\left(\bigcup_{j=1}^{n} A_{j}\right)+\left(\frac{\beta}{2}+1-\beta\right) \sum_{j=1}^{n} P\left(A_{j}\right)}\\ \end{multline*}

I understand they used the property $EI_A= P(A)$, the main assumption and Cauchy-Schwarz inequality to reach the before the last one step, but I can't seem to figure how they went from that one to the last one (in red), any help will be greatly appreciated, thanks !

Answer 1

This is a special case of Young's inequality, which states that for any constant $a > 0$,

$$ xy \leq \frac{x^2}{2a} + a \frac{y^2}{2}, $$

so if you use it on your product inside the paranthesis with $x = \sqrt{c \sum_j P(A_j)} , y = \sqrt{P(A)}$, and $a = \beta$, you can move to the last line.

Answer 2

The inequality follows by the AM-GM inequality - for $u,v \ge 0,x > 0,$ $$ \frac{ux}{2} + \frac{v}{2x} \ge \sqrt{uv}.$$ Now set $x = 1/\beta, u = cP(A), v = \sum P(A_j)$.

I certainly don't find this the cleanest way to show the result, btw. Indeed, the inequality before the red can be rearranged to $$ \beta \sum P(A_j) \le \sqrt{c(\sum P(A_j)) P(A)}\iff \beta^2 \sum P(A_j) \le c P(A)$$

which is a lot simpler in that it remains purely mechanistic and doesn't introduce a relation that requires thought.

However, this trick of replacing square roots by a sum via the AM-GM relation is often useful, and thus worth remembering. More generally, the idea is to replace a function by a variational definition of the same function, and then to choose a convenient point at which to evaluate the objective of this to get a upper/lower bound as appropriate. At times this can simplify computations without losing too much accuracy.