Suppose we wanted to determine the probability of the two shores being connected, when the probability each bridge remains standing is some probability other than ½.

Suppose the probability each bridge remains standing is *p*.
Then the probability each bridge has been removed is 1-*p*.
The probability associated with a particular set of bridges
remaining standing is the product of a *p* for each bridge
that remains standing, and a 1-*p* for each bridge that has
been removed.
If we say *k* is the number of bridges remaining standing
out of *n* bridges, then the probability is:

Now, this probability does not depend on *which* bridges
remain standing, just on the *number* of bridges that
remain standing.

Currently, the program increments a single counter whenever it
discovers a subset of bridges which leave the two shores connected.
Suppose that instead of a single counter, there were a vector of
counters, *M* = (*m*_{k}), indexed by the
number of bridges *k* in the subset.
Then the probability *P* of the shores remaining connected is
a function of the probability *p* of a given bridge remaining,
as follows:

As with a previous “mathematical diversions” note (you did read
those, didn’t you?), the capital sigma means to take the sum
of the quantities expressed; the “*i*=0” and
“n” limits on the sigma indicate that the index variable
*i* is taken to vary from 0 to *n*.
The sigma notation is just mathematical notation to indicate
accumulating a sum with an iteration.

Note that the *m*_{i} values do not depend on
the value of *p*.
This means we can compute the vector *M* once, then use it to
compute *P*(*p*) for any value of *p*.

There are two questions that arise here.
The first question is how we determine the number of bridges
standing, so that we can increment the correct element of the
vector of counters *M*.
The second question is how we should display a result that is a
function, rather than a value.

List 2 has a set of boolean values that indicate which bridges are standing in the set of bridges being considered. These boolean values are 0 to indicate bridges which have been removed, and 1 to indicate bridges that are present. Therefore, the sum of the elements in List 2 is a count of the number of bridges present in the subset of bridges being considered. Fortunately, the calculator lets us form the sum of the elements of a list simply, with the Sum operator.

The obvious way to display a function is to graph it.
The domain of the function is a probability in the range 0 to 1.
The range of the function is similarly a probability in the range
0 to 1.
The program can graph the function by evaluating *P*(*p*)
at each of an increasing (for example) sequence of *p* values,
plotting each (*p*, *P*(*p*)) point, and drawing a
line between the points corresponding to each adjacent pair of
*p* values.
Fortunately, the calculator has Plot and Line commands that do
much of the work for us.

In order to plot the function, however, we need to compute it.
Looking at the equation of *P*(*p*) above, we see it is
a sum of a number of terms.
So we have a collection of items, and we want to determine a
property (the sum) of the collection as a whole.
We can use the trick of the trade about properties of collections
as a whole to have the program iterate through the collection of
terms, accumulating a “sum of terms seen so far” value;
when the program reaches the end, the “sum of terms seen so
far” will be the “sum of all terms.”
This computation follows the following flowchart:

The variables referenced in this flowchart are named for mnemonic
reasons: *i* is an index of terms, *s* is a sum of terms,
and *t* is a term.
The value *n* is, as before, the number of bridges present
before the storm..

There is one potential problem with this computation: the calculator
refuses to compute 0^{0}.
All of *p*, 1-*p*, *i*, and *n*-*i* are at
some point or another zero.
By convention, *x*^{0} has the value 1 for all values
of *x*, including 0; and 1 is the multiplicative identity.
So we can compute the term *t* by the following somewhat
cumbersome process:

Now we are ready to modify the program.
First, we use List 4 to hold the vector *M*, and initialize
all the elements to 0:

Seq(0,A,1,Dim List 1, 1)→List 4

We need to add this statement at the front of the program with all the other list initialization. We can also delete the statements

0→D

0→E

as the program will not be using a ratio for a probability.

Note that our *M* vector is actually 0-indexed, while the
List is 1-indexed.
As it happens, though, *m*_{0} is always zero: if no
bridges remain standing, there is no way to get across the river.
As long as we do not attempt to access *m*_{0} —
and knowing it is always 0, there is no reason to access it —
we should not get into trouble.

Now, we need to replace the statement

D+1→D

This was incrementing the number of combinations of bridges that connected the two shores. We change the program to keep a vector of counts.

Sum List 2→D

List 4[D]+1→List 4[D]

We also delete the statement

E+1→E

Finally, we need to replace the last statement of the program.
Formerly, it computed the (single) value of the probability and
had the calculator produce it.
What we would like to do instead is produce a graph of the
probability function *P* as a function of *p*.

First, we initialize the graph view window.

ViewWindow 0,1,.25,0,1,.25

We will arbitrarily use 50 steps to graph the probability, and put the step index into A.

For 0→A To 50

The probability value *p* being considered is the step index,
divided by the number of steps.
Note that we started the step index (variable A) at 0, so the
values of the probability value *p* will be 0, 0.02, 0.04, ...,
0.98, 1.
We put the probability value *p* into B.

A÷50→B

We will compute the probability *P* as the sum of a set of
terms; the program has yet to see any terms, so the sum is 0.
We put the sum into C.

0→C

Now we compute each term, using D as the summation index and E as the term value.

For 1→D To Dim List 1

List 4[D]→E

(B^D)E→E

If D≠Dim List 1

Then ((1-B)^(Dim List 1-D))E→E

IfEnd

E+C→C

Next

The code has only one conditional inside the loop, rather than
two.
This is because the flowchart assumed we were adding terms with
indices from 0 to *n*, as we should.
However, the code is written with the count vector *M* being
1-based, rather than 0 based; *m*_{0} is zero.
Therefore the index of terms starts at 1, rather than 0, and so
*p*_{0} cannot occur.
As it cannot occur, we omit the test guarding against it.

Now we plot this *P* value against the *p* value.

Plot B,C

Unless this is the first *P* value, we connect this new point
to the previous point with a line.

If A≠0

Then Line

IfEnd

That is all we need to do for this value of *p*.

Next

We run this modified program, and after several hours the program produces the following graph:

This is what we wanted.

But wait! We can do more!

[ Previous page | Top of page | Next page ]

Copyright © 2002 Brian Hetrick

Page last updated 10 April 2006.