  A new approach to understanding evolution [Val09], namely viewing it through
the lens of computation, has already started yielding new insights, e.g.,
natural selection under sexual reproduction can be interpreted as the
Multiplicative Weight Update (MWU) Algorithm in coordination games played among
genes [CLPV14]. Using this machinery, we study the role of mutation in changing
environments in the presence of sexual reproduction. Following [WVA05], we
model changing environments via a Markov chain, with the states representing
environments, each with its own fitness matrix. In this setting, we show that
in the absence of mutation, the population goes extinct, but in the presence of
mutation, the population survives with positive probability. On the way to
proving the above theorem, we need to establish some facts about dynamics in
games. We provide the first, to our knowledge, polynomial convergence bound for
noisy MWU in a coordination game. Finally, we also show that in static
environments, sexual evolution with mutation converges, for any level of
mutation.
