 Puzzles

In memoriam: Edsger W. Dijkstra

Reflected Probabilities and Bridge Collections

We want to determine how to compute the coefficients of the polynomial in p that is equivalent to a polynomial 1-P(1-p). We can do this with the binomial theorem and another interchange of summation, as follows: This is very similar to the previous interchange of summations. The only major difference between this interchange and the last one is what happens to the index ranges. In this summation, the starting value of the inner summation, rather than the ending value, becomes a function of the outer summation’s index. Also note how subtracting the sum from 1 has turned into adding the sum to 1: we accomplished this by moving the negation inside the sum, by adding 1 to the exponent of -1.

We do know that the p0 term of the resulting polynomial will be zero, so we can actually ignore the leading “1+” and start the j summation at 1 rather than 0. We can write the program computing these coefficients directly from this equation:

Seq(0,A,1,Dim List 1,1)→List 6 For 1→A To Dim List 1 0→B For A→C To Dim List 1 CCA→D DList 5[C]→D D+B→B Next If Frac (A÷2)=0 Then (-)B→B IfEnd B→List 6[A] Next This program, too, is in the zip file.

The above program takes the original polynomial coefficients from List 5 (where our bridges program put them) and puts the new polynomial coefficients into List 6. The variable A is used for i; B is used to accumulate the inner sum; C is used for j; D is used to compute the term of the inner sum. The power of -1 is computed from i being even or odd.

So, after we compute the probability function for a pattern of bridges, we can compute the reflected probability function by running this new program. And we find that we were right: the probability functions we thought were reflections of one another are indeed exact reflections of one another.

The following table shows the probability function (P) and the reflected probability function (R) for each pattern of bridges we have considered so far:

 P(p) = p R(p) -same- P(p) = -p2 + 2p R(p) = p2 P(p) = p3 - 3p2 + 3p R(p) = p3 P(p) = p2 R(p) = -p2 + 2p P(p) = 2p5 - 5p4 + 2p3 + 2p2 R(p) -same- P(p) = 4p8 - 18p7+ 27p6 - 10p5 - 9p4 + 4p3 + 3p2 R(p) = -4p8 + 14p7 - 13p6 - 2p5 + 4p4 + 2p3 P(p) = p3 R(p) = p3 - 3p2 + 3p P(p) = -4p8 + 14p7 - 13p6 - 2p5 + 4p4 + 2p3 R(p) = 4p8 - 18p7+ 27p6 - 10p5 - 9p4 + 4p3 + 3p2 P(p) = 18p13 - 117p12 + 298p11 - 352p10 + 149p9 + 39p8 - 10p7 - 37p6 + 2p5 + 8p4 + 3p3 R(p) -same-

This is quite interesting. We can use this ability to compute the reflection of the probability polynomial, and a little intuition, to find some other pairs of bridge arrangements that are “reflections” of one another in whatever sense we have discovered here: is the reflection of . is the reflection of . is the reflection of . is the reflection of . is the reflection of .

And now, I think, we can quit. We have not only answered the master’s question, we have shaken it until odd and fascinating things have fallen out. The original problem was to determine the probability the two shores remain connected for a particular probability of bridge survival and a particular arrangement of bridges and islands. We have done this and far more. We can, for any arrangement of bridges and islands, compute the probability with which the two shores remain connected as an explicit function of the probability of individual bridge survival. We can, for any probability polynomial, compute the polynomial that is the reflection of that polynomial. We have identified examples of bridges whose probability polynomials are reflections of one another. And we have left two broad questions for further research: what determines the smallest exponent in the probability polynomial, and what topological properties determine this “reflection”? Perhaps, taking an idea from linear programming, what we are calling an arrangement’s “reflection” might better be called its “dual”?

On the whole, I think we did fairly well with this. Page last updated 11 April 2006.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

In memoriam: Dijkstra

Introduction

Interpretation

Plan, part 1

Plan, part 2

Code

Extension 1

Extension 2

Final Modification

Bridge Collections

Site Information 