Consider a state space in which the area, volume or hypervolume is proportional to the probability of events contained in the subset of space. This is easiest to visualize in the case of n=3, where the Venn diagram's 8 regions (bounded, so as to delimit even the null area) can be made proportional in area to the probability of each combination of events, say A(1) AND A(2) AND NOT A(3), or the outside, NOT A(1) AND NOT A(2) AND NOT A(3).
In the case of n=3, represented by the Venn diagram, for ease of discussion, call A(1), A; A(2), B; and A(3), C. We need to show that the central area, A AND B AND C is counted exactly once by the formula, and that for each other area, the adding in and subtracting out exactly cancel and add zero net to the total.
The central area is initially counted three times as it is included in P(A), P(B) and P(C). It is then subtracted out three times in P(A OR B), P(A OR C), P(B OR C). It is then added back in once in P(A OR B OR C). The net is it is counted once.
Now we only need to show that on net, none of the other areas is counted at all in the formula:
For pairwise, consider the area of A AND B AND NOT C. That area is counted twice initially as P(A) and again in P(B). But then it is subtracted out three times as it is included in P(A OR B), P(A OR C) and in P(B OR C). It is then added in once again as P(A OR B OR C). Thus it is added in a total of three times and subtracted out a total of three times. Similarly for the other ANDed pairs.
The areas that contain only a single occurrence, such as A AND NOT B AND NOT C, are added in once as P(A), subtracted out twice as P(A OR B) and P(A OR C), and added back in as P(A OR B OR C), thus adding in twice to balance out being subtracted out twice. Similarly for the other two events.
The area NOT A AND NOT B AND NOT C is not counted at all in the formula. QED.
The case of n=10 is of course more complicated. The central area, of A(1) AND A(2) AND...AND A(10), is counted in 10 times as P(A(1)) through P(A(10)). It is subtracted out 10C2 times, and added in 10C3 times, and subtracted out 10C4 times, etc. To sum up it is 10C1 - 10C2 + 10C3 - 10C4 + 10C5 - 10C6 + 10C7 - 10C8 + 10C9 - 10C10 + 10C0, where nCr is the combinations of n taken r at a time. We see that the 10C10 cancels out the 10C1, the 10C9 cancels out the 10C1, etc. as they are oppositely signed but equal in absolute value to their partner. The only one left is 10C1 = 1 time that this area is counted on net.
The pairwise ANDed areas are more complicated as they involve not only the probabilities of themselves but probabilities that include other than themselves: for example, the area that represents A(1) AND A(2) but not any of the others A(3) through A(10), is counted by A(1) OR A(2), and also by A(1) OR A(3), but not by A(3) OR A(4), for example. In fact the net times that that area is included is 2C1 - (2C2+2C1*8C1) + (8C1+2C1*8C2) - (8C2+2C1*8C3) + (8C3+2C1*8C4) - (8C4+2C1*8C5) + ... - (8C8+2C1*8C9), with 8C9 being zero. The rationale for one of these terms, say (8C2 + 2C1*8C3), is that in quadruple ORed sets A(1) OR A(2) OR A(i) OR A(j) will have 8C2 representatives (the i and j out of the remaining 8), while A(1) and A(2) can each be joined individually with 8C3 triplets drawn from the remaining 8. The total of this formula is 2-(1+2*8)+(8+2*28)-(28+2*56)+(56+2*70)-(70+2*56)+(56+2*28)-(28+2*8)+(8+2*1)-(1+0), which indeed comes out to zero.
The other areas on the multi-dimensional Venn diagram, containing two positive and eight negative events similarly count to zero.
The triples of events get more complicated still: Each is counted 3C1 = 3 times in the single event total, and is subtracted out (3C2+3C1*7C1) of the pairwise ORed totals, as they appear doubly in 3C2 compound events and in 3C1*7C1 where one of the three is paired with any one from the other seven. In the triples there is an additional term to be added: (3C3+3C2*7C1+3C1*7C2), as we can choose all three from the given set of three (in 3C3 = 1) way, or two from the three with one from the remaining seven (in 3C2*7C3 ways), or one from the set of three with 2 from the remaining seven (in 3C1*7C2 ways). From here on, the terms look similar to the third through tenth of the doublet terms, and we can write the remaining sum as Sigma{i=4 to 10} (-1)^(i-1)*(7C(i-3)+3C2*7C(i-2)+3C1*7C(i-1)). In fact, we can consider the entire sum as Sigma{i=1 to 10} (-1)^(i-1)*(7C(i-3)+3C2*7C(i-2)+3C1*7C(i-1)), if we consider 7C(-2) and 7C(-1) to be zero. This summation comes out to (0+0+3*1)-(0+3*1+3*7)+(1+3*7+3*21)-(7+3*21+3*35)+(21+3*35+3*35)-(35+3*35+3*21)+(35+3*21+3*7)-(21+3*7+3*1)+(7+3*1+0)-(1+0+0)=0.
We can see as we consider volumes in the Venn diagram that contain the overlap of r positive areas, with 10-r negative areas, such as A(1)...A(r), ~A(r+1),...,~A(10), the sum of their probabilities per the formula to be proved, is Sigma{i=1 to 10} (-1)^(i-1) Sigma{j=1 to r}(rCj*(10-r)C(i-j)). For quadruples this comes out to (4*1+0+0+0)-(4*6+6*1+0+0)+(4*15+6*6+4*1+0)-(4*20+6*15+4*6+1*1)+(4*15+6*20+4*15+1*6)-(4*6+6*15+4*20+1*15)+(4*1+6*6+4*15+1*20)-(0+6*1+4*6+1*15)+(0+0+4*1+1*6)-(0+0+0+1*1)=0
This formula does in fact produce 1 in the case of r = 10, and zero for all other r, proving the case for n = 10.
(1*1)-(1*9)+(1*36)-(1*84)+(1*126)-(1*126)+(1*84)-(1*36)+(1*9)-(1*1)=0
(2*1+0)-(2*8+1*1)+(2*28+1*8)-(2*56+1*28)+(2*70+1*56)-(2*56+1*70)+(2*28+1*56)-(2*8+1*28)+(2*1+1*8)-(0+1*1)=0
(3*1+0+0)-(3*7+3*1+0)+(3*21+3*7+1*1)-(3*35+3*21+1*7)+(3*35+3*35+1*21)-(3*21+3*35+1*35)+(3*7+3*21+1*35)-(3*1+3*7+1*21)+(0+3*1+1*7)-(0+0+1*1)=0
(4*1+0+0+0)-(4*6+6*1+0+0)+(4*15+6*6+4*1+0)-(4*20+6*15+4*6+1*1)+(4*15+6*20+4*15+1*6)-(4*6+6*15+4*20+1*15)+(4*1+6*6+4*15+1*20)-(0+6*1+4*6+1*15)+(0+0+4*1+1*6)-(0+0+0+1*1)=0
(5*1+0+0+0+0)-(5*5+10*1+0+0+0)+(5*10+10*5+10*1+0+0)-(5*10+10*10+10*5+5*1+0)+(5*5+10*10+10*10+5*5+1*1)-(5*1+10*5+10*10+5*10+1*5)+(0+10*1+10*5+5*10+1*10)-(0+0+10*1+5*5+1*10)+(0+0+0+5*1+1*5)-(0+0+0+0+1*1)=0
(6*1+0+0+0+0+0)-(6*4+15*1+0+0+0+0)+(6*6+15*4+20*1+0+0+0)-(6*4+15*6+20*4+15*1+0+0)+(6*1+15*4+20*6+15*4+6*1+0)-(0+15*1+20*4+15*6+6*4+1*1)+(0+0+20*1+15*4+6*6+1*4)-(0+0+0+15*1+6*4+1*6)+(0+0+0+0+6*1+1*4)-(0+0+0+0+0+1*1)=0
(7*1+0+0+0+0+0+0)-(7*3+21*1+0+0+0+0+0)+(7*3+21*3+35*1+0+0+0+0)-(7*1+21*3+35*3+35*1+0+0+0)+(0+21*1+35*3+35*3+21*1+0+0)-(0+0+35*1+35*3+21*3+7*1+0)+(0+0+0+35*1+21*3+7*3+1*1)-(0+0+0+0+21*1+7*3+1*3)+(0+0+0+0+0+7*1+1*3)-(0+0+0+0+0+0+1*1)=0
(8*1+0+0+0+0+0+0+0)-(8*2+28*1+0+0+0+0+0+0)+(8*1+28*2+56*1+0+0+0+0+0)-(0+28*1+56*2+70*1+0+0+0+0)+(0+0+56*1+70*2+56*1+0+0+0)-(0+0+0+70*1+56*2+28*1+0+0)+(0+0+0+0+56*1+28*2+8*1+0)-(0+0+0+0+0+28*1+8*2+1*1)+(0+0+0+0+0+0+8*1+1*2)-(0+0+0+0+0+0+0+1*1)=0
(9*1+0+0+0+0+0+0+0+0)-(9*1+36*1+0+0+0+0+0+0+0)+(0+36*1+84*1+0+0+0+0+0+0)-(0+0+84*1+126*1+0+0+0+0+0)+(0+0+0+126*1+126*1+0+0+0+0)-(0+0+0+0+126*1+84*1+0+0+0)+(0+0+0+0+0+84*1+36*1+0+0)-(0+0+0+0+0+0+36*1+9*1+0)+(0+0+0+0+0+0+0+9*1+1*1)-(0+0+0+0+0+0+0+0+1*1)=0
(10*1+0+0+0+0+0+0+0+0+0)-(0+45*1+0+0+0+0+0+0+0+0)+(0+0+120*1+0+0+0+0+0+0+0)-(0+0+0+210*1+0+0+0+0+0+0)+(0+0+0+0+252*1+0+0+0+0+0)-(0+0+0+0+0+210*1+0+0+0+0)+(0+0+0+0+0+0+120*1+0+0+0)-(0+0+0+0+0+0+0+45*1+0+0)+(0+0+0+0+0+0+0+0+10*1+0)-(0+0+0+0+0+0+0+0+0+1*1)=1
A similar proof works for any n substituted in Sigma{i=1 to n} (-1)^(i-1) Sigma{j=1 to r}(rCj*(n-r)C(i-j)). For example, for n = 4, 5 and 6:
N=4:
(1*1)-(1*3)+(1*3)-(1*1)=0
(2*1+0)-(2*2+1*1)+(2*1+1*2)-(0+1*1)=0
(3*1+0+0)-(3*1+3*1+0)+(0+3*1+1*1)-(0+0+1*1)=0
(4*1+0+0+0)-(0+6*1+0+0)+(0+0+4*1+0)-(0+0+0+1*1)=1
N=5:
(1*1)-(1*4)+(1*6)-(1*4)+(1*1)=0
(2*1+0)-(2*3+1*1)+(2*3+1*3)-(2*1+1*3)+(0+1*1)=0
(3*1+0+0)-(3*2+3*1+0)+(3*1+3*2+1*1)-(0+3*1+1*2)+(0+0+1*1)=0
(4*1+0+0+0)-(4*1+6*1+0+0)+(0+6*1+4*1+0)-(0+0+4*1+1*1)+(0+0+0+1*1)=0
(5*1+0+0+0+0)-(0+10*1+0+0+0)+(0+0+10*1+0+0)-(0+0+0+5*1+0)+(0+0+0+0+1*1)=1
N=6:
(1*1)-(1*5)+(1*10)-(1*10)+(1*5)-(1*1)=0
(2*1+0)-(2*4+1*1)+(2*6+1*4)-(2*4+1*6)+(2*1+1*4)-(0+1*1)=0
(3*1+0+0)-(3*3+3*1+0)+(3*3+3*3+1*1)-(3*1+3*3+1*3)+(0+3*1+1*3)-(0+0+1*1)=0
(4*1+0+0+0)-(4*2+6*1+0+0)+(4*1+6*2+4*1+0)-(0+6*1+4*2+1*1)+(0+0+4*1+1*2)-(0+0+0+1*1)=0
(5*1+0+0+0+0)-(5*1+10*1+0+0+0)+(0+10*1+10*1+0+0)-(0+0+10*1+5*1+0)+(0+0+0+5*1+1*1)-(0+0+0+0+1*1)=0
(6*1+0+0+0+0+0)-(0+15*1+0+0+0+0)+(0+0+20*1+0+0+0)-(0+0+0+15*1+0+0)+(0+0+0+0+6*1+0)-(0+0+0+0+0+1*1)=1
This actually shows particular values of n. The pattern is clear.
A formal mathematical proof for the general case can start with an already-proved theorem from Fellers Introduction to Probability Theory and Its Applications, vol. 1, 2nd edition. That theorem has the ORs interchanged with ANDs: P(A OR B OR C
OR Z) = P(A)+P(B)+
+P(Z) P(A AND B) P(A AND C)
- P(Y AND Z) + P(A AND B AND C) +
+P(X AND Y AND Z) P(A AND B AND C AND D)
Lets start with events A(1), A(2),
, A(n). Then P(A(1) OR
OR A(n)) = P(A(1)) + P(A(2)) +
+ P(A(n)) P(A(1) AND A(2)) -
- P(A(n-1) AND A(n)) +
where each ANDed even multiple of events is subtracted out and every ANDed odd multiple is added in.
Then consider the events A(1), A(2), A(3),
, A(n), defined as NOT A(1), NOT A(2), NOT A(3),
, NOT A(n). Similarly then, A(1) is the event NOT A(1), etc. Then P(A(1) OR
OR A(n)) is P(NOT A(1) OR
OR NOT A(n)). By De Morgans law this is P(NOT(A(1) AND A(2) AND A(3)
AND A(n))). By the definition of probability P(NOT x) = 1- P(x), so this becomes 1 P(A(1) AND
AND A(n)).
De Morgans law and negation can then also convert the right side into 1 P(A(1)) + 1- P(A(2)) +
+ 1- A(n) (1-P(A(1) OR A(2))) -
- (1-P(A(n-1) OR A(n))) +
So we have 1 P(A(1) AND
AND A(n)) = 1 P(A(1)) + 1- P(A(2)) +
+ 1- A(n) (1-P(A(1) OR A(2))) -
- (1-P(A(n-1) OR A(n))) +
If we subtract 1 from each side, and then multiply each side by 1, we get
P(A(1) AND
AND A(n)) =1 (1 P(A(1))) (1- P(A(2))) -
- (1- A(n)) + (1-P(A(1) OR A(2))) +
+ (1-P(A(n-1) OR A(n))) -
Now, the individual events as well as all odd ORed combinations have double negatives, therefore positive, and the even combinations of ORed events have negative. But there are all those 1s. Adding them, taking into consideration their signs, they total 1 nC1 + nC2 nC3 +
+/- nCn, the last term having absolute value 1 and positive sign if n is even and negative if odd. This is, however, the set of coefficients of (a-b)^n and in this instance a and b are both zero so a-b is zero and (a-b)^n is zero. Therefore all the 1s cancel out, and the formula is the one we are trying to prove.
|
