Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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)$. –  Nate Eldredge Oct 24 '10 at 22:50
add comment

1 Answer

up vote 2 down vote accepted

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$.

share|improve this answer
    
I added a factor of 2 that was missed... –  Nate Eldredge Oct 24 '10 at 22:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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