Mutual Algorithmic Information, Information Non-growth, and Allele Frequency

Due to popular demand I will take a quick stab at explaining the applicability of mutual algorithmic information and the information non-growth law to an allele frequency scenario.

First, I’ll outline the allele frequency scenario.

The alleles are 1s and 0s, and the gene G a bitstring of N bits.  A gene’s fitness is based on how many 1s it has, so fitness(G) = sum(G).  The population consists of a single gene, and evolution proceeds by randomly flipping one bit, and if fitness is improved, it keeps that gene, otherwise it keeps the original.  Once fitness(G) = N, the evolutionary algorithm stops and outputs G, which consists of N 1s.  The bitstring that is N 1s will be denoted Y.  We will denote the evolutionary algorithm E, and it is prefixed on an input bitstring X of length N that will be turned into the bitstring of N 1s, so executing the pair on a universal Turing machine outputs the bitstring of 1s: U(E,X) = Y.

Second, I’ll briefly state the required background knowledge on algorithmic mutual information.

Kolmogorov complexity K(X) (also called algorithmic information) is the length of the shortest program that generates bitstring X.  The standard form is prefix free so no program used to measure Kolmogorov complexity is the prefix of any other such program.  The shortest program itself will be denoted X*, so K(X) = |X*|.  Conditional Kolmogorov complexity is the length of the shortest program P* that given input I will generate X, so K(X|I) = |P*|.  Joint Kolmogorov complexity of X and Y is the minimal program XY* necessary to generate the pair {X,Y}, so K(X,Y) = XY*.  Mutual algorithmic information I(X:Y) is a symmetrical measurement (within a constant error) of two bitstrings: I(X:Y) = I(Y:X) = K(Y) – K(Y|X*) = K(X) – K(X|Y*) = K(X) + K(Y) – K(X,Y).

Third, I’ll state the non-growth theorem.

The law of information non-growth states the deterministic processing of random bitstrings (generated by a computable probability distribution) is not expected to increase the mutual algorithmic information between X and Y.  Formally: E[I(U(R,X):Y)] <= I(X:Y), where R is a randomly generated bitstring and U(R,X) is executing the concatenated pair of bitstrings {R,X} with a universal Turing machine.

Finally, I’ll apply the theorem to the scenario.

We will say Y is the target, which according to our scenario is a bitstring of length N that consists of 1s.  X is a randomly generated bitstring of length N.  The typical random bitstring will provide no information regarding Y, so K(Y|X) = K(Y).  Consequently, there is zero mutual algorithmic information with Y, since I(X:Y) = K(Y) – K(Y|X) = 0.  The non-growth theorem says we cannot expect to increase the mutual algorithmic information through generating another random bitstring R and executing the pair with a universal Turing machine, so E[I(U(R,X):Y)] = 0.

Next, we will bring in the evolutionary algorithm E.  As stated at the beginning when E is prefixed to bitstring X of length N, and executed on a universal Turing machine, then the result is N 1s, denoted Y.  Consequently, the pair {E, X} requires no further information to generate Y and K(Y|E,X) = 0.  This means the algorithmic mutual information between {E, X} and Y is maximal: I(Y:{E, X}) = K(Y) – K(Y|E,X) = K(Y) – 0 = K(Y).

Thus, since the combination of the evolutionary algorithm E with random input string X contains all the relevant information to generate Y, the information non-growth theorem states the combination of generating another random bitstring R and executing the triplet {R, E, X} can only decrease information regarding Y: E[I(U(R,E,X):Y)] <= I(E,X:Y).

133 Replies to “Mutual Algorithmic Information, Information Non-growth, and Allele Frequency”

  1. Rumraket Rumraket
    Ignored
    says:

    Mung: So there really is no known mechanism by which evolution might move from one peak to another?

    That merely depends on the environment. Selection pressures can be relaxed by many means, and the population size can even drop so drift can dominate over selection at least for a time. There can even be competing selective pressures and variations in their magnitude can push populations around.

    Of course, the selection pressure can simply change as the environment changes, or you can move from one environment to another that differ substantially in some particular way, and as a result what constitutes an adaptive phenotype will also change.

    A peak in a fitness landscape implies some condition that favors particular phenotypes over others. A dark environment can drive a population of mice, for example, up some “dark fur” hill. A subpopulation can split off, and migrate to a bright environment, and drive that subpopulation up a “bright fur” hill. That is actually known to have happened.

  2. Joe Felsenstein Joe Felsenstein
    Ignored
    says:

    Mung:
    Once again I propose a WEASEL model with two targets.

    METHINKS IT IS LIKE A WEASEL
    LESAEW A EKIL SI TI SKNIHTEM

    What does my objective function look like in that case, how do I design it?

    (I’ll comment on the more general issue of multiple fitness peaks and Functional Information in a day or so).

    As we have no outside information on what the fitness of a string is, we can do this in various ways. We could count the number of matches of a string to string 1 and also to string 2. Call these x and y. Then the we could use pretty much any function f(x, y). Some obvious possibilities are x+y, the average
    (1/2)(x+y), and my favorite, max(x,y). The average and the sum would in effect count all matches at each position, the average would count 0, 0.5, or 1, while the sum would count double that, 0, 1, or 2.

    If you use the maximum, the behavior of the Weasel would be to more-or-less converge on whichever string accidentally had the most matches early on. There would be a small chance of switching which string has the most matches very early on, but after that, it would converge on the one with more matches.

    FI? It would increase in a straightforward way, just as it does in the one-string Weasel.

    In biological systems with fitnesses, we could have a fitness surface. For example, if the species ate two sorts of prey, one small and one large, and 60% of prey encountered were small, the size of an individual would affect how many of each it would be able to eat, and the fitness would reflect the food value of that mix. Here (in Genetics in 1979, freely readable) is such a model, in which one possible outcome, if the two fitness peaks are close enough, is for the species to approach an equilibrium phenotype between the optimum phenotypes for the two peaks. With more separated peaks, the species climbs one of them, but ends up a little off the top of that peak.

  3. J-Mac
    Ignored
    says:

    Rumraket,

    What do you have here? An “evolution” of mice within a species or a kind? Even YECs don’t deny it… neither adaptations even with adaptive mutations that break or downgrade gene functions…98 % of so-called evolutionary proof involves changes within species or kinds..
    Show me proof that new body plans can develop or are in the process of development… You can’t because everyone knows that those changes would have to take place within the cell; like during embryo development, at the molecular level. But these changes, mutations, are the most likely to be lethal…That’s why we don’t see any transitional evolutionary changes because the organism that went through such mutations is either dead or defective…With 10 billion species on earth evolving there should be a least few million of transitional changes with newer body plans…
    Unfortunately, neither observed nor lab results have ever shown such evolution…
    Until then, “speculative evolutionary proof” abounds…

  4. Rumraket Rumraket
    Ignored
    says:

    Joe Felsenstein: Here (in Genetics in 1979, freely readable) is such a model, in which one possible outcome, if the two fitness peaks are close enough, is for the species to approach an equilibrium phenotype between the optimum phenotypes for the two peaks. With more separated peaks, the species climbs one of them, but ends up a little off the top of that peak.

    There’s a nice visualization of a similar scenario in this youtube video Using fitness landscapes to visualize evolution in action.

  5. Joe Felsenstein Joe Felsenstein
    Ignored
    says:

    That’s great. Randy Olson specializes in how to best teach about evolution, and this shows he knows how to do that well.

  6. Joe Felsenstein Joe Felsenstein
    Ignored
    says:

    … except I’m not sure that this is the same Randy Olson. Both seem to have done good jobs.

  7. phoodoo
    Ignored
    says:

    J-Mac: With 10 billion species on earth evolving there should be a least few million of transitional changes with newer body plans…

    The evolutionists only argument for this seems to be, “But what does new mean, what is new?”

    Which is a meaningless objection, because if we don’t agree about what the word new means, should they even be engaging in public discussion; perhaps it would be better if they just conversed with others in the facility about what is for lunch.

  8. dazz dazz
    Ignored
    says:

    phoodoo,

    What should we expect to see according to you, if “some species” was evolving a new body plan? Go ahead, phoodoo and J-Mac. Entertain us 😀

  9. Rumraket Rumraket
    Ignored
    says:

    phoodoo: Which is a meaningless objection, because if we don’t agree about what the word new means, should they even be engaging in public discussion; perhaps it would be better if they just conversed with others in the facility about what is for lunch.

    Why don’t you just define new then? Give a general definition we can apply in a lot of circumstances. See the problem is that when you have asked for examples of something “new”, we then give examples we think count, but then you just come up with some ad-hoc reason for why it isn’t new in the sense of new you totally, totally had in mind before and didn’t make up on the spot to avoid admitting something new evolved.

    So I’ve given a definition of new to go by, but you seem to have just ignored it. What would be new to you? How much must some shape change, how far must some attribute move, how much must some entity grow or shrink, how different must some sequence be, before it begins to count as “new” in your mind?

  10. Rumraket Rumraket
    Ignored
    says:

    dazz:
    phoodoo,

    What should we expect to see according to you, if “some species” was evolving a new body plan? Go ahead, phoodoo and J-Mac. Entertain us

    Inb4 he wants to see a member of a species without eyes, give birth to a species with eyes. In the past he has just given examples of radical transitions he wants to see, and avoids giving definitions (instead of radical examples) of new.

    Even were that to happen, phoodoo would just declare that it is impossible that it happened “by happy accident” because he has decided in his head it is impossible.

    The entirety of his position is based on having an absurd standard of evidence, the absense of a stated definition of new not actually compatible with evolutionary timescales (so he can always just claim whatever example is given doesn’t satisfy his demand), and a philosophical commitment to the impossibility of random change.

  11. dazz dazz
    Ignored
    says:

    Rumraket: Inb4 he wants to see a member of a species without eyes, give birth to a species with eyes. In the past he has just given examples of radical transitions he wants to see, and avoids giving definitions (instead of radical examples) of new.

    Yeah. Their tiny little brains can’t possibly shake those ridiculous creotard preconceptions about how novelties arise. It’s *poof* or nothing. So basic stuff like all species are transitional, every step in the way is fully formed, etc. they simply can’t wrap their heads around concepts like gradual change.

  12. J-Mac
    Ignored
    says:

    phoodoo: The evolutionists only argument for this seems to be, “But what does new mean, what is new?”

    Which is a meaningless objection, because if we don’t agree about what the word new means, should they even be engaging in public discussion; perhaps it would be better if they just conversed with others in the facility about what is for lunch.

    I have given the Darwinian believers ample opportunities to prove their theory experimentally.
    I’ve asked them first to grow a bacteria in the lab with a defective flagellum or to delete the gene for the flagellum and see if the bacterium either evolves an alternative flagellum or propeller or something even remotely resembling a flagellum…
    They said that I ask them to kill the bacterium by damaging or removing the measure of survival (the flagellum), so of course it’s not going to evolve.
    So, my question still remains: if bacterium can’t survive without a flagellum or with a defective flagellum, how did it evolve without a functioning flagellum it in the first place? I guess it used a paddle or it was another evolutionary miracle…
    What else?

    ETA: maybe Darwinists can ask Dr. Swamidass to pray for God’s guidance for bacterium without a flagellum to evolve one? Lol

  13. dazz dazz
    Ignored
    says:

    J-Mac: I’ve asked them first to grow a bacteria in the lab with a defective flagellum or to delete the gene for the flagellum and see if the bacterium either evolves an alternative flagellum or propeller or something even remotely resembling a flagellum…

    Been done. Well known experiment. So what now?

  14. J-Mac
    Ignored
    says:

    phoodoo: The evolutionists only argument for this seems to be, “But what does new mean, what is new?”

    The only thing new that species grow are tumors…

    If evolution were true, at least veterinarians would be reporting some of the animals transitioning and growing some future parts of bones, tissues or anything…
    Dog breeders still breed dogs and no new or transitional parts develop…the ” new” dog breeds are the continuations of broken genes of wolf…
    Darwinists specialize in speculative science… no hard evidence will ever be presented because there is none…
    Now you can read the excuses.. I won’t

  15. DNA_Jock
    Ignored
    says:

    J-Mac: They said that I ask them to kill the bacterium by damaging or removing the measure of survival (the flagellum), so of course it’s not going to evolve.

    Citation please. I do not believe that any such conversation ever took place.
    It took me ten seconds to find a counter-example online. I’ll bet there are others.

  16. J-Mac
    Ignored
    says:

    DNA_Jock: Citation please. I do not believe that any such conversation ever took place.
    It took me ten seconds to find a counter-example online. I’ll bet there are others.

    I guess wasn’t specific enough… Everyone knows that damaged cells have the ability to repair themselves including the cell membrane…to a certain degree of course. The repair of flaggelar motiality is not an example evolution but rather a repair mechanism…there are better examples of bacteria self-repair including DNA…

    Evolutionary resurrection of flagellar motility via rewiring of the nitrogen regulation system
    The ability to adapt to changes in the function of gene regulators, as opposed to structural genes, is a crucial aspect of evolutionary change. Taylor et al. mutated a central regulator for the formation of flagella in the bacterium Pseudomonas fluorescens. They then put the mutated flagella-free bacteria under strong selection pressure to regain mobility. The mutated bacteria regained the lost flagella, and motility, within 4 days. Two stereotypical mutations diverted an evolutionarily related regulator that normally controls nitrogen uptake to control flagella biosynthesis. The mutations increased the levels of the co-opted regulator, then altered its specificity for the flagella pathway.

    I was referring to the ability of the flagellum to evolve the loss of structure of the flagellum or anything new that would resemble a flagellum… or If the flagellum were able to evolve an alternative propeller…
    Or a bacteria without a flagellum evolving anything resembling a flagellum…

    Just like my last OP on the theme…
    http://theskepticalzone.com/wp/the-flagellum-the-icon-of-courage-by-michael-behe/

    I didn’t notice your comments there… You don’t have the confidence to try to challenge ID and grow a bacterium without a flagellum or the one with a structural damage in lab with your experimental experience? Why wouldn’t you take on such a task? If nothing in biology makes sense except in light of evolution, why not prove that evolution makes sense first?

  17. phoodoo
    Ignored
    says:

    dazz:
    phoodoo,

    What should we expect to see according to you, if “some species” was evolving a new body plan? Go ahead, phoodoo and J-Mac. Entertain us

    Well how about at least light sensitive spots galore, and maybe some even with crazy mutations that help some of those light spots focus? Is that too much to ask? Why do eyes have to stop at two? Where is the subset of humans with light sensitive spots on their back, surely New Yorkers would find that useful .

  18. phoodoo
    Ignored
    says:

    Rumraket,

    When you say define, I have no idea what you mean. Can you explain? Also the word the. I don’t know which the you are using.

    I think they are having meatloaf today!

  19. phoodoo
    Ignored
    says:

    J-Mac,

    I think we have to go into a long dissertation about what we mean when we say SOME of the population in a species. That apparently is also too complicated of a concept.

    I want to know when a few mutation for the beginnings of a rubics cube that applies sunscreen has begun to emerge. But just the beginning part!

  20. J-Mac
    Ignored
    says:

    phoodoo:
    J-Mac,

    I think we have to go into a long dissertation about what we mean when we say SOME of the population in a species.That apparently is also too complicated of a concept.

    I want to know when a few mutation for the beginnings of a rubics cube that applies sunscreen has begun to emerge.But just the beginning part!

    Just because there is no clear definition of species, don’t you think?
    If it were it would kill at least some of the evolutionary nonsense…

  21. phoodoo
    Ignored
    says:

    I want to see if it confers any reproductive advantage.

  22. J-Mac
    Ignored
    says:

    phoodoo,

    Ignore the ocapi clown troll…

  23. J-Mac
    Ignored
    says:

    phoodoo:
    I want to see if it confersany reproductive advantage.

    See? You are going to see speculation that’s all you are going to SEE…

  24. DNA_Jock
    Ignored
    says:

    J-Mac,

    You appear to be admitting that no such

    They said that I ask them to kill the bacterium by damaging or removing the measure of survival (the flagellum), so of course it’s not going to evolve.

    conversation ever took place. Good to hear that.
    The remainder of your comment is incoherent, although it is refreshingly honest of you to admit that you did not notice my comment on your “icon of courage” thread. That would explain why you did not respond. For a while there, I just assumed that you had no answer. My apologies.

  25. Rumraket Rumraket
    Ignored
    says:

    phoodoo:
    Rumraket,

    When you say define,I have no idea what you mean.Can you explain?Also the word the. I don’t know which the you are using.

    I think they are having meatloaf today!

    What are you so afraid of?

  26. Joe Felsenstein Joe Felsenstein
    Ignored
    says:

    BruceS: Yes, I think this is the root cause why arguments from consensus science fail to convince ID theorists.

    Eric made this comment at in Gregory’s thread on PS:“[PS’s goal] is to keep science metaphysically neutral, but I don’t think that’s possible to do while being faithful to the mathematical truth.”

    I am not sure of the details of what Eric meant, but I would parse the ID position like this:

    1.Reality is fundamentally mathematical (The cosmologist Tegmark holds this position as well).
    2.Mathematicians have access to that fundamental reality through sound proofs.
    3.Eric’s proof (based on consensus math in Levin) issound and so provides fundamental truths about reality.
    4.Eric’s proof shows that observed increases in fitness cannot be explained by naturalistic processes, which for him that means determinism+randomness. Such process are always Turing computable and conversely.
    5.Hence a non-Turing-computable process must underlie observed fitness increases.
    6.Halting oracles go beyond Turing computability and are logically and hence mathematically possible.
    7.Intelligence implements non-Turing computability (Godel and Penrose and Lucas believe this).Hence intelligence can explain observed fitness increases.

    It’s not clear to me how to argue against that position, given that one accepts 1, 2, 3.I don’t see anything in incoherent in accepting them.

    I’m not saying I do.I am just saying that I cannot think of a knock-down argument for rejecting them.

    Thanks, BruceS. This rings true as a description of how ID advocates are thinking. It is very helpful, explaining, for example, why they are so insistent on evolution having targets.

    I wonder whether it would not be helpful to have a separate thread on this.

  27. Neil Rickert
    Ignored
    says:

    Joe Felsenstein: I wonder whether it would not be helpful to have a separate thread on this.

    Probably not. But feel free to start such a thread if you want to try.

    The trouble is that the ID proponents are unlikely to engage in such a thread.

  28. J-Mac
    Ignored
    says:

    Joe Felsenstein: I wonder whether it would not be helpful to have a separate thread on this.

    1+1 +omnipotent natural selection =3?

    You could do a separate thread on evolutionary SEARCH that would have to use Grover’s Algorithm…
    I have pointed it out on Tom English’s thread that such evolutionary process is beyond classical information and classical evolutionary search … It would have to have involved quantum processes and more so Grover’s Algorithm, which is optimal. “What this means, in simple terms describing quantum mechanics, it that IF the fundamental blocks of life, like DNA 4 base pairs, and 20 amino-acids used by life systems, have evolved, they had to have used Grover’s quantum searching algorithm for optimal, error free replication… ”
    But since evolution is not search…aapparently.. it must have been another evolutionary miracle…

    http://theskepticalzone.com/wp/evo-info-4-non-conservation-of-algorithmic-specified-complexity/comment-page-2/#comment-238328

  29. BruceS
    Ignored
    says:

    Joe Felsenstein: It is very helpful, explaining, for example, why they are so insistent on evolution having targets.

    I’m glad you enjoyed it, Joe. I’m not sure the argument I made would stand up to detailed scrutiny by someone with walto’s experience in dissecting such things, but it seems to me to capture something about the stalemate.

    I don’t have much more to say for an OP, and Neil is no doubt right about participation by ID proponents.

    So I’ll leave it with this: One person’s modus ponens is another person’s modus tollens

    Biologist (modus ponens)
    1 If naturalistic, biological evolution can add information then conservation of information does not apply to biology.
    2. Naturalistic, biological evolution can add information.
    3. Therefore, conservation of information does not apply to biology.

    ID Proponent: (modus tollens)
    1. If naturalistic, biological evolution can add information then conservation of information does not apply to biology.
    2. Conservation of information is a math result that always applies.
    3. Therefore, naturalistic, biological evolution cannot add information.

  30. BruceS
    Ignored
    says:

    EricMH: .A very smooth landscape with steep gradient leads to rapid increase.A very bumpy or flat landscape leads to slow increase, and getting stuck if we cannot explore widely enough. […] a halting oracle becomes more of a necessity to make rapid enough progress to survive [ in some landscapes]..

    Eric: In case you check this thread before your detailed response:

    The landscape variation that you describe illustrates the limitation of using a population of size one only.

    Consider a population of bacteria exposed to a new, effective antibiotic. Then most sub-populations will find it impossible to increase the max fitness within the population fast enough to reach high enough in the fitness landscape to so that some members survive and reproduce. (It is not needed to reach a peak, as others have pointed out, but there will be a minimum requirement to be reached).

    However, in the real world we find that, eventually, the total population of bacteria is big enough to evolve resistance, ie to reach the required fitness level in the new landscape.

    To fully allow for fitness landscape variation, your revised model has to account for this somehow. Three ideas that occurred to me:
    1. Using a string consisting of independently mutating subsegments to represent the aggregate genome of a population.
    2. Some kind of analysis leading to the minimum population size needed to reach a new fitness level but still staying with populations of size one.
    3. Somehow biasing the mutation in the single-individual population to reflect population size.

  31. Joe Felsenstein Joe Felsenstein
    Ignored
    says:

    BruceS: 2. Naturalistic, biological evolution can add information.
    3. Therefore, conservation of information does not apply to biology.

    Number 3 may be true, but in a limited way. Information becomes embodied in a biological system as a result of processes that involve energy flows and increase of entropy. So I am hopeful that, down the road, some generalization can be made, perhaps some quantity conserved, that involves all these. But we don’t know yet what that generalization might be.

  32. Joe Felsenstein Joe Felsenstein
    Ignored
    says:

    BruceS:

    So I’ll leave it with this:

    2. Conservation of information is a math result that always applies.

    To this assertion of theirs I give the Scotch Verdict: Not Proven. I cannot see how it applies, for example, to my gene frequency case.

  33. Mung Mung
    Ignored
    says:

    Joe Felsenstein: But we don’t know yet what that generalization might be.

    The second law of bio-thermodynamics?

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.