1
$\begingroup$

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

I don't have a proof for the more complex identity though. Is it true? Why does it hold?

  • 0
    I am finding this difficult to parse: what are the events here? Also is there some independence assumed?2010-10-24
  • 0
    $A$ and $B$ are two sets of events -- the events are $i \in A \cup B$. The events are not necessarily independent, however.2010-10-24

1 Answers 1

2

If I've understood your notation, $A$ and $B$ are index sets of events denoted $i,j$ etc.

The inequality $2ab\leq a^2+b^2$ applied to the sums $a:=\sum_{i\in A}1_i$ and $b:=\sum_{j\in B}1_j$ of indicator functions, followed by integration, gives

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

which is stronger than what you asked for.