TransWikia.com

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

Mathematics Asked on November 9, 2021

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} Pleft{A_{i}right} .$ Then :
$$ left(1-Pleft(bigcup_{k=1}^{n} A_{k}right)right)^{2} sum_{i=1}^{n} Pleft{A_{i}right} leq c Pleft(bigcup_{k=1}^{n} A_{k}right)$$

Proof :

First off, set :
$$A =bigcup_{k=1}^{n} A_{k},,, beta=1-Pleft(Aright)$$

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} Pleft(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)\
= Eleft[sum_{j=1}^n (I_{A_j} – P(A_j))I_A)right] + sum_{j=1}^n P(A_j)(1-beta) \
=Eleft{sum_{j=1}^{n}left(I_{A_{j}}-Pleft(A_{j}right)right) I(bigcup_{i=1}^{n} A_{i})right}+sum_{j=1}^{n} Pleft(A_{j}right)(1-beta) \
leqleft(operatorname{Var}left(sum_{j=1}^{n} I_{A_{j}}right) Pleft(bigcup_{j=1}^{n} A_{j}right)right)^{1 / 2}+sum_{j=1}^{n} Pleft(A_{j}right)(1-beta) \
leqleft(cleft(sum_{j=1}^{n} Pleft(A_{j}right)right) Pleft(bigcup_{j=1}^{n} A_{j}right)right)^{1 / 2}+sum_{j=1}^{n} Pleft(A_{j}right)(1-beta) \
color{red}{leq frac{c}{2 beta} Pleft(bigcup_{j=1}^{n} A_{j}right)+left(frac{beta}{2}+1-betaright) sum_{j=1}^{n} Pleft(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 !

2 Answers

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.

Answered by stochasticboy321 on November 9, 2021

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.

Answered by E-A on November 9, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP