# MONKEY PROBABILITIES (MPROBS): by David C. Wise Written 1989 Originally posted in the Science & Religion Library on CompuServe

The program, MPROBS, calculates the probabilities encountered by the program, MONKEY, as it uses cumulative selection to produce the alphabet in alphabetical order through random changes. For more on this subject, read the text file, MONKEY.DOC, the source code of MONKEY, and Chapter 3 of Richard Dawkins' book, The Blind Watchmaker. This file discusses those probabilities.

Dawkins distinguishes between single-step selection and cumulative selection. Simply expressed, single-step selection requires that the process starts from scratch and produces the desired result in a single attempt; all repeated attempts must start from scratch as well. On the other hand, cumulative selection allows the process to proceed step-wise; the closest approach to the desired result in the previous step serves as the starting point of the next step.

The probability arguments of anti-evolutionists rely almost entirely on single-step selection. Yet cumulative selection is far more descriptive of evolution. Populations change step-wise through time, with each generation forming a step and providing a starting point for the next generation. An established population spawns the next generation which is largely similar, yet slightly different from it. In contrast, single-step selection is far more descriptive of creation ex nihilo.

Since MONKEY offers an empirical comparison between the two, it would be edifying to first examine the probabilities of single-step selection for later comparison with cumulative selection.

### SINGLE-STEP SELECTION:

In the single-step problem, we attempt to produce a target string, the alphabet in alphabetical order, by randomly generating the letters 'A' through 'Z' and stringing them together. If we fail to produce the target string, then we start from scratch. Multiple attempts improve the probability of success, but it turns out that single-step selection is very badly hampered. To judge the method empirically, the closest that any attempt in a continuous 4-day run came to matching the target was to match 8 out of 26 letters. The cumulative-selection method can consistently produce a match in less than 10 seconds.

The probabilities and their factors are as follows:

c = size of character set
= 26
n = target size
= 26

P1 = prob to generate the right letter in a given position
= 1/c
= 1/26 = 3.85%
Q1 = prob to generate the wrong letter in a given position
= 1 - P1
= (c-1)/c
= 25/26 = 96.15%
P2 = prob to succeed in selecting all right letters for all positions
= P1n
= 1/cn
= 1/2626 = 1.6244E-37
Q2 = prob to fail
= 1 - P2
= 1 - 1/cn = (cn - 1)/cn
= (6.156E36 - 1)/6.156E36 = 1 approx.
For any given position in the string, there is one chance in 26 that the correct letter will be generated. Since the correct letter must be generated 26 times in a row, the probability of generating the target string is the very small value, P2 = 1.6244E-37. In other words, it is very unlikely.

However, performing multiple attempts should help to make that probability higher. In his book, Evolutionary Genetics, John Maynard Smith advises the reader that if you cannot determine the probability of something happening, then determine the probability of it not happening. So to handle single-step selection with multiple independent trials:

m = number of trials

Q3 = prob that all m trials fail
= Q2m
= (1 - 1/cn)m
= (1 - 1.6244E-37)m
P3 = prob that at least 1 trial out of m trials will succeed
= 1 - Q3
= 1 - Q2m
= 1 - (1 - 1.6244E-37)m
Even though the probability Q2 (probability to fail in selecting all right letters for all positions) approaches total certainty (i.e. 100%), it is nevertheless less than 1. This means that as we successively multiply Q2 by itself, Q3 (probability that all m trials will fail) will diminish and P3 (probability that at least 1 trial out of m trials will succeed) will grow to eventually become likely -- given a sufficiently large number of trials.

But just how many is sufficient? Given the equation for P3, we can solve for the number of trials, m:

P3 = 1 - Q2m
Q2m = 1 - P3
m * LN(Q2) = LN(1 - P3)

ergo:  m = LN(1 - P3)/LN(Q2) = LN(1 - P3)/LN(1 - P2)
Unfortunately, neither my computer nor any of my calculators carry their floating-point operations to enough significant digits to be able to calculate m for the range of values our probabilities are running. J. M. Smith comes to the rescue again by offering an approximation:
(1 - p)n = EXP(-n * p) approx. for sufficiently large values of n
and sufficiently small values of p
Substituting this approximation for the term Q2m [ = (1 - P2)m], we get:
EXP(-m * P2) = 1 - P3
-m * P2 = LN(1 - P3)

ergo:  m = LN(1 - P3)/(-P2)  approx.
Now we can determine how many trials are necessary to ensure us of a given probability of success. For various values of P3, they are:
P3 (%)        m
1 E -9      6.156 E 27
1         6.187 E 34
10         6.486 E 35
25         1.771 E 36
50         4.267 E 36
75         8.534 E 36
85         1.168 E 37
90         1.417 E 37
95         1.844 E 37
99         2.835 E 37
99.99      5.670 E 37
So even for just one chance in a million of succeeding, we have to make something to the order of 1027 attempts! To put this into some perspective, assume we have a computer that can make one million attempts per second (a very generous assumption, since mine can only make about 200 per second). That translates to 31,556,926 million attempts per year. At this rate, it would take about 195 trillion years to earn that one-in-a-million chance -- nearly 10,000 times longer than the universe's estimated age of 20 billion years!

To be blunt, the performance of single-step selection is abysmal. But then it also does not come close to describing evolution. For that, we will now examine a model based on the cumulative-selection method.

### CUMULATIVE SELECTION:

The probability model employed in this program uses a state diagram of the system represented by the string that we are generating. The states of this system are determined by the number of correct letters that are correctly placed in the string; hence State 0 would have not correct letters, State 10 would have 10 letters correctly placed, and State 26 would be the final target state with all 26 letters correctly placed.

Since the Alphabet Test is constructed to allow only one letter position to change at a time, our probability model can only step to adjacent states. In each step one of four things happens:

1. a previously incorrect letter is changed to a correct letter,
2. a previously correct letter is changed to an incorrect letter,
3. a previously incorrect letter is changed to an incorrect letter, or
4. a previously correct letter is changed to an correct letter.
The first case causes the system to transition one step closer to the target state, the second case causes it to move one step away from the target state, and the third and fourth cases cause it to remain in the same state. Hence, for a given state, we can calculate the probabilities of the three state transitions occurring. The following defines these three probabilities and their underlying assumptions:
c = size of character set
= 26
k = current count of correct letters (hence the state number)
n = target size
= 26

P1 = prob to generate the right letter in a given position
= 1/c
Q1 = prob to generate the wrong letter in a given position
= 1 - P1
= (c-1)/c
P2 = prob to select position of a wrong letter
= (n-k)/n
Q2 = prob to select position of a correct letter
= k/n
The size of the character set is that of the alphabet itself, as is the length of the target string, which is the alphabet itself. For any given letter position, there is only one correct letter, so the probability of randomly picking that correct letter is 1 in 26 (1/26), as the probability of randomly picking a wrong letter is 25 in 26 ((26-1)/26). These probabilities remain constant once the size of the character set has been defined.

However, the probability of selecting the position of an incorrect letter varies with each state and is a function of the state number (i.e. number of correct letters already in place). In State #k, there are 26-k incorrect letters (e.g. State #0 has 26 incorrect letters, State #10 has 16, and State #25 has 1), so the probability of selecting the position of an incorrect letter is (26-k) in 26. Conversely, the probability of selecting the position of a correct letter is k in 26. It is interesting to note that when we are farthest from the target, we are more likely to change an incorrect letter (hopefully to a correct one), but when we get closer to the target, we are instead more likely to change an correct letter (usually to an incorrect one). So the closer we get to the target, the more vulnerable we are to slipping back. In light of this, consider the following probabilities of stepping toward the target, slipping back away from the target, and not changing state:

P3 = single prob to make next step
= P1 * P2
= (n-k)/nc
Q3 = single prob not to make step
= 1 - P3
= (nc - n + k)/nc
P4 = single prob to slip back
= Q1 * Q2
= k*(c-1)/nc
Q4 = single prob to not slip back
= 1 - P4
= (nc - kc + k)/nc
P5 = single prob of no change
= 1 - (P3 + P4)
= (nc - n + 2k - kc)/nc
In order to make a step toward the target state, we must both select the position of an incorrect letter and replace that incorrect letter with a correct one. Obviously, for all states, the probability of making a step is less than for not making it.

One of the cases for not making a step is the case of slipping back to the previous state. In order to do this, we must both select the position of a correct letter and replace it with an incorrect letter. When we are far from the target state, the probability of slipping back is less than of not slipping back. But after we get about half-way to the target the probability of slipping back becomes greater than of not slipping back and increases as we approach the target.

If we are neither making the next step and nor slipping back, then we are not making a state change (yes, it's obvious, but it had to be said). This is the third possible case and its probability is derived by realizing that the total sum of the probabilities of all possible moves is equal to 1. We find that as we approach the target state, the probability of change becomes increasingly greater (i.e. the probability of not making a state change diminishes).

So what do we find so far? We find that not only is it harder to advance toward the target state than to slip back, but that it keeps getting harder the closer we get to the target state. We also find that the system is far less stable near the target state than away from it; the closer we get, the greater the chance of changing the state, which means a greater chance of slipping back.

All these probabilities that we have developed seem to conspire against any attempt to produce the alphabet in alphabetical order through randomly changing a random character string. If anything, our calculations indicate that the system possesses a strong resistence to random efforts to establish order and that it tends toward disorder. In short, we appear to have developed a probability argument that demonstrates the effects of entropy and hence the impossibility of MONKEY.

Yet MONKEY not only succeeds in accomplishing its task, but it does so very rapidly and consistently. It never fails -- never. How does it do it?

The answer lies partly in the process under investigation, cumulative selection. But we have determined that cumulative selection alone does not account for MONKEY's success (see below for a discussion of how it still does contribute greatly). What has been lacking so far is discussion of the factor of multiple offspring; i.e. we have examined the probabilities of a single offspring's state transitions, but not of a population of offspring.

The standard creationist approach to probability problems is to consider the probabability a number of independent events all occurring. Such a probability is calculated by multiplying the probabilities of all the individual events together (e.g. tossing heads ten times in a row would be 0.5 10 = 9.765625E-4).

However, we want to determine the probability of a given result occurring at least once in a number of independent events. I.e., instead of determining the probability of A and B and C and ... , we need to determine the probability of A or B or C or ... .

Another way to view the problem is to realize that the probability of any one (or more) offspring making a given state transition is the inverse of none of them making it; i.e.:

A or B or C or D = NOT( NOT(A) and NOT(B) and NOT(C) and NOT(D) )
The analogy should be immediate apparent to the de Morgan Theorem in Boolean algebra, wherein an OR-gate is logically equivalent to an AND-gate with all its inputs and output inverted.

For P(A) being the probability of an event, A, occurring, we would apply the above thus:

NOT(A) = Q(A) = 1 - P(A)
A and B and C = P(A) * P(B) * P(C)
A or B or C = NOT(Q(A) * Q(B) * Q(C))
= 1 - (Q(A) * Q(B) * Q(C))
and for P(A) = P(B) = P(C) = P:
A and B and C = P3
A or B or C = NOT(Q3)
= 1 - (1-P)3
Now applying this technique to our example, we obtain the following probabilities:
m = number of members per generation
P6 = prob to make next step
= OR(i in 1..m,P3i)
= 1 - Q3m
= 1 - ((nc - n + k)/nc)m
P7 = prob to slip back
= AND(i in 1..m,P4i)
= P4m
= (k*(c-1)/nc)m
P8 = prob of no change
= 1 - (P6 + P7)
= Q3m - P4m
= ((nc - n + k)/nc)m - (k*(c-1)/nc)m
Rather than analyzing these probabilities algebraically, let's test them empirically by plugging in some sample values:
g:  c = 26
n = 26
k in 0..25
m = 10, 20, 80, or 99

P6 = 1 - ((262 - 26 + k)/262)m
= 1 - ((650 + k)/676)m

for m = :     10           20          80          99
for k = 0    .3244        .5436       .9566       .9794
5    .2706        .4680       .9199       .9560
10    .2130        .3806       .8528       .9066
15    .1513        .2797       .7308       .8029
20    .0853        .1633       .5099       .5863
25    .0147        .0292       .1117       .1363

P7 = (k*(25)/262)m
= ((nc - n + k)/nc)m - (k*(c-1)/nc)m
= km * (25/676)m
= km * (.036982248)m

for m = :     10           20          80          99
for k = 1     4.786E-15    2.290E-29   0            0
5     4.673E-8     2.184E-15   2.275E-59    2.688E-73
10     4.786E-5     2.290E-9    2.751E-35    1.703E-43
15     2.760E-3     7.615E-6    3.363E-21    4.617E-26
20     4.900E-2     2.401E-3    3.326E-11    1.080E-13
25     .4564        .2083       1.882E-3     4.240E-4

P8 = ((262 - 25 + k)/262)m - (k*(25)/262)m
= ((650 + k)/676)m - km * (25/676)m
= ((650 + k)/676)m - km * (.036982248)m

for m = :     10           20          80          99
for k = 0     .6756        .4564       .0434       .0206
5     .7294        .5320       .0801       .0440
10     .7869        .6194       .1472       .0934
15     .8459        .7203       .2692       .1971
20     .8657        .8343       .4901       .4137
25     .5289        .7625       .8864       .8633
Some trends are immediately apparent. As expected from the previous discussion, P6 (probability to make next step) decreases and P7 (probability to slip back) increases as we approach the target state. In general, P8 (probability of no change) also increases as we approach the target state, except for a decrease in the highest states of the smaller-generation cases; this is apparently due to the sudden increase in P7. However, except for that sudden increase of P7 in the highest states of the smaller-generation cases, the probability to make the next step remains higher than that of slipping back, with the probability of no change occurring becoming dominant as we approach the target state.

The reasons for this should be intuitively obvious by now. In order to advance to the next higher state, only one offspring of the new generation need advance, so the probability is fairly high. In order to slip back to the next lower state, all of the offspring must have slipped back -- which becomes much less likely as the generation size increases. So in the higher states, the most likely thing is for neither advancing nor slipping back to occur, but rather to remain in the current state.

The system is biased to either advancing or holding its ground; how could it lose? Since Darwinian evolution uses cumulative selection, there is little cause to be amazed at its uncanny ability to repeatedly and reliably generate the improbable.

### MARKOV CHAINS:

The preceeding discussion only deals with the probabilities of advancing, slipping back, or staying put in a single state. It does not and cannot deal with the probabilities of being in a given state after a given number of iterations (generations). In order to determine those probabilities, I used Michael Olinick's discussion of Markov chains (An Introduction to Mathematical Models in the Social and Life Sciences, pp 274-292, Addison-Wesley Publishing Company, 1978) to write the program, MPROBS (AKA "Monkey Probabilities").

First studied by the Russian mathematician, Andrei Andreevich Markov, Markov chains are stochastic (i.e. probabilistic) processes with a finite number of states and whose probability of being in a particular state only depends on the state occupied in the previous step. Their fundamental principle is the independence of the future from the past if the present is known; the outcome of the current step/event only depends on the current conditions, not on the outcome of the past steps.

By its very nature, a finite-state machine will be in a given state at a given time and will transition from one state to another under certain conditions. These transitions can be represented graphically with a state diagram, in which each state is represented by a vertex and each transition by a directed arc connecting the affected vertices. Each directed arc is labeled with either the conditions required for the transition or, in a stochastic state machine, with the probability of making that transition. One thing to keep in mind is that a finite-state machine will always make a transition, even if it is to the same state -- so a transition arc to the same state is common.

The most common way to define a finite-state machine is by setting up a transition matrix. In an n-state machine, such a matrix would be n-by-n such that each row would represent a current state, each column would represent a possible next state, and the element at a given row and column would describe the conditions under which the machine will transition from that current state to that next state. In a stochastic transition matrix, those elements will be the probability of making that transition.

Since a finite-state machine will always transition, it is a dead certainty (i.e. probability = 100% or 1.0). Therefore in a stochastic machine, the sum of the probabilities of all the arcs transitioning from a given state must also be 1.0. Since each row of a transition matrix holds the probabilities of all of that state's transitions, the sum of all of a row's elements must also be 1.0.

In setting up the transition matrix for our test problem, we define 27 different states, numbered from 0 to 26, thus giving us a 27x27 matrix. Since our test case only changes one letter at a time, the probability of transitioning to any non-adjacent state is zero -- in state "i", we can only transition to state "i-1", "i+1", or "i". In addition, state 0 can only transition to state 0 or to state 1 and state 26, the target state, can only transition to itself. This produces a transition matrix which is diagonal, i.e. all its elements are zero except for those along and directly alongside the diagonal. This matrix contains all the probabilities for transitioning from one state to another in a single step.

But we need to know what those probabilities are after a given number of steps. According to Olinick, for a given transition matrix, P, the probability distribution of a Markov chain after n steps is given by Pn, i.e. by matrix-multiplying P by itself n times. Needless to say, rather than multiply a 27x27 matrix by itself by hand over 50 times, I wrote a program, MPROBS, to do it for me.

Then to implement a Markov chain, we take the probability matrix for a given number of steps and multiply it by a vector containing the initial probabilities. Since in our problem we are assuming the worst case of starting in state 0, those initial probabilities are the 0'th row of the initial transition matrix. The resultant vector contains the probabilities of being in a given state after a given number of steps.

Some sample probabilities are:

String Length = 26
Character Set Size = 26
Generation Size = 100

After 2 Tries:
0.   7.76243917887951E-0006     1.   1.35501990792492E-0003
2.   6.68489384068925E-0002     3.   9.31788279246004E-0001
4.   0.00000000000000E+0000     5.   0.00000000000000E+0000
6.   0.00000000000000E+0000     7.   0.00000000000000E+0000
8.   0.00000000000000E+0000     9.   0.00000000000000E+0000
10.   0.00000000000000E+0000    11.   0.00000000000000E+0000
12.   0.00000000000000E+0000    13.   0.00000000000000E+0000
14.   0.00000000000000E+0000    15.   0.00000000000000E+0000
16.   0.00000000000000E+0000    17.   0.00000000000000E+0000
18.   0.00000000000000E+0000    19.   0.00000000000000E+0000
20.   0.00000000000000E+0000    21.   0.00000000000000E+0000
22.   0.00000000000000E+0000    23.   0.00000000000000E+0000
24.   0.00000000000000E+0000    25.   0.00000000000000E+0000
26.   0.00000000000000E+0000
Total Prob =  1.00000000000000E+0000

After 3 Tries:
0.   1.53696607123681E-0007     1.   3.88965362127042E-0005
2.   3.12336737523576E-0003     3.   9.42885227159933E-0002
4.   9.02549059675951E-0001     5.   0.00000000000000E+0000
6.   0.00000000000000E+0000     7.   0.00000000000000E+0000
8.   0.00000000000000E+0000     9.   0.00000000000000E+0000
10.   0.00000000000000E+0000    11.   0.00000000000000E+0000
12.   0.00000000000000E+0000    13.   0.00000000000000E+0000
14.   0.00000000000000E+0000    15.   0.00000000000000E+0000
16.   0.00000000000000E+0000    17.   0.00000000000000E+0000
18.   0.00000000000000E+0000    19.   0.00000000000000E+0000
20.   0.00000000000000E+0000    21.   0.00000000000000E+0000
22.   0.00000000000000E+0000    23.   0.00000000000000E+0000
24.   0.00000000000000E+0000    25.   0.00000000000000E+0000
26.   0.00000000000000E+0000
Total Prob =  1.00000000000000E+0000

After 12 Tries:
0.   7.18884155327911E-0023     1.   1.36587282061300E-0019
2.   9.95841557114434E-0017     3.   3.68726253541922E-0014
4.   7.73168212633555E-0012     5.   9.68973105291572E-0010
6.   7.46214709539537E-0008     7.   3.57266376263599E-0006
8.   1.06243918389683E-0004     9.   1.93613456774215E-0003
10.   2.09887440143447E-0002    11.   1.27968513616336E-0001
12.   3.92546433877660E-0001    13.   4.56450281743552E-0001
14.   0.00000000000000E+0000    15.   0.00000000000000E+0000
16.   0.00000000000000E+0000    17.   0.00000000000000E+0000
18.   0.00000000000000E+0000    19.   0.00000000000000E+0000
20.   0.00000000000000E+0000    21.   0.00000000000000E+0000
22.   0.00000000000000E+0000    23.   0.00000000000000E+0000
24.   0.00000000000000E+0000    25.   0.00000000000000E+0000
26.   0.00000000000000E+0000
Total Prob =  1.00000000000000E+0000

After 13 Tries:
0.   1.42339351127543E-0024     1.   3.22430406904809E-0021
2.   2.81433103572681E-0018     3.   1.25395450341657E-0015
4.   3.18450349694895E-0013     5.   4.87320308525569E-0011
6.   4.63089838944933E-0009     7.   2.77389474425751E-0007
8.   1.05148394627683E-0005     9.   2.50733046762119E-0004
10.   3.69747670988938E-0003    11.   3.26457526073730E-0002
12.   1.62818034661829E-0001    13.   4.09602108055062E-0001
14.   3.90975098010197E-0001    15.   0.00000000000000E+0000
16.   0.00000000000000E+0000    17.   0.00000000000000E+0000
18.   0.00000000000000E+0000    19.   0.00000000000000E+0000
20.   0.00000000000000E+0000    21.   0.00000000000000E+0000
22.   0.00000000000000E+0000    23.   0.00000000000000E+0000
24.   0.00000000000000E+0000    25.   0.00000000000000E+0000
26.   0.00000000000000E+0000
Total Prob =  1.00000000000000E+0000

After 24 Tries:
0.   2.61006758475300E-0043     1.   3.55150450775138E-0039
2.   1.89283776157541E-0035     3.   5.25445178210882E-0032
4.   8.52233648869593E-0029     5.   8.58796758204334E-0026
6.   5.58200103508184E-0023     7.   2.39823252801117E-0020
8.   6.92438819195425E-0018     9.   1.35871557758278E-0015
10.   1.82519317137957E-0013    11.   1.68563666036883E-0011
12.   1.07201010831148E-0009    13.   4.69106767119093E-0008
14.   1.40799220556543E-0006    15.   2.88198555797693E-0005
16.   3.98830795029074E-0004    17.   3.68643765423917E-0003
18.   2.23831616182958E-0002    19.   8.72793423715648E-0002
20.   2.11883542764748E-0001    21.   3.06564380511672E-0001
22.   2.47961717347950E-0001    23.   1.01398636037889E-0001
24.   1.75522769131906E-0002    25.   8.61398137908306E-0004
26.   0.00000000000000E+0000
Total Prob =  1.00000000000000E+0000

After 25 Tries:
0.   5.16794428781524E-0045     1.   8.22610842748171E-0041
2.   5.13038934495227E-0037     3.   1.66724904997810E-0033
4.   3.16737261359312E-0030     5.   3.74100908931385E-0027
6.   2.85237696018835E-0024     7.   1.43903523994241E-0021
8.   4.88505419830093E-0019     9.   1.12872883803522E-0016
10.   1.78876838327407E-0014    11.   1.95336035876433E-0012
12.   1.47298351980200E-0010    13.   7.66884906779809E-0009
14.   2.75003505885182E-0007    15.   6.76027406097354E-0006
16.   1.13087701875966E-0004    17.   1.27396113009890E-0003
18.   9.52754857943844E-0003    19.   4.63985566831162E-0002
20.   1.43335468463491E-0001    21.   2.70922328855997E-0001
22.   2.97623313838890E-0001    23.   1.75979849443642E-0001
24.   4.94567973091932E-0002    25.   5.24351470352053E-0003
26.   1.18530195050912E-0004
Total Prob =  1.00000000000000E+0000

After 26 Tries:
0.   1.02325504205247E-0046     1.   1.90449736470726E-0042
2.   1.38918443590897E-0038     3.   5.28169718751450E-0035
4.   1.17440487823349E-0031     5.   1.62437178889128E-0028
6.   1.45135335702137E-0025     7.   8.58754784214750E-0023
8.   3.42250720777077E-0020     9.   9.29582391761532E-0018
10.   1.73437226849661E-0015    11.   2.23394841416024E-0013
12.   1.99150644196094E-0011    13.   1.22918207215893E-0009
14.   5.24332869782812E-0008    15.   1.53970604698079E-0006
16.   3.09279046257145E-0005    17.   4.21089644095767E-0004
18.   3.83754322777901E-0003    19.   2.30154941929388E-0002
20.   8.87847201177896E-0002    21.   2.13516042333986E-0001
22.   3.06379248659897E-0001    23.   2.46012552813180E-0001
24.   9.99584395356211E-0002    25.   1.72022993375577E-0002
26.   8.40048843872012E-0004
Total Prob =  1.00000000000000E+0000

After 40 Tries:
0.   1.45649458723736E-0070     1.   2.36532314786899E-0065
2.   1.50422630241845E-0060     3.   4.98447043404008E-0056
4.   9.66112926630794E-0052     5.   1.16571749940723E-0047
6.   9.09950978492957E-0044     7.   4.71464466406131E-0040
8.   1.65074169860415E-0036     9.   3.95635195046600E-0033
10.   6.55128771314636E-0030    11.   7.54460649312992E-0027
12.   6.06953116491372E-0024    13.   3.41996404321745E-0021
14.   1.35100573601043E-0018    15.   3.73926380085322E-0016
16.   7.23446223167808E-0014    17.   9.74333643888483E-0012
18.   9.07660154038980E-0010    19.   5.79539098861826E-0008
20.   2.50388536461045E-0006    21.   7.18924772000977E-0005
22.   1.33669777410578E-0003    23.   1.54828101092095E-0002
24.   1.05396897148180E-0001    25.   3.69263025525215E-0001
26.   5.08446114209339E-0001
Total Prob =  1.00000000000000E+0000

After 53 Tries:
0.   1.04705088108580E-0092     1.   1.25649005316697E-0086
2.   5.88824908539943E-0081     3.   1.43389390800707E-0075
4.   2.03704637924722E-0070     5.   1.79690486290035E-0065
6.   1.02289451951949E-0060     7.   3.85575688482935E-0056
8.   9.79953485824100E-0052     9.   1.70123264354440E-0047
10.   2.03649230363238E-0043    11.   1.69240228468721E-0039
12.   9.80952172114997E-0036    13.   3.97704369200769E-0032
14.   1.12923741741133E-0028    15.   2.24485874926821E-0025
16.   3.11842524031036E-0022    17.   3.01583256494953E-0019
18.   2.01865665215001E-0016    19.   9.27242629385853E-0014
20.   2.88758895825400E-0011    21.   5.99257778438261E-0009
22.   8.08391514784564E-0007    23.   6.84294192596518E-0005
24.   3.62558058960004E-0003    25.   8.84950742808855E-0002
26.   9.07810101297193E-0001
Total Prob =  1.00000000000000E+0000

After 69 Tries:
0.   5.84285230686047E-0120     1.   8.20589294673473E-0113
2.   4.48375498479832E-0106     3.   1.26837941620846E-0099
4.   2.08547972077776E-0093     5.   2.12133346783483E-0087
6.   1.38742550753166E-0081     7.   5.98701983708059E-0076
8.   1.73567395559488E-0070     9.   3.42484359882105E-0065
10.   4.64345879373942E-0060    11.   4.35539939877661E-0055
12.   2.83948635563670E-0050    13.   1.29045342430994E-0045
14.   4.09357466845024E-0041    15.   9.06177835491687E-0037
16.   1.39722929954868E-0032    17.   1.49514058238668E-0028
18.   1.10395790116946E-0024    19.   5.57718757490839E-0021
20.   1.90482844411605E-0017    21.   4.32379438105615E-0014
22.   6.36889410224392E-0011    23.   6.12570828697717E-0008
24.   6.00462806622741E-0005    25.   8.98292604805135E-0003
26.   9.90956966350471E-0001
Total Prob =  1.00000000000000E+0000

After 100 Tries:
0.   9.18910221266464E-0173     1.   1.51510287746832E-0163
2.   9.64831153691716E-0155     3.   3.15781682342792E-0146
4.   5.96371987697140E-0138     5.   6.91749797424836E-0130
6.   5.12205287282496E-0122     7.   2.48436273181953E-0114
8.   8.03763487003430E-0107     9.   1.75732834924321E-0099
10.   2.62127436292282E-0092    11.   2.68580712310207E-0085
12.   1.89928675492715E-0078    13.   9.29685162248260E-0072
14.   3.15419939516307E-0065    15.   7.41573518668768E-0059
16.   1.20596879082333E-0052    17.   1.35164749471298E-0046
18.   1.03811391236184E-0040    19.   5.41789118093089E-0035
20.   1.89860194985002E-0029    21.   4.40952855446064E-0024
22.   3.58025323201934E-0018    23.   9.41157248472128E-0012
24.   3.10146599422794E-0007    25.   9.34351932814400E-0005
26.   9.99906254650708E-0001
Total Prob =  1.00000000000000E+0000

A few trends should be immediately apparent. Early on, the greatest probability is to advance (to the tune of over 90%), so most of the steps should result in transitioning to the next higher state. Then about half-way through (13 tries), the probability of having missed an advancement edges into the lead and from there on, the probability of missing a few advancements increase, as we would expect from our previous discussions.

The probability of making all 26 advancements in a row is only about .01%, but at the same time there is about a 30% chance of having made 22 out of the 26. From this point on, the probabilities of reaching the target climb sharply:

after 25 tries:   0.01%,
"   40   "  :  50.8%,
"   53   "  :  90.8%,
"   69   "  :  99.1%, and
"  100   "  :  99.99%.
Now wonder MONKEY works so well!

Of course, 100 copies per iteration is a rather generous amount which contributes greatly to this example's rapid success. Contrast the case of 20 copies per iteration:

String Length = 26
Character Set Size = 26
Generation Size = 20

After 2 Tries:
0.   9.50604010209044E-0002     1.   3.50402367892303E-0001
2.   4.06425126101306E-0001     3.   1.48112104985486E-0001
4.   0.00000000000000E+0000     5.   0.00000000000000E+0000
6.   0.00000000000000E+0000     7.   0.00000000000000E+0000
8.   0.00000000000000E+0000     9.   0.00000000000000E+0000
10.   0.00000000000000E+0000    11.   0.00000000000000E+0000
12.   0.00000000000000E+0000    13.   0.00000000000000E+0000
14.   0.00000000000000E+0000    15.   0.00000000000000E+0000
16.   0.00000000000000E+0000    17.   0.00000000000000E+0000
18.   0.00000000000000E+0000    19.   0.00000000000000E+0000
20.   0.00000000000000E+0000    21.   0.00000000000000E+0000
22.   0.00000000000000E+0000    23.   0.00000000000000E+0000
24.   0.00000000000000E+0000    25.   0.00000000000000E+0000
26.   0.00000000000000E+0000
Total Prob =  1.00000000000000E+0000

After 25 Tries:
0.   1.38887629209615E-0009     1.   6.48614847492766E-0008
2.   1.37165179649830E-0006     3.   1.74594913056761E-0005
4.   1.49983113001696E-0004     5.   9.24081914236774E-0004
6.   4.23659724469089E-0003     7.   1.48004191350264E-0002
8.   4.00230742315974E-0002     9.   8.46457644494096E-0002
10.   1.40901980068229E-0001    11.   1.85203304430084E-0001
12.   1.92332747548973E-0001    13.   1.57520306649484E-0001
14.   1.01316795948715E-0001    15.   5.08395840126470E-0002
16.   1.97162583893632E-0002    17.   5.83549821991124E-0003
18.   1.29645801197705E-0003    19.   2.11545856735814E-0004
20.   2.46302416998999E-0005    21.   1.96776341100338E-0006
22.   1.02144086095704E-0007    23.   3.18052457171944E-0009
24.   5.23687475328652E-0011    25.   3.62961785156948E-0013
26.   6.07587513931197E-0016
Total Prob =  1.00000000000000E+0000

After 35 Tries:
0.   5.44497267801217E-0013     1.   4.20586944922562E-0011
2.   1.48599958254616E-0009     3.   3.19465028627034E-0008
4.   4.68966661082308E-0007     5.   5.00072312301541E-0006
6.   4.02302007883069E-0005     7.   2.50349438983825E-0004
8.   1.22588870475529E-0003     9.   4.78006126617978E-0003
10.   1.49638063296708E-0002    11.   3.78085635648670E-0002
12.   7.73373619182511E-0002    13.   1.28199642209686E-0001
14.   1.72082016604609E-0001    15.   1.86556448336743E-0001
16.   1.62619491715375E-0001    17.   1.13233359265892E-0001
18.   6.24131820991935E-0002    19.   2.68986176724612E-0002
20.   8.91308293839282E-0003    21.   2.21791874140644E-0003
22.   4.00537100899919E-0004    23.   4.98376707044801E-0005
24.   3.92901408839593E-0006    25.   1.68369526110476E-0007
26.   3.67263673942586E-0009
Total Prob =  1.00000000000000E+0000

After 50 Tries:
0.   4.22662692437302E-0018     1.   6.12256952271774E-0016
2.   4.08474715710520E-0014     3.   1.67035730754485E-0012
4.   4.70040017738570E-0011     5.   9.68749511032835E-0010
6.   1.51958417327164E-0008     7.   1.86109852673792E-0007
8.   1.81154864136810E-0006     9.   1.41915055363535E-0005
10.   9.02763387571841E-0005    11.   4.69193006463940E-0004
12.   2.00013968162007E-0003    13.   7.00772636824696E-0003
14.   2.01853340174027E-0002    15.   4.77372916840984E-0002
16.   9.24132484254349E-0002    17.   1.45731414724306E-0001
18.   1.85878544500565E-0001    19.   1.89823580485665E-0001
20.   1.52913348031701E-0001    21.   9.49474945204797E-0002
22.   4.37387239530174E-0002    23.   1.39905479253025E-0002
24.   2.76704771983750E-0003    25.   2.71410152797763E-0004
26.   1.84730869662511E-0005
Total Prob =  1.00000000000000E+0000

After 75 Tries:
0.   1.28624667722373E-0026     1.   4.58629044077004E-0024
2.   7.56275023204864E-0022     3.   7.67710807403722E-0020
4.   5.38749066899384E-0018     5.   2.78243230455217E-0016
6.   1.09928781061242E-0014     7.   3.40927580903678E-0013
8.   8.45101250374383E-0012     9.   1.69608554292028E-0010
10.   2.78157926579224E-0009    11.   3.75196215569316E-0008
12.   4.18038667462695E-0007    13.   3.85688974070379E-0006
14.   2.94918125749554E-0005    15.   1.86801870567355E-0004
16.   9.78411632547865E-0004    17.   4.22600940092574E-0003
18.   1.49982672862656E-0002    19.   4.35283067960875E-0002
20.   1.02446613728825E-0001    21.   1.91318621198642E-0001
22.   2.66177201074569E-0001    23.   2.39620126655387E-0001
24.   1.12033236125493E-0001    25.   1.99818277035449E-0002
26.   4.47076930654938E-0003
Total Prob =  1.00000000000000E+0000

After 100 Tries:
0.   3.91430458441633E-0035     1.   3.18303144297649E-0032
2.   1.19819023348861E-0029     3.   2.77946967056498E-0027
4.   4.46227120778983E-0025     5.   5.27864711198532E-0023
6.   4.78298934278243E-0021     7.   3.40675496731194E-0019
8.   1.94231661209683E-0017     9.   8.97999803524438E-0016
10.   3.39834929966382E-0014    11.   1.05966312988066E-0012
12.   2.73475264195801E-0011    13.   5.85762503598804E-0010
14.   1.04287578221780E-0008    15.   1.54464861511338E-0007
16.   1.90587590904192E-0006    17.   1.96658701306634E-0005
18.   1.71506833555501E-0004    19.   1.29661285618246E-0003
20.   8.81529240448593E-0003    21.   5.12387016906795E-0002
22.   1.97602384566919E-0001    23.   3.72120088415403E-0001
24.   2.72877564683768E-0001    25.   6.13816162386368E-0002
26.   3.44744950565068E-0002
Total Prob =  1.00000000000000E+0000
Progress toward the target is much slower, but still the probability of success increases noticably with each iteration and the most probable state to be in continually increases toward the target. The trends are:
Prob[generating target]     Most Prob. State
after 25 tries:   6.076 E -16                  12
"   35   "  :   3.673 E -9                   15
"   50   "  :   1.847 E -5                   19
"   75   "  :   0.45 %                       22
"  100   "  :   3.45 %                       23
An even more constrained case only has 10 copies per iteration:
String Length = 26
Character Set Size = 26
Generation Size = 10

After 25 Tries:
0.   3.72676306209510E-0005     1.   5.67680609022318E-0004
2.   3.95890766851757E-0003     3.   1.67999980732499E-0002
4.   4.86367495761099E-0002     5.   1.02080390566773E-0001
6.   1.61135357554785E-0001     7.   1.95879368161121E-0001
8.   1.86265177576548E-0001     9.   1.39978839544459E-0001
10.   8.36561205330446E-0002    11.   3.98829992789633E-0002
12.   1.51745441742954E-0002    13.   4.59823631622295E-0003
14.   1.10475876258971E-0003    15.   2.08972051458642E-0004
16.   3.08156158125031E-0005    17.   3.49631649948419E-0006
18.   3.00042666329172E-0007    19.   1.90497497804253E-0008
20.   8.69454058831085E-0010    21.   2.74606763973422E-0011
22.   5.69620222713541E-0013    23.   7.19329196719772E-0015
24.   4.90279939379207E-0017    25.   1.44419406864609E-0019
26.   1.05622976229832E-0022
Total Prob =  1.00000000000000E+0000

After 50 Tries:
0.   2.05587619384557E-0009     1.   7.58576778556687E-0008
2.   1.30560788386252E-0006     3.   1.39483595899279E-0005
4.   1.03840112464947E-0004     5.   5.73292648566504E-0004
6.   2.43900726012295E-0003     7.   8.20249961107662E-0003
8.   2.21954132942406E-0002     9.   4.89344066862941E-0002
10.   8.86862897535283E-0002    11.   1.32931299574135E-0001
12.   1.65407120787205E-0001    13.   1.71139733559602E-0001
14.   1.47170956753077E-0001    15.   1.04902995212143E-0001
16.   6.16488577135449E-0002    17.   2.96158093861685E-0002
18.   1.14855339410140E-0002    19.   3.53359189521127E-0003
20.   8.42191438001999E-0004    21.   1.50649211426477E-0004
22.   1.93885512187033E-0005    23.   1.69522779840799E-0006
24.   9.26896247542500E-0008    25.   2.74430532288419E-0009
26.   6.82024044096271E-0011
Total Prob =  1.00000000000000E+0000

After 75 Tries:
0.   1.13412815733568E-0013     1.   7.79329472641509E-0012
2.   2.51249544742474E-0010     3.   5.05823804882093E-0009
4.   7.14072065902283E-0008     5.   7.52462983384211E-0007
6.   6.15196216682858E-0006     7.   4.00452005313291E-0005
8.   2.11333854869631E-0004     9.   9.16118401683077E-0004
10.   3.29338820144491E-0003    11.   9.88614601674930E-0003
12.   2.48956685694277E-0002    13.   5.27283640630151E-0002
14.   9.39526440891626E-0002    15.   1.40479052285289E-0001
16.   1.75145166485599E-0001    17.   1.79987301621223E-0001
18.   1.49640168468767E-0001    19.   9.79143801489654E-0002
20.   4.85551366698508E-0002    21.   1.73885571384113E-0002
22.   4.24127419293308E-0003    23.   6.56586619054371E-0004
24.   5.88910059642760E-0005    25.   2.62302546862337E-0006
26.   1.72791839126457E-0007
Total Prob =  1.00000000000000E+0000

After 100 Tries:
0.   6.25644034947666E-0018     1.   7.22273838299411E-0016
2.   3.92184468978272E-0014     3.   1.33325446492397E-0012
4.   3.18675414962487E-0011     5.   5.70161588652334E-0010
6.   7.93810678088748E-0009     7.   8.82751828707307E-0008
8.   7.98753672937136E-0007     9.   5.96207869055839E-0006
10.   3.70980118628193E-0005    11.   1.94016972557230E-0004
12.   8.58341633233657E-0004    13.   3.22751900911670E-0003
14.   1.03415192792850E-0002    15.   2.82109642555944E-0002
16.   6.50595082511514E-0002    17.   1.24637852615870E-0001
18.   1.91956566292230E-0001    19.   2.26173297996016E-0001
20.   1.91629335247329E-0001    21.   1.09224987354665E-0001
22.   3.91839979814567E-0002    23.   8.25996881633628E-0003
24.   9.41329351401366E-0004    25.   5.00098733454383E-0005
26.   6.82940949423364E-0006
Total Prob =  1.00000000000000E+0000

Prob[generating target]     Most Prob. State
after 25 tries:   1.056 E -22                   7
"   50   "  :   6.820 E -11                  13
"   75   "  :   1.728 E -7                   17
"  100   "  :   6.829 E -6                   19

Again, progress toward the target is much slower, but the probability of success still increases, not quite as noticably, with each iteration and the most probable state to be in still increases toward the target.

Empirically, the amount of time and number of iterations required for the preceeding three cases are (running the program on an 8MHz IBM XT):

Iterations (average of 3 runs)      Time
For  10 copies:  21136 (varied from 2784 to 51262)   22.15 min
For  20 copies:    383 (varied from 72 to 1035)      41.5 sec
For 100 copies:     42 (varied from 39 to 51)        25.6 sec
As expected, more time and more iterations are needed as the number of copies per iteration decreases (the increase in time does not seem proportional because with fewer copies each iteration takes less time). In each run, the string being generated came rapidly (within 10-15 seconds) to within a few letters of the target and then spent the rest of the time, gaining and losing ground, trying to make those last few letters.

### CONCLUSIONS:

This discussion was meant to compare the probabilities involved in the two methods of selection described by Richard Dawkins: single-step selection and cumulative selection. In applying both methods to the problem of randomly generating the alphabet in alphabetical order, we have seen that cumulative selection far surpasses single-step selection in obtaining the desired results. In calculating the probabilities involved in both methods, we have found that cumulative selection enjoys vastly greater chances for success than does single-step selection. In summary:
Single-Step      Cumulative:
10 copies      20 copies     100 copies
-----------        ---------      ---------     ----------
Prob of success
in 100 steps:   1.6244 E -37       6.829 E -6       3.45 %        99.99 %
Number of Steps
Needed:         2.0 E 37 (est.)      21,136          383           42
Time needed to
succeed:        1.5 E 26 yr (est.)   22.15 min      41.5 sec      25.6 sec

The relevance of this study to the creation/evolution issue depends on the degree to which either of the two methods models natural selection.

Natural selection works by having parent organisms reproduce, thus creating offspring which are very similar to them, yet slightly different. If more offspring are produced than can be supported by the environment, then only a fraction of the offspring will live to produce the next generation. Selective pressures exerted by the environment contribute most to determining which offspring survive to reproduce. This means that the second generation will quite probably be slightly different from the first generation. The second generation's offspring, in turn, will be slightly different from their parents and so the third generation should be even more different from the first, and so on.

Quite obviously, the cumulative selection method better describes natural selection (which should come as no surprise since Dawkins had modelled it after natural selection). Each iteration/generation builds upon the previous one. Multiple copies/offspring are produced which are very similar to yet slightly different from the original/parents. That/those copy/offspring which best fits the selection criteria is then used to produce the next iteration/generation.

The cumulative selection model does suffer from a few short-comings. First, the criterion for selection is a resemblance to the target string. This teleological view is missing from natural selection, which can only work from immediate selective pressures in the immediate environment.

This is perhaps not as big a problem as it may seem at first. Consider an analogy in the two-body problem of orbital mechanics. Even though the motion of an orbiting body is directly due to the immediate factors of velocity and gravity with no teleological view of its orbit, that orbit does nevertheless describe a conic section -- be it an ellipse, a circle, a parabola, or a hyperbola. Similarly, if for an unchanging environment there were some ideally adapted form, then the immediate selection pressures could be seen as leading to that optimal form. This would seem to handle the teleology problem.

Second, the cumulative selection model assumes an unchanging environment (since the criterion for selection does not change throughout the experiment). Changes in the environment appear to be major factors in driving evolution.

The case of a maneuvering spacecraft can be handled by the patched-conics method, wherein the spacecraft's trajectory can be described by a series of intersecting orbits, any one of which the spacecraft would follow completely if it were not to perform another maneuver. Similarly, changes in the environment could be viewed as causing changes in the final, optimal form being targeted, causing the immediate selective pressures to change and so too the direction of change taken by the population of organisms.

The teleology problem seems to be more apparent than real. One way to eliminate it would be to redesign the model to only allow immediate selection, but that would complicate both the model and its analysis. Further complexity would be introduced by allowing the "environment" within the model to change as well.

Despite the greater realism that such changes offer, this cumulative selection model does still offer insight into the source of natural selection's ability to generate the improbable with such great speed and consistency.

We have already seen not only that single-step selection is not at all capable of producing the results of cumulative selection, but also that it has nothing to do with how evolution, or even life itself, operates. For single-step selection to apply to life would require each and every generation to be created ex nihilo. Indeed, single-step selection is far more descriptive of creation and its abysmally miniscule probabilities demonstrate creation's utter dependence on miracles to make it work. Evolution, on the other hand, has no need for miracles since its probabilities for success are very good.

Ironically, creationism's probability arguments against evolution depend very heavily on requiring evolution to depend on single-step selection. Of course, we not only know this to be false, but now we also know why it is false.

First uploaded on 2001 September 05.
Updated on 2011 August 02.