It’s as Easy as Falling Off a Cliff, or Is It?
In a kingdom
long ago, a king decided to let chance determine whether persons who
committed major crimes would be allowed to live and stay in the kingdom
or would fall to their deaths off a steep cliff. Offenders would be
placed blindfolded at the edge of the cliff, and then for the rest of
their lives, they would proceed to take a step forward, toward the
cliff”s edge, or a step backward, away from the edge, thus saving
themselves—at least for the time being.
A spinner, to be spun by a favorite of the king, would determine
whether the offenders stepped forward or backward. On the first spin, a
step toward the cliff would send the blindfolded criminal right over the
edge. A step away from the cliff would take the offender two steps back
from the edge. But then the king’s favorite would get to take another
spin, randomly determining the offender’s next step. And so on…
The king, being a “merciful” ruler, wanted the criminal to have a
sporting chance of .5 of not going over the cliff. So he asked the court
mathematician, “How should the spinner be divided for stepping toward
the cliff and stepping away from the cliff so that an offender has a .5
chance of surviving indefinitely?”
Some Ponderings:
Recall that in the June Problem to Ponder, we left a convicted
felon poised at the edge of a cliff. From that initial position, one
step toward the cliff, and the felon would fall to his death. This felon
was sentenced to a lifetime of taking steps either toward or away from
the cliff.
A spinner, to be spun by a favorite of the king, would determine
whether the offender stepped forward or backward. On the first spin, a
step toward the cliff would send the criminal right over the edge. A
step away from the cliff would take the offender two steps back from the
edge. But then the king’s favorite would get to take another spin,
randomly determining the offender’s next step. And so on…
The problem was to determine how the probabilities should be assigned
for this criminal to take steps toward the cliff or away from the
cliff, so that he had a 50% chance of surviving. Is there a break-even
survival probability for the criminal for steps toward the cliff?
We need to set the probability of a step toward the cliff at less
than 50%. If we fixed that probability right at 50%, the criminal would
have a 50% chance of falling on the very first step, plus the additional
probabilities of falling from any other positions further away from the
edge. For example, suppose the criminal manages to get one step away
from the cliff, but then moves back two steps in a row toward the cliff
and falls. Using the notation T for “toward” and A for “away” from the
cliff, the probability of this sequence ATT would be ½ x ½ x ½, so the
additional chance that the criminal falls is at least .125. Thus,
overall the probability would be at least .5 + .125, or .625, that the
criminal perishes.
One approach would be to experiment, setting probabilities of toward the cliff at p, and away from the cliff at (1 – p) and then running many simulations, gathering data for various values of p.
Another approach might be to think of this problem recursively.
# Steps away from the cliff…
<== Cliff (p) away from Cliff (1 – p)==>
“ouch!” <== 1 2 3 4 . . . ==>
Suppose we let P1 = probability of an eventual fall
if the criminal is at position 1 (right at the edge of the cliff). Our
challenge is to find a value of p that will make P1 = .5.
Suppose we let P2 represent the probability of an eventual fall if the criminal is at position 2. Then we have some relationships involving P1, P2, and p, since the probability p will be the same for any single step (fixed for the life of the criminal).
Note: P2 = (P1)2 (equation 1), and, P1 = p + (1 – p)P2 (equation 2).
Equation 1 holds because the probability of eventually falling off
the cliff is the same as the probability of eventually moving from
position 2 back to position 1. In fact, the probability of eventually
moving from any position n to position (n – 1) is the same for any n, where n is the number of steps away from the cliff.
Equation 2 says that the probability of falling from position 1 is
the sum of the probability of falling on a first step toward the cliff, p, plus the probability of falling from position 2 after a first step away from the cliff, which is (1 – p)P2.
These equations provide a good start to determine what value of p, if any, that could make the probability of an eventual fall, P1, equal to .5. More ponderings to come…
Future Ponderings:
In our previous discussion on the June Problem to Ponder, a
convicted criminal was positioned at the edge of a cliff and sentenced
to take a random step forward or backward, with probability p of moving toward the edge, and probability (1 - p) of moving away from it. We wanted to find a value of p that makes the criminal’s sentence fair, meaning that the felon has a .5 overall chance of long-term survival.
<== Cliff (p) away from Cliff (1 – p)==>
Number of steps away from the cliff…
“ouch!” <== 1 2 3 4 . . . ==>
We modeled the situation by letting P1 represent the probability of an eventual fall if the criminal starts at position 1, at the edge of the cliff. Then we let P2 represent the probability of an eventual fall if the criminal is at position 2, P3 represent the probability of a fall if at position 3, and so forth, with Pn representing the probability of an eventual fall at position n.
We noted that the probability of eventually falling off the cliff is
the same as the probability of eventually moving from position 2 back to
position 1 (or in general, from position n to position (n – 1)). So we have the following relation:
P2 = (P1)2 (Equation 1)
Also, the probability of falling from position 1 is the sum of the probability of falling on a first step toward the cliff, p, plus the probability of falling from position 2 after a first step away from the cliff. Thus, we can write the following:
P1 = p + (1 – p)P2 (Equation 2)
Substituting for P2 in equation 2 yields a quadratic in P1:
P1 = p + (1 – p) (P1)2, so (1 – p) (P1)2 – P1 + p = 0 (Equation 3)
In this case, we want to know the value of p that will make the value of P1
= .5, since the probability of an eventual fall, or long-term survival,
will each be ½, a fair sentence for the criminal. Substituting .5 for P1 in equation 3 gives us the following:
(1 – p) (.5) 2 – (.5) + p = 0
So, .25(1 – p) – (.5) + p = 0,
which yields
.75p – .25 = 0,
so p = 1/3 will make P1 = .5.
If the king sets the probability of any step towards the cliff at p = 1/3, our criminal will have a fifty-fifty chance of long-term survival.
Of course, the exhausted felon will eventually wear out anyway from all that random walking back and forth!