First, we must make sure we understand the problem. The initial situation consists of (i) a river, represented in the diagram by the white background; (ii) two shores of the river, represented by the two hatched bands; (iii) six islands in the river, represented by circles between the two hatched bands; and (iv) thirteen bridges, represented by gray lines between the circles and between circles and the hatched bands.

This situation changes by bridges being “swept away” with “probability ½.” We interpret a bridge being “swept away” as the bridge being removed from the set of bridges available for use. We interpret the phrase “probability ½” as each bridge, independently, having an equal likelihood of remaining available for use or being removed from the set of bridges available for use.

The question involves whether “the shores remain connected.” We interpret this as asking whether there is a path from one shore to the other shore, where the path goes from a location over a remaining bridge to another location, and from that location over a remaining bridge to yet another location, and so forth.

Finally, the question asks the probability that the shores remain connected. To interpret this question, we need to understand just a little bit about about probability.

A probability space is a triple (*S*,
, *P*) where *S* is a nonempty
set called the *sample space*, is a σ algebra of subsets of
*S* called the *set of events*, and *P*: is a
*probability measure*.

Come back! Come back! I promise I’ll be good. I’ll go back to English now, really!

There are 13 bridges. After a storm, each bridge either remains, or is removed. The possible outcomes are particular combinations of bridges remaining. The sample space is the set of possible outcomes. The sample space here is the set of combinations of the 13 bridges. Each outcome is a set of bridges that remain standing; the set of all outcomes — in this case, a set of sets — is the sample space.

The set of all subsets of a set *A* is called the *power
set* of *A*.
The power set of *A* is denoted by 2^{A}.
If we associate each bridge with an index taken from {1, 2, ...,
13}, then the outcomes are {} (the empty set, representing the
case where no bridge survives the storm), {1}, {2}, {1, 2}, {3},
{1, 3}, {2, 3}, {1, 2, 3}, ..., {1, 2, ..., 12, 13}.
The sample space is therefore the power set of {1, 2, ..., 13}.

The number of elements in a set *A* is called its
*cardinality* and is represented by the absolute value
operator |*A*|.
For finite sets *A*, |2^{A}| =
2^{|A|}, that is, the cardinality of the power
set of a set is two to the power of the cardinality of the set.

The *probability* of an event is a number from 0 to 1
that measures the likelihood of an event.
In this case, it is the likelihood of a particular combination
of bridges remaining after a storm passes.
A probability of 0 means an event is impossible, and cannot
occur.
A probability of 1 means an event is certain, and must occur.
In our case, we assume that whether a given bridge remains or
has been removed is not influenced by what other bridges
remain or have been removed.
This property of probabilities is called *independence*,
and it implies that we can compute the probability of the
intersection of two events — that they both happen at
once — in a particularly easy way: we get to multiply
the two probabilities together.

Suppose we have an outcome, that is, a combination of bridges
that remain after a storm passes.
There is a set of bridges that remained, and a set of bridges
that were removed.
Each bridge that remained, had a probability ½ of
remaining; and each bridge that was removed, had a probability
½ of being removed.
As the bridges remaining or being removed are independent of
one another, we can multiply the probabilities together: ½
for the first bridge — either it remains, with probability
½, or it has been removed, with probability ½ —
½ for the second bridge, ½ for the third bridge, and
so forth, on to ½ for the thirteenth bridge.
There are 13 instances of ½ to multiple together, one for
each bridge.
The probability is therefore ½^{13}, or 1/8192, for
the outcome — for the particular combination of bridges to
remain after the storm has passed.
This is true for every outcome, *regardless of which particular
bridges remain*.

Each outcome, that is, each possible combination of bridges
remaining after the storm has passed, therefore has probability
½^{13}, or 1/8192.
What we are interested in, though, is “the probability that
the shores remain connected,” that is, whether the bridges
that remain after the storm let one travel from one shore to the
other.
For each possible combination of bridges that could remain after a
storm, either the shores are connected or they are not.
Further, if a particular combination of bridges remains after the
storm, then no other combination of bridges remains after the
storm.
So what we want is the probability of the event that the two shores
remain connected.

We have outcomes — combinations of bridges that remain after the storm — and events — sets of possible outcomes. We want the probability of the event “the shores remain connected.” One of the properties of a probability measure is that the probability of an event composed of a number of outcomes in the sum of the probabilities of the individual outcomes. So the probability that the event “the shores remain connected” occurs is just the sum of the probabilities of the outcomes where the shores remain connected.

The properties of a probability measure are:

where the zero with the slash through it indicates the *null
set*, *S* we remember is the sample space, and the
{*A*_{i}} are mutually exclusive events.
The big “U” symbol indicates the *union* of the
sets *A*_{i}; the capital sigma symbol
indicates the *sum* of the values
*P*(*A*_{i}); and *i*∈*I*
underneath the union and sum operators indicates that the union
or sum is taken over all the indexes in a set *I*.
The phrase “mutually exclusive” means that no two
events can occur at the same time.

Well, each outcome is an event, and the outcomes are mutually exclusive. So we can determine the probability of an event as just the sum of probabilities of the outcomes composing the event.

In the case of the bridges, each outcome has the same probability,
1/8192; so if *C* is the set of outcomes, that is, sets of
bridges remaining, that leave the shores connected, the
probability of the shores being connected is just the number of
elements of C, divided by 8192.

Therefore, we can answer the question (remember the question? “What is the probability that the shores remain connected?”) by the following process:

- Consider all possible outcomes;
- Count the outcomes that leave the shores connected; and
- Divide the count of outcomes that leave the shores connected by 8192.

Well, let’s get started, then.

[ Previous page | Top of page | Next page ]

Copyright © 2002 Brian Hetrick

Page last updated 10 April 2006.