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
Сайт управляется системой
uCoz