Suppose we have two sets of discrete events, $A$ and $B$. Then I think it is true that:

$$2\sum_{i \in A, j \in B}\Pr[i\ \textrm{AND}\ j] \leq \sum_{i \in A}\Pr[i]+ \sum_{j \in B}\Pr[j] +\sum_{i, j \in A}\Pr[i\ \textrm{AND}\ j] + \sum_{i, j \in B}\Pr[i\ \textrm{AND}\ j]$$

My intuition for why this should be true is just by analogy to the simple Cauchy-Schwarz like inequality for $a, b \in \mathbb{R}:$ $$2ab \leq a + b + a(a-1) + b(b-1)$$ To see why this identity is true, note: $$a + b + a(a-1) + b(b-1) = a^2 + b^2 = 2ab + (a-b)^2 \geq 2ab$$

Is my inequality true, and is there a simple proof?

  • $\begingroup$ FYI, your notation is kind of odd. One usually uses capital letters for events, and usually calligraphic letters for sets of events, and set operations instead of logical operations. So I'd write the LHS as $2 \sum_{A \in \mathcal{A}, B \in \mathcal{B}} P(A \cap B)$. $\endgroup$ – Nate Eldredge Oct 24 '10 at 22:50

yes, if $\sum_{i,j\in A}$ means double summation (each pair $i,j$ is taken twice) then denote $f_i$ and $g_i$ characteristic functions of your events from $A$ and $B$ respectively, LHS equals $2 \sum \int f_i g_j=\int 2(\sum f_i)(\sum g_j)$, RHS equals $\sum \int f_i^2+\sum \int g_j^2+2\sum \int f_i f_j+2\sum \int g_i g_j=\int (\sum f_i)^2+(\sum g_j)^2$, and RHS-LHS equals $\int (\sum f_i-\sum g_j)^2\geq 0$.

  • $\begingroup$ I added a factor of 2 that was missed... $\endgroup$ – Nate Eldredge Oct 24 '10 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.