# analog of principle of inclusion-exclusion

When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some students to draw the analogy between the two concepts implied by the following pair of statements:

• To compute the probability of the union of disjoint events, you add the probabilities of the events.

• To compute the probability of the intersection of independent events, you multiply the probabilities of the events.

I also teach them is that when events are not disjoint, you can still compute the probability of their union by applying the principle of inclusion-exclusion. Hence the question: Is there a useful analog of the principle of inclusion-exclusion for computing the probability of the intersection of non-independent events?

Edit: I am incorporating the following clarification that I made in a comment responding to the answer of Anna Varvak:

In inclusion-exclusion, one alternately adds and subtracts intersections. Intersections measure the degree to which disjointness fails. Can we write the right-hand side of Bayes Theorem as alternate multiplications and divisions of something, where "something" measures the degree to which independence fails?

Sounds like Bayes Theorem, which in its intuitive form is

P(A and B) = P(A) * P(B, given A) = P(B) * P(A, given B)

This really is quite intuitive, and I find that students understand it quite easily: for both A and B to happen, we can describe it in two ways: either A happens and then B happens (given that A happened), or B happens and then A happens (given that B happened).

For more than two events, there's the extended Bayes theorem:

P(A and B and C) = P(A) * P(B, given A) * P(C, given A and B)

• This certainly works. I suppose what I was looking for was something in which the symmetry between A, B, and C was more manifest on the right-hand side. Of course I realize the symmetry really is still there. – Will Orrick Oct 20 '09 at 1:54
• To elaborate a little bit more: In inclusion-exclusion, one alternately adds and subtracts intersections. Intersections measure the degree to which disjointness fails. Can we write the right-hand side of Bayes Theorem as alternate multiplications and divisions of something, where "something" measures the degree to which independence fails. – Will Orrick Oct 20 '09 at 2:15
• One last comment: This wasn't intended as a pedagogical question. Clearly the students need to learn about Bayes theorem. I was more interested in trying to formulate the analogy between disjointness and independence more completely for my own benefit. – Will Orrick Oct 20 '09 at 2:32

I suppose one attempt would be to just reverse the inclusion-exclusion equation.

Since P(A union B) = P(A) + P(B) - P(A intersect B) we also have

P(A intersect B) = P(A) + P(B) - P(A union B)

Of course, that totally ignores the analogy you want to make between disjointness and independence.

Maybe I can try to reverse-engineer something. Let P(A intersect B) = P(A)P(B)/f(A,B), where f is the function giving the unknown factor. We see that f(A,B)=P(A)P(B)/P(A intersect B).

For the three-variable case we have P(A intersect B intersect C) = P(A)P(B)P(C) divided by (f(A,B)f(A,C)f(B,C) times g(A,B,C). Plugging in the formula for f(A,B), we see that

P(A intersect B intersect C) = P(A intersect B)P(A intersect C)P(B intersect C) divided by (P(A)P(B)P(C)) times g(A,B,C). So g is the three-way intersection times the individual probabilities, divided by the two-way intersections.

I must admit, I don't see any interesting pattern developing here with f and g, the way I did in the inclusion-exclusion case, but maybe someone else does?

• Thanks for the suggestion. The generalization of f(A,B) and g(A,B,C) is the product of all intersections of an odd number of events divided by the product of all intersections of an even number of events. According to Wikipedia, -log f(A,B) is called the pointwise mutual information. I haven't been able to find out whether g(A,B,C), etc. have names. – Will Orrick Oct 21 '09 at 2:07

Writing B \ A for the event "B occurs but A does not" (as in the difference of sets) we have...

P(A ∪ B) = P(A) + P(B \ A)

P(A ∩ B) = P(A) × P(B | A)

Just fun with symbols I think...

• Cute! And the generalization to the case of more than two events is clearly analogous to the extended Bayes Theorem. I'm still not completely satisfied, however. For the case of k events, your rule/extended Bayes Theorem has k terms/factors on the right-hand side. Inclusion-exclusion, on the other hand has 2^k-1 terms. – Will Orrick Oct 20 '09 at 3:34

In belief propagation there is a notion of inclusion-exclusion for computing the join probability distributions of a set of variables, from a set of factors or marginals over subsets of those variables. For example, suppose {X,Y,Z} is your set of variables, and you know the marginal probabilities for pX,Y(x,y) and pY,Z(y,z). If these two are compatible, then the marginal pY can be computed in either of the ways

pY(y) = integral pX,Y(x,y) dx = integral pY,Z(y,z) dz

Then a maximum entropy guess at the full joint distrubution is given by inclusion-exclusion over subsets of variables

pX,Y,Z(x,y,z) = pX,Y(x,y) pY,Z(x,y) / pY(y)

You might take a look at "Belief propagation" on wikipedia, or the more techinical article "Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms" by Yedidia, Freeman and Weiss, which uses inclusion-exclusion in the form of 'counting numbers'.

• Thanks for the references. I will certainly take a look at them. Just a few quick impressions: If I understand correctly, the maximum entropy guess is equivalent to the hypothesis that the conditional probabilities P(X=x|Y=y) and P(Z=z|Y=y) are independent. This suggests that if one knew there were some dependency one would have to adjust accordingly, and it is this sort of adjustment that I would count as an inclusion-exclusion type principle. It may be that in practice one seldom has a good enough handle on the dependencies to make such a procedure useful. – Will Orrick Oct 27 '09 at 14:49

Inclusion-exclusion doesn't depend on independence. You want

P(A union B) = P(A) + P(B) - P(A intersect B).

Now, P(A intersect B) is P(A) P(B) if A and B are independent. But that holds even if A and B aren't independent. You might rewrite it as

P(A union B) = P(A) + P(B) - P(A) P(B|A)

if your students are okay with conditional probability.

• P(A union B) = P(A) + P(B) - P(A intersect B) looks to me like the statement of the usual principle of inclusion-exclusion (for two events). I hope the edited question makes it clearer what sort of analog I was looking for. – Will Orrick Oct 26 '09 at 0:55

I'll take a stab at answering my own question.

The missing “something” in the edited version of my question appears to be the mutual information of one or more events, denoted $$I(A,B,C,...)$$. More precisely, it appears to be the quantity $$e^{-I(A,B,C,...)}$$. It would be good if someone knowledgeable about information theory could weigh in here—I haven't found a definition in the literature of the mutual information of more than two events, but the one I give below seems to be the “right” one.

In the information theory textbooks I looked at, the information of a single event E is defined as I(E) = −log P(E). The mutual information of two events, E and F, is defined as $$I(E,F) = -\log \frac{P(E) P(F)}{P(E\cap F)}$$, and is a measure of the degree to which E and F fail to be independent. That is, $$I(E,F)$$ is zero if E and F are independent, positive if they are positively correlated, and negative if they are negatively correlated.

The appropriate generalization to three events seems (following the suggestion of Kenny Easwaran) to be $$\displaystyle I(E,F,G) = -\log \frac{P(E) P(F) P(G) P(E \cap F \cap G)}{P(E\cap F) P(E \cap G) P(F \cap G)}$$ which makes some sense as a measure of the failure of independence since, in order for E, F, and G to be independent, it is required, not only that P(A ∩ B) = Pr(A) P(B) for all pairs of events, but also that P(E ∩ F ∩ G) = P(E) P(F) P(G). (Does anyone know if the definition of I(E,F,G) given above is standard?)

Now define C({A,B,C,...}) = P(A ∩ B ∩ C ∩ ...). The appropriate generalization of the mutual information to an arbitrary number of events seems to be I(E,F,G,...) = −log [ΠS C(S) / ΠT C(T)] where the product over S runs over all subsets of {E,F,G,...} of odd cardinality and the product over T runs over all subsets of {E,F,G,...} of even cardinality. (Again, does anyone know if this definition is standard?)

With these definitions, we get the inclusion-exclusion-like rule,

−log P(E ∩ F ∩ G ∩ ...) = I(E) + I(F) + I(G) + ... − I(E,F) − I(E,G) − ... + I(E,F,G) + ... − ...

This can be proved by a counting argument identical to the one used to prove the principle of inclusion-exclusion. Negating and exponentiating both sides produces an identity of the desired form. It would be nice to also find a Möbius-inversion style proof.

As to whether this is “useful” in the same sense that the principle of inclusion-exclusion is useful, I can't say. The definition of I(E,F,G,...) is itself an inclusion-exclusion-like rule, so it's tautological that when you invert it to find −log P(E ∩ F ∩ G ∩ ...) you will get an inclusion-exclusion-like rule. I suppose the significance of all this depends on how fundamental the mutual information is.

Addendum: The book Elements of Information Theory by Cover and Thomas mentions the problem of defining the mutual information of three random variables in Problem 2.25. The mutual information of random variables is related to but somewhat different from the mutual information of events since, for example, I(X,Y,Z) involves taking the expectation over all events (X=x, Y=y, Z=z). The problem notes that, in contrast with the two random variable case, the mutual information of three random variables is not a non-negative quantity in general. This perhaps explains why not much theory has been developed around it. Interestingly, however, the mutual information of three random variables can be expressed in terms of the entropy of one, two, or three random variables via the inclusion-exclusion principle.

• The notation is confusing and looks wrong. For example, you say $I(E) = −\log P(E)$. What is $P$ the probability? The conventional definition of entropy $I(X)=-\sum_{x\in X(\Omega)} P(x)\ln P(x)$ for a random variable $X$. How does your definition reconcile with the conventional one? – Hans Jan 15 at 8:22
• @Hans It's been a while since I thought about this, but, yes, $P$ does represent the probability. The distinction is that I am speaking of the information content of an event rather than of a random variable. Perhaps it would have been clearer if I had stuck with the term "pointwise mutual information", which I used in my comment to Kenny Easwaran's answer, instead of dropping the adjective "pointwise", but many books do the same. The information content of a single event is sometimes referred to as "self information". – Will Orrick Jan 15 at 19:47