Answers to the Programming Quiz:
Tom got the answer to number one. The assignment
(-1 ^ (j - 1))
will always be -1 for any integer value of j, because of Visual Basic's order of operations. The carat operator is applied before the minus operator. This added about 15 minutes to my debugging time.
As for the second question, Dave was right on with his assessment:
"it seems to take a set of real numbers and multiplies them against each other, alternately adding/subtracting the products."
That is, in fact, exactly what it does, and had he known the law in question, you probably would have gotten it from here. The law (or maybe formula would be a better term) is the general form of the Addition Law for n Independent, Non-exclusive Events, and is used in the field of probability to determine the chances that at least one of n events occurs, given the probabilities of each individual event.
To explain this, let me first define independent and non-exclusive. Two events are independent if the occurrence of one does not affect the occurrence of the other. Example: a die rolling 6 and a coin landing heads.
Two events are exclusive if they cannot occur at the same time. Example: a coin landing heads, and the same coin landing tails.
So the probability of either of two independent, non-exclusive events occurring is given by the equation:
P(A+B) = P(A) + P(B) - P(A)∙P(B)
Where P(A+B) is the probability that either A or B occurs, P(A) is the probability that A occurs independently, and P(B) is the probability that B occurs independently. (I am using + notation because I can't find the stupid Union symbol in the character map.)
This can be easier to understand with a Venn diagram.
If we want to find the area covered by both ellipses (the probability that at least one of the events occurs), we start by adding the area of each ellipse (P(A)+P(B)). But then we have added the intersection of the two events twice, so we need to subtract it out once (–P(A)∙P(B)).
We can determine the probability that any of three independent, non-exclusive events occurs with the equation:
P(A+B+C) = P(A) + P(B) + P(C) - P(A)∙P(B) - P(A)∙P(C) - P(B)∙P(C) + P(A)∙P(B)∙P(C)
To understand this, let's look at another Venn diagram.
To find the area covered by all three circles, we begin by adding in the area of each circle (the independent probability of each event, P(A) + P(B) + P(C)), but then we have added some regions more than once. To compensate, we can subtract out the intersection of every two circles (–P(A)∙P(B) – P(A)∙P(C) – P(B)∙P(C)). But now we have completely subtracted out the center region, the intersection of all three circles (P(A)∙P(B)∙P(C)).
I think you see where this is going for four events, etc. It gets very complex. In fact, the general form of the Addition Law, for n independent, non-exclusive events is:
(I)
In essence, we add in the independent probability of each event, subtract the products of each combination of two events, add the products of each combination of three events, subtract the products of each combination of four, etc., until we finally add or subtract (depending on if there are an odd or even number of events) the product of every event probability. This is what my VB code was attempting.
(There is an alternate, less complex way of attempting this. Instead of a brute force method, we can instead consider the inverse probabilities. Instead of finding the area covered by the circles/ellipses, we can find the area not covered by them, and subtract that from 1. To wit:
De Morgan's theorem states: P(A+B)' = P(A'∙B') = P(A')∙P(B')
That is, the probability that neither A nor B occurs is the probability that A does not occur and B does not occur. So if we subtract that from 1, we get:
P(A+B) = 1 – P(A')∙P(B') = 1 – (1 – P(A))∙(1 – P(B))
Which, for the general form, expands to:
(II)
)
So what brought this all up?
Probability theory figures heavily in fault tree analysis. A fault tree is, essentially, a collection of events (each with an associated probability of occurrence, specifically a probability of failure) connected via logic gates, such as AND and OR gates (and sometimes VOTE gates).
What? Explanation of the logic gates? Ok, we can do that.
This is an AND gate. It denotes that the output occurs if all of the input events occur.
An OR gate denotes that the output occurs if any of the inputs occurs.
A VOTE gate denotes that the output occurs if at least n of the inputs occurs (in this case 2).
(These symbols may seem familiar to those of you who took computer architecture. The symbols are the same ones used in logic gate diagrams, but turned sideways.)
There are also other miscellaneous gates, such as a NOT gate or XOR gate, but that's a bit beyond the scope of a simple introduction.
So the basic premise of fault tree analysis is we want to know about how often (the probability) a TOP event will occur, based on the occurrence of basic events. The TOP event is usually some hazard that we would like to prevent. A basic event is a failure or occurrence which may cause the TOP event to occur.
So, to create a fault tree, we connect these basic events to the TOP event through intermediate logic gates. These logic gates represent how the failures combine to cause a TOP event occurrence. A small fault tree might look like this:

The way to read this is by looking at the logic symbol of each gate to determine which of its input events must occur to cause the gate to occur. For example, if EVENT5 and EVENT6 occur, this will cause GATE3 to occur, because it's an AND gate and requires the occurrence of all input events. If GATE3 occurs, GATE2 will also occur, because it's an OR gate and the occurrence of any of its inputs will cause its occurrence. Now, if any two of the inputs to GATE1 occurs, say EVENT1 and EVENT3, then GATE1 will occur (because it's a VOTE gate). And if both GATE1 and GATE2 occur, then TOP1 will also occur. So we could say that TOP1 will occur if EVENT1, EVENT3, EVENT5, and EVENT6 all occur at the same time. We call this occurrence of events a minimal cut set. (I might talk more about cut sets in the future, if you wish, but as it is, this post is running too long.) Another minimal cut set might be EVENT2.EVENT3.EVENT4. (Note, EVENT2.EVENT3.EVENT4.EVENT5 is also a cut set, but not minimal. Do you see the difference?)
I will skip over how to produce the full list of minimal cut sets for this tree, and just list them all. They are:
EVENT1.EVENT2.EVENT5.EVENT6
EVENT1.EVENT2.EVENT4
EVENT1.EVENT3.EVENT5.EVENT6
EVENT1.EVENT3.EVENT4
EVENT2.EVENT3.EVENT5.EVENT6
EVENT2.EVENT3.EVENT4
By this point, you can probably see how to produce them yourself. Now each cut set can be thought of as an event, itself. So, basically, what we have here is a list of non-exclusive, independent events, the occurrence of any of which will cause the TOP event.
Sound familiar?
The obvious way to solve this, then, would be to use... the Addition Law!
And this is exactly what the software (that company I work for) writes does. You tell it the events, how they're logically connected, and some quantitative data, such as a failure rate or MTTF (mean time to failure), and it will calculate:
1) The probability of each event occurring,
2) The probability of each cut set occurring (simple: the product of the probabilities of each event in the cut set)
3) The probability of occurrence of the TOP gate (using the Addition Law).
Note how quickly the addition law gets complex. This small and simple tree produces six cut sets, which would require 6 + 15 + 20 + 15 + 6 + 1 = 63 product terms in the addition law. Just the other day I was working with a fault tree that had 152 cut sets for one intermediate-level gate. This is why our software will use approximation methods and all sorts of other tricks to be able to solve the tree. In fact, one of the approximation methods involves using de Morgan's theorem and equation II. This is called the Esary-Proschan approximation method, but you didn't really want to know that.
If you would like, I could talk a little bit more about fault tree analysis later, and give real examples, instead of odd abstractions. But this post has gone on too long.
And now you know what I do for a living!
So back to the topic at hand, why was I writing a VB program to implement the Addition Law? Basically, I needed to verify the results of a fault tree. By hand.