MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer
I added a factor of 2 that was missed... – Nate Eldredge Oct 24 '10 at 22:48

Your Answer


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.