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)mEven 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 pSubstituting 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 37So 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:
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:
- a previously incorrect letter is changed to a correct letter,
- a previously correct letter is changed to an incorrect letter,
- a previously incorrect letter is changed to an incorrect letter, or
- a previously correct letter is changed to an correct letter.
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/nThe 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)/ncIn 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)3Now 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)mRather 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 .8633Some 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+0000A 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+0000Progress 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 % 23An 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 19Again, 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 secAs 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 secThe 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.
Return to DWise1's "Monkey" Page
Return to DWise1's Creation/Evolution Links Page
Return to DWise1's Creation/Evolution Home Page
First uploaded on 2001 September 05.
Updated on 2011 August 02.