On 13 Bridges


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