Imagine that there six islands in a river that flows through a city, and there are 13 bridges connecting the North and South banks of a river and the islands as shown below: North Bank ########################### | | | O------O------O | | | O------O------O | | | ########################### South Bank Suppose there's a storm one night, and each bridge has a 50% chance of collapsing (independent of what happens to the other bridges). What's the probability that it will be possible to cross the river from the North bank to the South bank using the bridges remaining after the storm? This is an interesting problem. Of course, for the specific case where each bridge has a 50% chance of collapsing, we can see immediately the overall probability of being able to cross the river is simply 1/2. It's kind of a trick question - the trick being to notice that you're unable to cross the river if and only if you ARE able to paddle a boat all the way from East to West without passing under a standing bridge. Then notice that the paddling network is identical to the bridge network, i.e., they are self-duals (just as the tetrahedron is its own dual). This is illustrated below, with 0's denoting the six isolated land regions (islands) and *'s denoting the six isolated water regions. ====================North shore======================= | | | | | | <--------|----*-------*---|-------- | | | | | West side 0----|---0---|---0 East side | | | | | <--------|----*---|---*---|-------- | | | | | 0----|---0---|---0 | | | | | <--------|----*-------*---|-------- | | | | | | ======================South shore======================== Since each bridge has a 50% chance of standing, it follows that the two networks (the bridge network and its dual water network) have equal probabilities of being "crossable", i.e., the probability of being able to cross North-South via the bridges is equal to the probability of being able to cross East-West via the water. Since these are mutually exclusive and complementary conditions, they must each have a probability of 1/2. Of course, there is an infinite family of problems that can all be solved in essentially the same way. All you need is a set of n(n+1) islands with 2n^2 + 2n + 1 orthogonal connections. For example, you could ask someone to figure out the probability of being able to cross with the following arrangement ===========north shore============ | | | | 0--0--0--0 | | | | 0--0--0--0 | | | | 0--0--0--0 | | | | ==========south shore============= So here there are 12 islands with 25 bridges. Or you could ask about 20 islands with 41 bridges, and so on. In every case this arrangement is self-dual so, assuming the probability of each bridge collapse is 1/2, the overall answer is 1/2. (Are these "n(n+1) orthogonal" arrangements the only complementary self-dual arrangements?) On the other hand, if each bridge collapse has a probability of something other than 50%, then the dual networks are no longer symmetrical, so the answer is less obvious. For example, if each of the 13 bridges in the origianl problem bridge has only a 25% chance of collapsing, the probability of being able to cross the river is 31161105/33554432. To determine the general solution, we need to know which of the 2^13 = 8192 possible states are "crossable" via the bridges. One approach would be to determine the "mincuts" of the system, i.e., the number of paths connecting the two sides of the river. By inspection, we see that there are 29 distinct ways of getting across (excluding loops and backtracking, etc). These represent the 29 mincuts of the system. It's easy to determine the probability that any particular one of these paths will be possible, but unfortunately you can't just add up these 29 individual probabilities because they aren't mutually exclusive; some states allow more than one path. The "brute force" approach would be to write a little program to check each of the 8192 states, and sum the individual probabilities of all the crossable states. However, since the number of states is 2^N where N is the number of bridges, this method becomes impractical very quickly as N increases. A more efficient method is to use what's sometimes called "Shannon's decomposition rule" (although it should really be attributed to George Boole rather than Claude Shannon, because it appears in Boole's "The Rules of Thought") to break up the problem into sub-cases that are more easily handled. Let's draw the picture like this 0 / | \ / | \ a b c / | \ / | \ 0---d--0---e--0 | | | f g h | | | 0---i--0---j--0 \ | / \ | / k m n \ | / \ | / 0 The basic rule of decomposition is that for any event E Pr{E} = Pr{E|X}Pr{X} + Pr{E|X'}Pr{X'} Here the notation a|b means "a given b", and a' means "not a". Very often it's easier to determine the probabilities of E|X and E|X' than it is to determine the probability of E, so this allows us to split up the problem into easier sub-cases. Essentially we want to be able to factor the 29 mincuts into independent components, so we can compute their probabilities independently and just add them up. One way of doing this is to specify the values of the four "horizontal" bridges d,e,i,j. In effect, these four parameters are our "X" in the decomposition rule. There are 16 possible (mutually exclusive) states of these four variables, and for each of these states we can determine the probability of being able to cross the river. For example, with {d,e,i,j} = {0,0,0,0} the only ways to cross are the paths afk, bgm, and chn, so we just need to evaluate the probability of the Boolean expression afk+bgm+chn. (In Boolean notation it's common practice to let multiplication denote logical AND and addition denote logical OR.) The three terms in this expression are independent (i.e., no common elements), so we can easily compute this probability. For example, if each bridge has a 50% chance of collapsing, then each of the events afk, bgm, and chn has a probability of (1/2)^3 = 1/8, and the probability of the logical OR of these three events is Pr{afk+bgm+chn} = 1/8 + 1/8 + 1/8 - 1/64 - 1/64 - 1/64 + 1/512 = 169/512 We then multiply this by the probability that d=e=i=j=0, which is just (1/2)^4 = 1/16, to give one of the components of our answer. Using this method to evaluate all 16 possible states of {d,e,i,j}, the complete problem breaks down as shown in the following table. (The Boolean mincut expressions in this table are general, but the probabilities are just examples based on the assumption that each bridge has a 50% chance of collapsing.) conditional probability d e i j g conditional mincuts probability of condition (50% case) (50% case) - - - - - --------------------- ----------- ------------ 0 0 0 0 afk + bgm + chn 169/512 1/16 0 0 0 1 afk + (bg+ch)(m+n) 211/512 1/16 0 0 1 0 (af+bg)(k+m) + chn 211/512 1/16 0 0 1 1 (af+bg+ch)(k+m+n) 259/512 1/16 0 1 0 0 afk + (b+c)(gm+hn) 211/512 1/16 0 1 0 1 afk + (b+c)(g+h)(m+n) 253/512 1/16 0 1 1 0 0 af(k+m) + (b+c)hn 87/256 1/32 1 (af+b+c)(k+m+hn) 169/256 1/32 0 1 1 1 (af+(b+c)(g+h))(k+m+n) 301/512 1/16 1 0 0 0 (a+b)(fk+gm) + chn 211/512 1/16 1 0 0 1 0 (a+b)fk + ch(m+n) 87/512 1/32 1 (a+b+ch)(fk+m+n) 169/512 1/32 1 0 1 0 (a+b)(f+g)(k+m) + chn 253/512 1/16 1 0 1 1 ((a+b)(f+g)+ch)(k+m+n) 301/512 1/16 1 1 0 0 (a+b+c)(fk+gm+hn) 259/512 1/16 1 1 0 1 (a+b+c)(fk+(g+h)(m+n)) 301/512 1/16 1 1 1 0 (a+b+c)(hn+(f+g)(k+m)) 301/512 1/16 1 1 1 1 (a+b+c)(f+g+h)(k+m+n) 343/512 1/16 Notice that a couple of these cases don't completely factor unless we also specify the state of g, so I've split them up into two sub- cases. The idea is that once we factor them into independent terms, we can easily compute the probabilities using the normal rules for independent events. Then, since all 18 conditions are mutually exclusive, we simply add up all the products of the conditional probabilities times the probabilities of the respective conditions to give the final result. In the "50% case" the answer comes out as 4096/8192 = 1/2, in agreement with our earlier "trick" solution. The self-dual nature of this network shows up in the fact that the above Boolean expressions occur in complementary pairs. We know the complementary "paddling problem" breaks down into a formally similar set of mincuts (with negated letters). Also, we know the logical complement of each "bridge expression" must have the same form as one of the "paddling expressions". It follows that the complement of each bridge expression is formally similar to one of the other bridge expressions with negated letters. We can confirm this by applying De Morgan's rules to each expression. For example, the complement of the first expression is _______________ ___ ___ ___ _ _ _ _ _ _ _ _ _ afk + bgm + chn = (afk)(bgm)(chn) = (a+f+k)(b+g+m)(c+h+n) which corresponds to the last expression (a+b+c)(f+g+h)(k+m+n). Another interesting aspect of this problem arises when we consider the case where the survival probability of each bridge is some fixed number x. Working from the mincut decomposition in the table above, we find that the overall probability of being able to cross the river is given by the 13th degree polynomial P(x) = 3x^3 + 8x^4 + 2x^5 - 37x^6 - 10x^7 + 39x^8 + 149x^9 - 352x^10 + 298x^11 - 117x^12 + 18x^13 Obviously we have P(0)=0, P(1/2)=1/2, and P(1)=1. In between these values the function P(x) has an "S" shape as shown (roughly) below | 1 - * | * | * | * | * | * | * | * 0 |*___________________________ 0 1 Because of the complementarity with the boat problem, it's clear that this polynomial satisfies the identity P(x) + P(1-x) = 1 (1) We can determine the polynomial corresponding to any of the generalized problems as well, and in each case they satisfy equation (1). For example, for the simple case with 2 islands and 5 bridges ============ | | 0--0 | | =========== the polynomial is the quintic P(x) = 2x^2 + 2x^3 - 5x^4 + 2x^5 Of course, the simplest example of all is the case n=0 with 0 islands and 1 bridge, which has the polynomial P(x) = x. If we plot these functions P(x) we see that with n=0 it's a straight diagonal line, and as n increases it becomes more like a diagonal S shape. In the limit (for larger and larger arrays of islands and bridges) it approaches a step function, equal to zero for all x < 1/2 and equal to 1 for all x > 1/2. There are other polynomials with the property (1), such as P(x) = 3x^2 - 2x^3 but off hand I don't see what (if any) crossing arrangement this represents. It does, however, give the probability that three randomly chosen points on the unit interval will be within x of each other.

Return to MathPages Main Menu