What is the meaning of this Sigma notation?

Question

This is from Probability and Statistics Fourth Edition by Mark J. Schervish and Mark J. Schervish pg.48.

$Pr(\bigcup\limits_{i=1}^{n}A_i) = \sum\limits_{i=1}^{n} Pr(A_i) - \sum\limits_{\bbox[yellow] {i<j}} Pr(A_i \cap A_j) + \sum\limits_{\bbox[yellow] {i<j<k}} Pr(A_i \cap A_j \cap A_k) - \sum\limits_{\bbox[yellow] {i<j<k<l}} Pr(A_i \cap A_j \cap A_k \cap A_l) + (-1)^{n+1}Pr(A_1 \cap A_2 \cap \ldots \cap A_n$

---

I don't understand the highlighted parts.

For instance:

$\sum\limits_{i<j<k} Pr(A_i \cap A_j \cap A_k)$

Does $k$ go from $3$ to $n$? and $j$ from $2$ to $n-1$? and $i$ from $1$ to $n-2$?
If I understand correctly, this is taking all $A$s three at a time, finding the intersection of each three, and adding up all the probabilities of those intersections, right?
Is this the usual notation? Is there a better way to write this?

Answer 1

It means summing over all the intersections, but without duplicates. So if $n=3$ then $\sum\limits_{ {i<j}} \Pr(A_i \cap A_j)$ means $\Pr(A_1 \cap A_2)+\Pr(A_1 \cap A_3)+\Pr(A_2 \cap A_3)$

You could rewrite $\sum\limits_{ {i<j<k}} Pr(A_i \cap A_j \cap A_k)$ as $\sum\limits_{ {i=1}}^{n-2}\sum\limits_{ {j=i+1}}^{n-1}\sum\limits_{ {k=j+1}}^{n} Pr(A_i \cap A_j \cap A_k)$ or as $\sum\limits_{ {k=3}}^{n}\sum\limits_{ {j=2}}^{k-1}\sum\limits_{ {i=1}}^{j-1} Pr(A_i \cap A_j \cap A_k)$ but some might say this was less immediately clear

Answer 2

The notation $\sum_{i<j}Pr(A_i\cap A_j)$ means $\sum_{(i,j)\in\{(i,j)\in I^2\mid i<j\}}Pr(A_i\cap A_j)$. That is, the sum over all pairs $(i,j)\in I\times I$ which satisfy $i < j$. Here $I=\{1,\dots,n\}$ which isn't implied by the notation but is inferred from context in your example from the first sum, $\sum_{i=1}^n Pr(A_i)$ which, for consistency, can be written $\sum_{i\in I}Pr(A_i)$. (For that matter, the union can be written $\bigcup_{i\in I}A_i$.)

The further sums are over all triples in $I^3$ satisfying the conditions, then all quadruples, and so forth.

Since it's somewhat redundant to use set builder notation just to immediately test for membership, I've seen notation like $\sum_{i,j:i<j}Pr(A_i\cap A_j)$. And, of course, what you started with compresses this further.

If you wanted to take a different perspective on it, you could view $\sum$ as taking a set of terms and write $\sum\{Pr(A_i\cap A_j)\mid i\in I,j\in I, i < j\}$.

Answer 3

Interpreting $\sum_{i<j} P(A_i\cap A_j)$

The indices goes from $i$ to $n$ and $j$ to $n$, but only where $i<j$.

The indices can be represented in a table ($n=4$):

$$\begin{array}{|c|c|}\hline i/j&1&2&3&4 \\ \hline 1& & x& x&x \\ \hline 2& & &x &x \\ \hline 3& & & & x \\ \hline 4& & & & \hline \end{array}$$

So the number of summands is $6$

For an arbitrary $n$ the closed formula for the number of summands is

$$s(n)=\frac{n}2\cdot (n-1)$$

You just substract n cells (blank diagonal) from the total number of the cells: $n\cdot n-n$. Then you divide the result by 2. You get the number of cells above the diagonal.

In case of $n=4$ we get $s(n)=\frac{4}2\cdot (3)=2\cdot 3=6$

Consequently $\sum_{i<j}^4 P(A_i\cap A_j)$

$$=P(A_1\cap A_2)+P(A_1\cap A_3)+P(A_1\cap A_4)+P(A_2\cap A_3)+P(A_2\cap A_4)+P(A_3\cap A_4)$$