analog of principle of inclusion-exclusion - MathOverflow

analog of principle of inclusion-exclusion

2009-10-20T01:27:13Z

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?

Answer by Michael Lugo for analog of principle of inclusion-exclusion

2009-10-20T01:39:53Z

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.

Answer by Anna Varvak for analog of principle of inclusion-exclusion

2009-10-20T01:42:36Z

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)

Answer by Reid Barton for analog of principle of inclusion-exclusion

2009-10-20T02:39:43Z

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

Answer by Kenny Easwaran for analog of principle of inclusion-exclusion

2009-10-20T07:42:26Z

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?

Answer by Will Orrick for analog of principle of inclusion-exclusion

2009-10-24T15:28:11Z

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 [P(E) P(F) / P(E ∩ 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 I(E,F,G) = −log [P(E) P(F) P(G) P(E ∩ F ∩ G) / P(E ∩ F) P(E ∩ G) P(F ∩ 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.

Answer by Fritz for analog of principle of inclusion-exclusion

2009-10-26T17:05:30Z

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 p_X,Y(x,y) and p_Y,Z(y,z). If these two are compatible, then the marginal p_Y can be computed in either of the ways

p_Y(y) = integral p_X,Y(x,y) dx = integral p_Y,Z(y,z) dz

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

p_X,Y,Z(x,y,z) = p_X,Y(x,y) p_Y,Z(x,y) / p_Y(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'.