Raphaël Cerf Dma
email: rcerf@math.u-psud.fr

The quasispecies regime for the simple genetic algorithm with ranking selection

We study the simple genetic algorithm with a ranking selection mechanism (linear ranking or tournament). We denote by the length of the chromosomes, by m the population size, by pC the crossover probability and by pM the mutation probability. We introduce a parameter σ, called the strength of the ranking selection, which measures the selection intensity of the fittest chromosome. We show that the dynamics of the genetic algorithm depend in a critical way on the parameter π = σ(1 -pC )(1 -pM ) .

If π < 1, then the genetic algorithm operates in a disordered regime: an advantageous mutant disappears with probability larger than 1 -1/m β , where β is a positive exponent. If π > 1, then the genetic algorithm operates in a quasispecies regime: an advantageous mutant invades a positive fraction of the population with probability larger than a constant p * (which does not depend on m). We estimate next the probability of the occurrence of a catastrophe (the whole population falls below a fitness level which was previously reached by a positive fraction of the population). The asymptotic results suggest the following rules: • π = σ(1 -pC )(1 -pM ) should be slightly larger than 1;

• pM should be of order 1/ ; • m should be larger than ln ;

• the running time should be at most of exponential order in m. The first condition requires that pM + pC < ln σ. These conclusions must be taken with great care: they come from an asymptotic regime, and it is a formidable task to understand the relevance of this regime for a real-world problem. At least, we hope that these conclusions provide interesting guidelines for the practical implementation of the simple genetic algorithm.

Introduction

Genetic algorithms are search procedures based on the genetic mechanisms which guide natural evolution: selection, crossover and mutation. The most cited initial references on genetic algorithms are the beautiful books of Holland [START_REF] Holland | Adaptation in natural and artificial systems[END_REF], who tried to initiate a theoretical analysis of these processes, and of Goldberg [START_REF] Goldberg | Genetic algorithms in search, optimization and machine learning[END_REF], who made a very attractive exposition of these algorithms. The success of genetic algorithms over the years has been amazing. They have been used to attack optimization problems of every possible kind. Numerous variants, extensions and generalizations of the basic genetic algorithms have been developed. The literature on genetic algorithms is now so huge that it is beyond my ability to compile a decent reasonable review. Unfortunately, the theoretical understanding of the mechanisms at work in genetic algorithms is still far from satisfactory.

We study here the simple genetic algorithm with a ranking selection mechanism. Ranking selection means that the selection mechanism depends only on the ranking of the chromosomes according to the fitness function. We consider mainly two popular selection mechanisms: linear ranking selection and tournament selection. The simple genetic algorithm operates on binary strings of length , called the chromosomes. The population size is denoted by m. We use the standard single point crossover and the crossover probability is denoted by p C . We use independent parallel mutation at each bit and the mutation probability is denoted by p M . We introduce a parameter σ, called the strength of the ranking selection, which measures the selection intensity of the fittest chromosome. For linear ranking selection with parameters η -, η + , the strength of the ranking selection σ is equal to η + . For tournament selection with parameter t, the strength of the ranking selection σ is equal to t. We show that the dynamics of the simple genetic algorithm depend in a critical way on the parameter π = σ(1 -p C )(1 -p M ) .

Heuristically, the parameter π might be interpreted as the mean number of offspring of the fittest chromosome from one generation to the next. We prove that:

• If π < 1, then the genetic algorithm operates in a disordered regime: an advantageous mutant disappears with probability larger than 1 -1/m β , where β is a positive exponent.

• If π > 1, then the genetic algorithm operates in a quasispecies regime: an advantageous mutant invades a positive fraction of the population with probability larger than a constant p * (which does not depend on m).

These results hold in the limit of large populations, when m grows to ∞.

One is naturally led to think that the parameters of the genetic algorithm should be adjusted so that π is larger than 1. Yet we think that the most interesting regime is when π is only slightly larger than 1. Indeed, in order to increase π, the mutation and crossover probabilities p M and p C should be decreased and this would slow down the exploration of the space. However an efficient search procedure should realize a delicate balance between the exploration mechanism and the selection mechanism. This general idea is present in numerous works dealing with random optimization [START_REF] Ochoa | Error Thresholds and Optimal Mutation Rates in Genetic Algorithms[END_REF][START_REF] Rogers | Phase transitions and symmetry breaking in genetic algorithms with crossover[END_REF][START_REF] Van Nimwegen | Optimizing epochal evolutionary search: Population-size dependent theory[END_REF].

Another reason is that we wish to avoid the premature convergence of the genetic algorithm, i.e., an excessive concentration of the population on the current best chromosome. This problem has been encountered in practice and it is discussed in several works on genetic algorithms (see for instance [START_REF] Rocha | Preventing premature convergence to local optima in genetic algorithms via random offspring generation[END_REF][START_REF] Xu | Characteristic analysis and prevention on premature convergence in genetic algorithms[END_REF][START_REF] Zhao | The Markov chain analysis of premature convergence of genetic algorithms[END_REF]). It seems therefore more judicious to choose "large" values of p M and p C compatible with the condition π > 1. This means that the mutation probability should be of order 1/ ; more precisely, the condition π > 1 implies that p M + p C < ln σ .

In particular, the crossover probability cannot be too large in order to avoid the disordered regime. It has already been observed in the practice of genetic algorithms that it is sensible to take the mutation probability p M of the same order than 1/ . Another outcome of our study concerns the occurrence of a catastrophe and the influence of the population size. Loosely speaking, a catastrophe occurs if the whole population falls below a fitness level which was previously reached by a positive fraction of the population. A straightforward strategy to prevent the occurrence of a catastrophe is to use "elitism", i.e., to retain automatically the best chromosome from one generation to another. Yet, in the quasispecies regime, the simple genetic algorithm is robust enough to avoid catastrophes for a very long time. We prove that, when π > 1, a catastrophe occurs typically after a number of generations which is of exponential order in m, in fact of order exp(c * m), where c * is a constant depending on π only. With a small population size, the danger is that a catastrophe might occur before the genetic algorithm succeeds in finding an advantageous mutant. Thus the genetic algorithm will work efficiently only if the population size is sufficiently large. Suppose that the population is stuck on a local maximum. The typical time to discover an advantageous mutant is of order p -∆ M , where 0 ≤ ∆ ≤ and ∆ depends on the current population (rigorous estimates were derived in [START_REF] Cercueil | Sharp asymptotics for fixation times in stochastic population genetics models at low mutation probabilities[END_REF]). We wish to ensure that, with high probability, this discovery will occur before a catastrophe. So we should have

m ∆ c * ln 1 p M .
A natural strategy would be to take m very large. Yet there is another practical constraint: we wish to minimize the number of evaluations of the fitness function. Therefore we aim for the smallest population size compatible with the desired goal. To take into account these contradictory constraints, we suggest that the parameters σ, p C , p M , , m should be adjusted according to the following rules:

• π = σ(1 -p C )(1 -p M ) should be slightly larger than 1;

• p M should be of order 1/ ;

• m should be larger than ln ;

• the running time should be at most of exponential order in m.

These conclusions must be taken with great care: they come from an asymptotic regime, and it is a formidable task to understand the relevance of this regime for a real-world problem. At least, we hope that these conclusions provide interesting guidelines for the practical implementation of the genetic algorithm.

We provide also sufficient conditions on the fitness function f ensuring that, starting from any population, the hitting time of the optimal chromosomes is polynomial in . We close with a condition ensuring the concentration of the invariant probability measure of the genetic algorithm on populations containing optimal chromosomes. This condition reads:

π = σ(1 -p C )(1 -p M ) > 1 , p M ≥ c * , m ≥ m 0 , m ≥ c * ln .
Here c * and m 0 are constants depending on π only. This result is certainly less relevant in practice than the previous ones, however it demonstrates the asymptotic validity of the genetic algorithm and it is reassuring to know that the genetic algorithm works in this asymptotic regime. The other good news is that this condition holds uniformly with respect to the fitness function. Hence a population of size of order ln is enough to search an arbitrary function on the space { 0, 1 } . By the way, the results obtained here vindicate a conjectural picture outlined in [START_REF] Cerf | Critical control of a genetic algorithm[END_REF]. Namely, the genetic algorithm running on a fitness landscape is a finite population model, approximating an infinite population model. This infinite model presents several phase transitions, depending on the geometry of the fitness landscape. In a way, there is a phase transition associated to each local maximum.

The results presented here have been derived with the help of ideas coming from the quasispecies theory. In 1971, Manfred Eigen analyzed a simple system of replicating molecules and demonstrated the existence of a critical mutation rate, called the error threshold [START_REF] Eigen | Self-organization of matter and the evolution of biological macromolecules[END_REF]. This fundamental result led to the notion of quasispecies developed by Eigen, McCaskill and Schuster [START_REF] Eigen | The molecular quasi-species[END_REF]. If the mutation rate exceeds the error threshold, then, at equilibrium, the population is completely random. If the mutation rate is below the error threshold, then, at equilibrium, the population contains a positive fraction of the Master sequence (the most fit macromolecule) and a cloud of mutants which are quite close to the Master sequence. This specific distribution of individuals is called a quasispecies.

Several researchers have already argued that the notion of error threshold plays a role in the dynamics of a genetic algorithm. This is far from obvious, because Eigen's model is formulated for an infinite population model. However there is evidence that a similar phenomenon occurs in finite populations as well, and also in genetic algorithms. In her PhD thesis [START_REF] Ochoa | Error Thresholds and Optimal Mutation Rates in Genetic Algorithms[END_REF], Ochoa demonstrated the occurrence of error thresholds in genetic algorithms over a wide range of problems and landscapes. This very interesting work is published in a series of conference papers [START_REF] Ochoa | Consensus sequence plots and error thresholds: Tools for visualising the structure of fitness landscape[END_REF][START_REF] Ochoa | Setting the mutation rate: Scope and limitations of the 1/L heuristic[END_REF][START_REF] Ochoa | Error thresholds in genetic algorithms[END_REF][START_REF] Ochoa | Optimal mutation rates and selection pressure in genetic algorithms[END_REF][START_REF] Ochoa | Recombination and error thresholds in finite populations[END_REF][START_REF] Ochoa | Error thresholds and their relation to optimal mutation rates[END_REF][START_REF] Ochoa | On recombination and optimal mutation rates[END_REF]. One of the most interesting and inspiring works on the theory of genetic algorithms that I have read over the last years is the series of papers by van Nimwegen, Crutchfield and Mitchell [START_REF] Van Nimwegen | Metastable evolutionary dynamics: Crossing fitness barriers or escaping via neutral paths[END_REF][START_REF] Van Nimwegen | Optimizing epochal evolutionary search: Population-size independent theory[END_REF][START_REF] Van Nimwegen | Optimizing epochal evolutionary search: Population-size dependent theory[END_REF][START_REF] Van Nimwegen | Finite populations induce metastability in evolutionary search[END_REF][START_REF] Van Nimwegen | Statistical dynamics of the royal road genetic algorithm[END_REF]. In these papers, the authors perform a theoretical and experimental study of a genetic algorithm on a specific class of fitness functions. Their analysis relies on techniques from mathematical population genetics, molecular evolution theory and statistical physics. Among the fundamental ingredients guiding the analysis are the quasispecies model, the error threshold and metastability. In the last work of the series [START_REF] Van Nimwegen | Optimizing epochal evolutionary search: Population-size dependent theory[END_REF], van Nimwegen and Crutchfield describe an entire search effort surface and they introduce a generalized error threshold in the space of the population size and the mutation probability delimiting a set of parameters where the genetic algorithm proceeds efficiently. In a genetic algorithm, the crossover operator complicates the dynamics and either it shifts the critical points or it creates new ones. This phenomenon has been observed independently by Rogers, Prügel-Bennett and Jennings [START_REF] Rogers | Phase transitions and symmetry breaking in genetic algorithms with crossover[END_REF] and by Nilsson Jacobi and Nordahl [START_REF] Nilsson | Quasispecies and recombination[END_REF].

A version of the quasispecies theory was recently worked out in the context of a classical model of population genetics, namely the Wright-Fisher model [START_REF] Cerf | Critical population and error threshold on the sharp peak landscape for the Wright-Fisher model[END_REF][START_REF] Dalmau | The distribution of the quasispecies for the Wright-Fisher model on the sharp peak landscape[END_REF]. The Wright-Fisher model corresponds exactly to a genetic algorithm without crossover. Let us explain briefly why quasispecies theory is relevant to understand the dynamics of a genetic algorithm. Typically, on a complicated landscape, the evolution of the genetic algorithm proceeds by jumps. The population stays for a long time exploring the space around the current best fit chromosome, until it discovers a better chromosome. If this discovery time is very long, the process reaches a local equilibrium and the distribution of the population looks like a quasispecies. Our goal here is to estimate the persistence time of this quasispecies, i.e., the time the quasispecies stays alive until it is destroyed by a catastrophe. The persistence time depends in a complicated way on the structure of the fit-ness landscape. The persistence time depends also on the population size. If the population size is large, the genetic algorithm will be able to keep an interesting quasipecies alive for a long time, long enough until a new advantageous mutant is discovered and creates a new quasispecies. We shall obtain a simple lower bound on the persistence time of the fittest chromosomes by comparing the genetic algorithm with a family of simpler processes, which are amenable to rigorous mathematical analysis.

A very interesting conclusion of [START_REF] Van Nimwegen | Optimizing epochal evolutionary search: Population-size dependent theory[END_REF] is the existence of a critical population size below which it is practically impossible to reach the global optimum. A similar conclusion was obtained in the simpler framework of the generalized simulated annealing [START_REF] Cerf | Une théorie asymptotique des algorithmes génétiques[END_REF]: within a specific asymptotic regime of low mutations and high selection pressure, the convergence to the global maximum could be guaranteed only above a critical population size. The approach presented here confirms this prediction. The genetic algorithm is very unlikely to reach the global optimum if the population size is too small. If the population size is too large, the genetic algorithm will evolve slowly and will require too many evaluations of the fitness function. The optimal population size seems to depend strongly on the optimization problem. In any case a population size of order c * ln should be enough to search the space of chromosomes of length (here again c * is a constant depending on π only).

Technically, we study the genetic algorithm within the framework of the theory of Markov chains. It has been noted numerous times in the literature that a genetic algorithm is conveniently modelled as a Markov chain. Several researchers have studied genetic algorithms in this context, here is a selection of works belonging to this line of research: [START_REF] Bäck | Theory of genetic algorithms[END_REF][START_REF] Bérard | Genetic algorithms in random environments: two examples[END_REF][START_REF] Eiben | Global convergence of genetic algorithms: a Markov chain analysis[END_REF][START_REF] Greenhalgh | Convergence criteria for genetic algorithms[END_REF][START_REF] Löwe | On the convergence of genetic algorithms[END_REF][START_REF] Lozano | Genetic algorithms: bridging the convergence gap[END_REF][START_REF] Mak | A Markov chain analysis of genetic algorithms with individuals having different birth and survival rates[END_REF][START_REF] Ming | Convergence rate of a class of genetic algorithms[END_REF][START_REF] Nakama | Markov chain analysis of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noise[END_REF][START_REF] Nix | Modeling genetic algorithms with Markov chains[END_REF][START_REF] Schmitt | Theory of genetic algorithms[END_REF][START_REF] Schmitt | Theory of genetic algorithms. II. Models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling[END_REF][START_REF] Ben Xu | Almost sure convergence of genetic algorithms: a martingale approach[END_REF][START_REF] Zhao | The Markov chain analysis of premature convergence of genetic algorithms[END_REF][START_REF] Suzuki | A Markov chain analysis of genetic algorithms: large deviation principle approach[END_REF]. Unfortunately, the transition matrix is very complicated and the resulting formulas are intractable. Our strategy is to consider a specific asymptotic regime. Twenty years ago, in [START_REF] Cerf | Une théorie asymptotique des algorithmes génétiques[END_REF], an asymptotic regime corresponding to the simulated annealing was studied. In this regime, the space { 0, 1 } and the population size were kept fixed, while the mutation probability was sent to 0 and the selection strength to ∞. It was then possible to analyze precisely the asymptotic dynamics of the population. Several other interesting results have been obtained in this regime, in particular, the understanding of the asymptotic dynamics helped to design potentially more efficient variants of the genetic algorithm [START_REF] Rigal | A new genetic algorithm specifically based on mutation and selection[END_REF][START_REF] François | Global optimization with exploration/selection algorithms and simulated annealing[END_REF][START_REF] Francois | An evolutionary strategy for global minimization and its markov chain analysis[END_REF][START_REF] Del Moral | On the convergence and applications of generalized simulated annealing[END_REF]. Although this regime made it possible to derive rigorous convergence results, it turned out to be irrelevant in practice, because it is certainly not the correct regime of parameters to run efficiently a genetic algorithm. Another interesting approach based on the Feynman-Kac formula was developed by Del Moral and Miclo [START_REF] Del Moral | Asymptotic results for genetic algorithms with applications to nonlinear estimation[END_REF][START_REF] Del Moral | Genealogies and increasing propagation of chaos for Feynman-Kac and genetic models[END_REF][START_REF] Del | Dynamiques recuites de type Feynman-Kac: résultats précis et conjectures[END_REF]. Several other works have considered other asymptotic approximations on specific fitness landscapes [START_REF] Bérard | Sharp asymptotic results for simplified mutation-selection algorithms[END_REF][START_REF] Bérard | Genetic algorithms in random environments: two examples[END_REF][START_REF] Dombry | A weighted random walk model, with application to a genetic algorithm[END_REF][START_REF] Mazza | On the effect of selection in genetic algorithms[END_REF]. Here we consider the asymptotic regime corresponding to the quasispecies theory in a finite population, namely:

• The size m of the population goes to ∞.

• The length of the chromosomes is large.

• The mutation probability is of order 1/ .

We are able to derive various estimates in this specific asymptotic regime. We hope that these results will be relevant in practice. The proofs use various tools from the theory of Markov chains: coupling techniques, Galton-Watson processes, large deviations estimates, Poisson approximation. The main strategy of the proofs is to analyze the evolution of the most fit chromosomes, and more precisely the number of their descendants which are not altered by mutation and crossover. This evolution is described by an auxiliary Markov chain which is adequately coupled with the genetic algorithm. The study of this auxiliary chain rests on several ideas which were developed in the Freidlin-Wentzell theory and in the analysis of the simulated annealing.

The main results are stated in the section 2. The simple genetic algorithm is briefly explained before presenting the main results and it is formally described in section 3. The remaining sections are devoted to the proofs. In section 4, we build a coupling for the genetic algorithms starting with different populations. In section 5, we develop stochastic bounds to study the disordered regime. In section 6, we build an auxiliary chain and we study its dynamics. This auxiliary chain keeps track of the evolution of the quasispecies within the genetic algorithm. Section 7 contains the final proofs of the main theorems. Several classical results from probability theory are gathered in the appendix.

Main results

In this section, we provide a brief description of the simple genetic algorithm and we present our main results. The goal of the simple genetic algorithm is to find the global maxima of a fitness function f defined on { 0, 1 } with values in R. The genetic algorithm starts with a population of m points of { 0, 1 } , called the chromosomes, and it repeats the following fundamental cycle in order to build the generation n + 1 from the generation n: When building the generation n + 1 from the generation n, all the random choices are performed independently. Therefore, the above algorithmic description is equivalent to the parallel version described in section 3. Let us describe more precisely the selection, crossover and mutation steps.

Selection. We use ranking selection, meaning that the chromosomes are ordered according to their fitness, and they are selected with the help of a probability distribution which depends only on their rank. In case there is a tie between several chromosomes, we rank them randomly (with the uniform distribution over all possible choices). We consider mainly two popular selection mechanisms: linear ranking selection and tournament selection. The linear ranking selection depends on two parameters η -, η + satisfying 0 ≤ η -≤ η + , η -+ η + = 2 and we have

P selecting the (m -i + 1)-th best chromosome = 1 m η -+ (η + -η -) i -1 m -1 .
The tournament selection depends on an integer parameter t satisfying 2 ≤ t ≤ m and we have

P selecting the (m -i + 1)-th best chromosome = 1 m t i t -(i -1) t .
We introduce a parameter σ, called the strength of the ranking selection.

In the cases we consider, the parameter σ is equal to the limit σ = lim m→∞ m × P the selection operator chooses the best fit individual present in the population .

For the linear ranking selection, the strength of the ranking selection σ is equal to η + . For the tournament selection, the strength of the ranking selection σ is equal to t.

Crossover. We use the standard single point crossover and the crossover probability is denoted by p C : Mutation. We use independent parallel mutation at each bit and the mutation probability is denoted by p M :

P
P 0000000 -→ 0101000 = p 2 M (1 -p M ) 5 .
We state next the main results. in the form of six theorems. The first two theorems show that the dynamics of the genetic algorithm depend in a critical way on the value of

π = σ(1 -p C )(1 -p M ) .
If π < 1, the most fit chromosome is very likely to disappear before κ ln m generations. If π > 1, the most fit chromosome has a positive probability (independent of m) to invade a positive fraction of the population. Heuristically, the parameter π can be interpreted as the mean number of offsprings of the fittest chromosome from one generation to the next.

The disordered regime. We consider the fitness function f defined by

∀u ∈ { 0, 1 } f (u) = 2 if u = 1 • • • 1 1 otherwise
This corresponds to the sharp peak landscape. The chromosome 1 • • • 1 is called the Master sequence. We start the genetic algorithm from the population x 0 containing one Master sequence 1 • • • 1 and m -1 copies of the chromosome 0 • • • 0, i.e.,

x 0 =      1 • • • 1 0 • • • 0 . . . . . . 0 • • • 0     
Theorem 2.1 Let π < 1 be fixed. We suppose that the parameters are set so that = m and σ(1

-p C )(1 -p M ) = π.
There exist strictly positive constants κ, β, m 0 , which depend on π only, such that, for the genetic algorithm starting from x 0 ,

∀m ≥ m 0 P   the Master sequence 1 • • • 1 disappears from the population before κ ln m generations   ≥ 1 - 1 m β .
This theorem furnishes an example where the genetic algorithm performs poorly, even for large populations. To build this example, we take = m and we work with the sharp peak landscape. To prove theorem 2.1, we shall bound from above the number of Master sequences present in the population with a subcritical Galton-Watson process of parameter π. The quasispecies regime. We consider an arbitrary fitness function f . We start the genetic algorithm from an arbitrary population x 0 . Let f * 0 be the maximal fitness in x 0 , i.e.,

f * 0 = max 1≤i≤m f x 0 (i) .
Theorem 2.2 Let π > 1 be fixed. We suppose that the parameters are set so that σ(1

-p C )(1 -p M ) = π.
There exist strictly positive constants V * , p * , which depend on π only, such that, for the genetic algorithm starting from x 0 , for any , m ≥ 1,

P  
until the generation exp(V * m) the population always contains a chromosome with fitness larger than or equal to

f * 0   ≥ p * .
To prove theorem 2.2, we couple the genetic algorithm with an auxiliary chain on the integers, which bounds from below the evolution of the most fit chromosomes in the population. When π is strictly larger than 1, this chain can be seen as a stochastic perturbation of a deterministic map, which has one stable fixed point ρ * . Theorems 2.3, 2.4, 2.5 are obtained in the same way, they are consequences of more refined results on the dynamics of the auxiliary chain. The catastrophes. We consider next an arbitrary fitness function f and we start the genetic algorithm from an arbitrary position. For λ ∈ R and a population x, we define N (x, λ) as the number of chromosomes in x whose fitness is larger than or equal to λ:

N (x, λ) = card { i ∈ { 1, . . . , m } : f (x(i)) ≥ λ } .
For i ∈ { 1, . . . , m } and x ∈ { 0, 1 } , we define Λ(x, i) as the fitness of the i-th best chromosome in the population x:

Λ(x, i) = max λ ∈ R : N (x, λ) ≥ i .
We denote by X n the population of the genetic algorithm after n iterations.

Theorem 2.3 Let π > 1 be fixed. There exist strictly positive constants ρ * , c * , m 0 , which depend on π only, such that: for any fitness function f , any set of parameters , p C , p M satisfying σ(1 -p C )(1 -p M ) = π, for any m ≥ m 0 , for the genetic algorithm starting from an arbitrary population, we have

P ∀n ≤ exp(c * m) max 1≤i≤m f X n (i) ≥ max 0≤s≤n Λ X s , ρ * m ≥ 1 -exp(-c * m) .
It might be that ρ * is very small, especially if π is close to 1. We point out that the sequence max 0≤s≤n Λ X s , ρ * m is non-decreasing with respect to the time n. Thus, with very high probability, until time exp(c * m), the maximal fitness observed in the population stays above a non-decreasing sequence. We say that a catastrophe occurs at time n if max

1≤i≤m f X n (i) < max 0≤s≤n Λ X s , ρ * m .
This means that the maximal fitness in generation n has fallen below a fitness level which had been previously reached by a fraction ρ * of the chromosomes. In other words, a quasispecies has been destroyed. Hitting time of optimal chromosomes. We denote by H the Hamming distance between two chromosomes:

∀u, v ∈ { 0, 1 } H(u, v) = card j : 1 ≤ j ≤ , u(j) = v(j) .
For λ ∈ R, we define L(λ) as the set of the points in { 0, 1 } having a fitness larger than or equal to λ:

L(λ) = u ∈ { 0, 1 } : f (u) ≥ λ .
For λ < γ, we define ∆(λ, γ) as the maximal distance between a point of L(λ) and the set L(γ), i.e., ∆(λ, γ) = max

u∈L(λ) min v∈L(γ)
H(u, v) .

Let τ * be the hitting time of the set of the populations containing optimal chromosomes, i.e.,

τ * = min n ≥ 1 : ∃ i ∈ { 1, . . . , m } f (X n (i)) = max f (u) : u ∈ { 0, 1 } .
We give next a theoretical upper bound on the expected value of τ * .

Theorem 2.4 Let π > 1 be fixed. There exist constants c * , κ * , m 0 , which depend only on π, such that: for any set of parameters , p C , p M , m satisfying

σ(1 -p C )(1 -p M ) = π , p M ≥ c * , m ≥ m 0 , m ≥ c * ln ,
for the genetic algorithm starting from an arbitrary population, for any increasing sequence

λ 0 < • • • < λ r such that λ 0 = min f (u) : u ∈ { 0, 1 } , λ r = max f (u) : u ∈ { 0, 1 } ,
we have

E(τ * ) ≤ 2 + κ * (ln m)m 2 r-1 k=0 (p M ) -∆(λ k ,λ k+1 ) .
In the next result, we make a strong structural hypothesis on the fitness landscape and we obtain a bound on τ * which is polynomial in .

Theorem 2.5 Let γ, ∆ ≥ 1. Suppose that the fitness function is such that there exists an increasing sequence

λ 0 = min { 0,1 } f < λ 1 < • • • < λ r-1 < λ r = max { 0,1 } f with r ≤ γ and satisfying ∀k ∈ { 0, . . . , r -1 } ∆(λ k , λ k+1 ) ≤ ∆ .
Let π > 1 be fixed. There exist positive constants c * , m 0 , which depend only on π, such that: for any set of parameters , p C , p M , m satisfying

π = σ(1 -p C )(1 -p M ) , p M ≥ c * , m ≥ m 0 , m ≥ c * ∆ ln ,
for the genetic algorithm starting from an arbitrary population,

E(τ * ) ≤ 2 + (ln m) m 2 γ+∆ .
Asymptotic convergence. The bounds on the hitting time of optimal chromosomes yield simple estimates for the invariant probability measure of the genetic algorithm. Let us recall that the invariant probability measure µ is given by

∀x, y ∈ { 0, 1 } m µ(y) = lim n→∞ P X n = y X 0 = x .
The invariant probability measure µ depends on the fitness function f and the parameters , p C , p M , m, as well as the selection mechanism.

Theorem 2.6 Let π > 1 be fixed. There exist positive constants c * , m 0 , which depend only on π, such that: for any set of parameters , p C , p M , m satisfying

π = σ(1 -p C )(1 -p M ) , p M ≥ c * , m ≥ m 0 , m ≥ c * ln ,
for any fitness function f : { 0, 1 } → R, the invariant probability measure µ of the simple genetic algorithm satisfies

µ x : max 1≤i≤m f x(i) = max { 0,1 } f ≥ 1 -exp(-c * m) .
This result is certainly less relevant in practice than the previous ones, since it is extremely difficult to understand the speed of convergence of the genetic algorithm towards its invariant measure, yet it demonstrates that the genetic algorithm is successful in this asymptotic regime.

The model

Let ≥ 1 be an integer. We work on the space { 0, 1 } of binary strings of length . An element of { 0, 1 } is called a chromosome. Generic elements of { 0, 1 } will be denoted by the letters u, v, w. Let m ≥ 1 be an even integer.

A population is an m-tuple of elements of { 0, 1 } . Generic populations will be denoted by the letters x, y, z. Thus a population x is a vector

x =    x(1) . . . x(m)   
whose components are chromosomes. For i ∈ { 1, . . . , m }, we denote by

x(i, 1), . . . , x(i, )
the digits of the sequence x(i). This way a population x can be represented as an array

x =    x(1, 1) • • • x(1, ) . . . . . . x(m, 1) • • • x(m, )   
of size m × of zeroes and ones, the i-th row corresponding to the ith chromosome of the population. Let f : { 0, 1 } → R be an arbitrary objective function, traditionally called the fitness function.

Mathematically, a simple genetic algorithm is conveniently modelled by a Markov chain (X n ) n∈N with state space { 0, 1 } m , the space of the populations of m chromosomes. The transition mechanism of the simple genetic algorithm can be decomposed into three steps: selection, crossover and mutation. We explain separately each step.

Selection

We perform first the selection operation, which consists in selecting with replacement m chromosomes from the population. To this end, we build a selection distribution

sel : { 0, 1 } m × { 1, . . . , m } → [0, 1] .
The value sel(x, i) is the probability of selecting the i-th chromosome in the population x. We consider only ranking selection mechanisms, hence the value sel(x, i) depends only on the ranking of the chromosomes of the population x according to their fitness. We first define a ranking function, which gives the rank of a chromosome in a population. Let x ∈ { 0, 1 } m be a population. We choose a permutation σ of { 1, . . . , m } such that

f (x(σ(1))) ≤ • • • ≤ f (x(σ(m))) .
The choice of σ is not unique in case of ties, when several chromosomes have the same fitness. It turns out that the way the permutation σ is chosen affects considerably the behavior of the genetic algorithm. We choose the permutation σ randomly, according to the uniform distribution over the set of the permutations σ which satisfy the above condition. The choice of σ is done independently from the other steps of the algorithm, and it is performed again at each selection step. In particular, each time the process returns to the population x, a new permutation σ is drawn independently, and the ordering of the chromosomes will change accordingly. We define the rank of the i-th chromosome of the population x as

rank(x, i) = σ -1 (i) .
Thus if rank(x, i) = m, this implies that x(i) has the largest fitness in the population x, but the converse is false: when the fitness function f is not one to one, a chromosome with maximal fitness might get a ranking smaller than m. Once the ranking function rank(x, i) is built, we need a selection distribution F m on { 1, . . . , m } to complete the definition of the selection distribution sel(x, i). A selection distribution F m on { 1, . . . , m } is simply a probability distribution on { 1, . . . , m }. We define the selection distribution sel(x, i) by setting

∀i ∈ { 1, . . . , m } sel(x, i) = F m (rank(x, i)) .
Throughout the paper, we shall make the following hypothesis on F m . Hypothesis on F m . There exists a cumulative distribution function

F on [0, 1] such that ∀s ∈ [0, 1] lim m→∞ i≤sm F m (i) = F (s) .
We suppose that F is continuous on [0, 1], strictly increasing on [0, 1], convex on ]0, 1[ and left differentiable at 1. The value of its left derivative at 1 is called the selection drift and is denoted by σ (necessarily σ ≥ 1). We suppose that the discrete derivative of F m at 1 converges to σ in the following sense:

∀ε > 0 ∃ δ > 0 ∃m 0 ≥ 1 ∀m ≥ m 0 ∀i ∈ 1, . . . , δm F m (m -i + 1) + • • • + F m (m) -σ i m ≤ εσ i m .
We consider two popular choices for the selection distribution F m . Linear ranking selection. This selection scheme depends on two parameters η -, η + which satisfy

0 ≤ η -≤ η + , η -+ η + = 2 .
We define the linear ranking selection distribution by

∀i ∈ { 1, . . . , m } F m (i) = 1 m η -+ (η + -η -) i -1 m -1 .
The linear ranking selection distribution satisfies the hypothesis with

F (s) = η -s + 1 2 (η + -η -)s 2 , σ = η + .
Tournament selection. This selection scheme depends on an integer parameter t satisfying 2 ≤ t ≤ m. We define the tournament selection distribution by

∀i ∈ { 1, . . . , m } F m (i) = 1 m t i t -(i -1) t .
The tournament selection distribution satisfies the hypothesis with

F (s) = s t , σ = t .
Finally, we draw independently m chromosomes from the population x according to the selection distribution sel(x, •) to obtain the population after selection. The stochastic matrix P S associated to the selection operator is defined as follows. The probability to select the population y starting from the population x is

P S (x, y) = m i=1 j:x(j)=y(i)
sel(x, j) .

Crossover

After having selected m chromosomes, we perform the crossover operation.

The crossover depends on a parameter p C ∈ [0, 1] and it acts on pairs of chromosomes. Let us explain how the crossover operator acts on two chromosomes u, v. With probability 1 -p C , there is no crossover and the chromosomes u, v are not modified. With probability p C , there is a crossover between the chromosomes u, v. We choose uniformly at random a cutting position k in { 1, . . . , -1 }. A new pair (u , v ) of chromosomes is formed, where u (respectively v ) consists of the first k digits of u (respectively v) and the last -k digits of v (respectively u). Mathematically, this mechanism is encoded in a crossover kernel

C : { 0, 1 } 2 × { 0, 1 } 2 → [0, 1] .
The value C (u, v), (u , v ) is the probability that, by crossover, the pair of chromosomes (u, v) becomes the pair (u , v ). More precisely, we define, for u, v two chromosomes and

k ∈ { 1, . . . , -1 }, switch k, u, v = u(1) • • • u(k)v(k + 1) • • • v( ) .
The crossover kernel C is then equal to

C u v , u v = (1 -p C )1 (u,v)=(u ,v ) + p C -1 card k ∈ { 1, . . . , -1 } : switch k, u, v = u switch k, v, u = v .
We apply simultaneously the crossover operator on the m/2 consecutive pairs of chromosomes of a population of size m. The stochastic matrix P C associated to the crossover operator is defined as follows. The probability to obtain the population z after performing the crossover starting from the population y is

P C (y, z) = m/2 i=1 C y(2i -1) y(2i) , z(2i -1) z(2i) .

Mutation

After having performed the crossover, we perform the mutation. The mutation depends on one parameter, the mutation probability p M ∈ [0, 1], and it acts on a single chromosome. Let u be a chromosome. For each k ∈ { 1, . . . , }, the digit u(k) is kept unchanged with probability 1 -p M and it mutates to 1 -u(k) with probability p M . These changes are done simultaneously and independently. Mathematically, this mechanism is encoded in a mutation kernel

M : { 0, 1 } 2 → [0, 1] .
The value M (u, v) is the probability that, by mutation, the chromosome u becomes the chromosome v, and it is given by

M (u, v) = p H(u,v) M (1 -p M ) -H(u,v) ,
where H(u, v) is the Hamming distance between u and v, defined by

H(u, v) = card j : 1 ≤ j ≤ , u(j) = v(j) .
The stochastic matrix P M associated to the mutation operator is defined as follows. The probability to obtain the population x after performing the mutation starting from the population z is

P M (z, x ) = m i=1
M z(i), x (i) .

Transition matrix of the SGA

The fundamental cycle of the simple genetic algorithm consists in applying successively the selection, the crossover and the mutation operators on the population. Mathematically, the simple genetic algorithm is conveniently modelled by a Markov chain (X n ) n∈N with state space { 0, 1 } m , the space of the populations of m chromosomes. The transition matrix P SGA of the simple genetic algorithm is defined by

∀x, x ∈ { 0, 1 } m P SGA (x, x ) = P X n+1 = x | X n = x .
The matrix P SGA is simply the product of the three matrices P M , P C , P S , i.e., P SGA = P M P C P S , or equivalently,

∀x, x ∈ { 0, 1 } m P SGA (x, x ) = y,z P M (x, y)P C (y, z)P S (z, x ) .

Coupling for the genetic algorithm

Throughout the proofs, we rely on various coupling arguments. We will couple here the simple genetic algorithm starting from any possible initial population. We first define separately the maps for coupling the selection, crossover and mutation.

Selection. We define a selection map

S : { 0, 1 } m × [0, 1] → { 1, . . . ,
F m (1) + • • • + F m (i -1) ≤ s < F m (1) + • • • + F m (i) .
Let next x ∈ { 0, 1 } m and let s ∈ [0, 1[. We define S(x, s) = j where j is the unique index in { 1, . . . , m } such that rank(x, j) = I(s). The map S is built in such a way that, if U is a random variable with uniform law on the interval [0, 1], then, for any population x, the law of S(x, U ) is given by the selection distribution:

∀i ∈ { 1, . . . , m } P S(x, U ) = i = sel(x, i) .
Crossover. We define a map

C : { 0, 1 } 2 × { 0, 1 } × { 1, . . . , -1 } → { 0, 1 } in order to couple the crossover mechanism starting with different pairs of chromosomes. Let u, v ∈ { 0, 1 } and let ε ∈ { 0, 1 }, k ∈ { 1, . . . , -1 }. We define C u, v, ε, k = switch k, u, v if ε = 1 u if ε = 0
The map C is built in such a way that, if V, W are two independent random variables with respective laws the Bernoulli law with parameter p C and the uniform law on { 1, . . . , -1 }, then, for any chromosomes u, v, the law of the pair of chromosomes C(u, v, V, W ), C(v, u, V, W ) is given by the crossover kernel C:

∀u , v ∈ { 0, 1 } P C(u, v, V, W ) = u C(v, u, V, W ) = v = C u v , u v .
Mutation. We define a map

M : { 0, 1 } × { 0, 1 } → { 0, 1 }
in order to couple the mutation mechanism starting with different chromosomes. Let ε 1 , . . . , ε ∈ { 0, 1 } and let u 1 , . . . , u ∈ { 0, 1 }. The map M is defined by setting

M(ε 1 • • • ε , u 1 , • • • , u ) = η 1 • • • η , where ∀i ∈ { 1, . . . , } η i = ε i if u i = 0 1 -ε i if u i = 1
The map M is built in such a way that, if U 1 , . . . , U are independent random variables with law the Bernoulli law with parameter p M , then, for any chromosome u, the law of the chromosome M(u, U 1 , . . . , U ) is given by the line of the mutation matrix corresponding to u:

∀v ∈ { 0, 1 } P M(u, U 1 , . . . , U ) = v = M (u, v) .
Coupling for the genetic algorithm. We will now combine the maps S, C, M with random inputs in order to couple the genetic algorithm with various initial conditions. We will build all the processes on a single large probability space. We consider a probability space (Ω, F, P ) containing the following collection of independent random variables:

• Uniform on the interval [0, 1]: S i n , n ≥ 1 , 1 ≤ i ≤ m ; • Bernoulli with parameter p M : U i,j n , n ≥ 1 , 1 ≤ i ≤ m , 1 ≤ j ≤ ; • Bernoulli with parameter p C : V i n , n ≥ 1 , 1 ≤ i ≤ m/2 ; • Uniform on { 1, . . . , -1 }: W i n , n ≥ 1 , 1 ≤ i ≤ m/2 .
The variables having subscript n constitute the random input which is used to perform the n-th step of the Markov chains. For each n ≥ 1, we build a map

Φ n : { 0, 1 } m → { 0, 1 } m
in order to realize the coupling between the genetic algorithm with various initial conditions. The coupling map Φ n is defined by

∀x ∈ { 0, 1 } m Φ n (x) =             M C S(x, S 1 n ), S(x, S 2 n ), V 1 n , W 1 n , U 1,1 n , . . . , U 1, n M C S(x, S 2 n ), S(x, S 1 n ), V 1 n , W 1 n , U 2,1 n , . . . , U 2, n M C S(x, S 3 n ), S(x, S 4 n ), V 2 n , W 2 n , U 3,1 n , . . . , U 3, n M C S(x, S 4 n ), S(x, S 3 n ), V 2 n , W 2 n , U 4,1 n , . . . , U 4, n . . . M C S(x, S m-1 n ), S(x, S m n ), V m/2 n , W m/2 n , U m-1,1 n , . . . , U m-1, n M C S(x, S m n ), S(x, S m-1 n ), V m/2 n , W m/2 n , U m,1 n , . . . , U m, n            
The coupling is then built in a standard way with the help of the sequence (Φ n ) n≥1 . Let x ∈ { 0, 1 } m be the starting point of the process. We build the process (X n ) n≥0 by setting X 0 = x and

∀n ≥ 1 X n = Φ n X n-1 .
A routine check shows that the process (X n ) n≥0 is a Markov chain starting from x with the adequate transition matrix. This way we have coupled the genetic algorithm with all possible initial conditions.

The disordered regime

We consider the fitness function f defined by

∀u ∈ { 0, 1 } f (u) = 2 if u = 1 • • • 1 1 otherwise
This corresponds to the sharp peak landscape. The chromosome 1 • • • 1 is called the Master sequence. We start the genetic algorithm with the population

x 0 =      1 • • • 1 0 • • • 0 . . . . . . 0 • • • 0     
and we wish to estimate the probability of survival of the Master sequence. We denote by (X n ) n∈N the genetic algorithm starting from x 0 . We shall develop bounds in the sense of stochastic domination. Let π < 1 be fixed.

Throughout the section, we suppose that , p C , p M satisfy

σ(1 -p C )(1 -p M ) = π .

Genealogy

To build a chromosome in the generation n, we select two parents in generation n -1, and we apply the crossover and the mutation operators. Thus each chromosome has two parents in the previous generation. With the coupling construction, the parents of the chromosomes

X n (2i -1), X n (2i) are the chromosomes S(X n-1 , S 2i-1 n ), S(X n-1 , S 2i n ).
The genealogy of a chromosome consists of all its ancestors until time 0. We define auxiliary random variables in order to control the progeny of the initial Master sequence. For n ≥ 1, i ∈ { 1, . . . , m }, we set M n (i) = 1 if the Master sequence appears in the genealogy of X n (i) and 0 otherwise. We denote by M n the vector (M n (1), . . . , M n (m)) and we define also

T n = m i=1 M n (i) .
The variable T n is the total number of descendants of the Master sequence at time n. Let also N * n be the number of Master sequences present in the population at time n:

∀n ≥ 1 N * n = card i ∈ { 1, . . . , m } : X n (i) = 1 • • • 1 .
We shall next compute stochastic bounds on (T n ) n∈N and (N * n ) n∈N . The process (T n ) n∈N will be controlled by a supercritical branching process, while the process (N * n ) n∈N will be controlled by a subcritical branching process.

Bound on T n

By construction, the chromosomes X n (2i -1) and X n (2i) have the same parents, thus M n (2i -1) = M n (2i) and

∀n ≥ 1 T n = m/2 i=1 2M n (2i) .
Conditionally on X n-1 , M n-1 , the random variables M n (2i), 1 ≤ i ≤ m/2, are independent and identically distributed. Let us estimate their parameter:

P M n (2) = 0 X n-1 , M n-1 = P  
the selection operator selects two parents in X n-1 which do not belong to the progeny of the initial Master sequence

X n-1 , M n-1   .
The number of chromosomes in the progeny of the initial Master sequence at time n-1 is T n-1 . The lowest value for the above conditional probability corresponds to the situation where all these chromosomes are ranked best during the selection process, therefore

P M n (2) = 0 X n-1 , M n-1 ≥ F m (1) + • • • + F m (m -T n-1 ) 2 .
To go further, we need a bound on T n-1 . Thus we define

τ 1 = inf n ≥ 1 : T n > m 1/4
and we will study the random variable T n 1 { τ1≥n } . In order to incorporate the event { τ 1 ≥ n } in the previous inequality, we condition with respect to the whole history of the process as follows:

P M n (2) = 1, τ 1 ≥ n X n-1 , M n-1 , . . . , X 0 , M 0 = 1 { T0≤m 1/4 ,...,Tn-1≤m 1/4 } P M n (2) = 1 X n-1 , M n-1 , . . . , X 0 , M 0 = 1 { τ1≥n } P M n (2) = 1 X n-1 , M n-1 ≤ 1 { τ1≥n-1 } 1 -F m (1) + • • • + F m (m -T n-1 ) 2 .
Using the hypothesis on F m , we obtain that, for m large enough, there exists δ > 0 such that ∀i ∈ 1, . . . , δm F m (m

-i + 1) + • • • + F m (m) ≤ 2σ i m .
For m large enough, if τ 1 ≥ n, then T n-1 ≤ m 1/4 ≤ δm , whence

P M n (2) = 1, τ 1 ≥ n X n-1 , M n-1 , . . . , X 0 , M 0 ≤ 1 { τ1≥n-1 } 1 -1 -2σ T n-1 m 2 ≤ 1 { τ1≥n-1 } 4σ T n-1 m .
Proposition 5.1 Let (Z n ) n∈N be a Galton-Watson process starting from Z 0 = 1 with reproduction law ν = 2P(4σ), i.e., the law ν is twice the Poisson law of parameter 4σ. For m large enough, we have

∀n ≥ 0 T n 1 { τ1≥n } Z n .
Proof. We recall that means stochastic domination (see appendix C).

We will prove the inequality by induction on n. For n = 0, the inequality holds trivially, since

T 0 1 { τ1≥0 } = Z 0 = 1 .
Let n ≥ 1 and suppose that the inequality has been proved at rank n -1. The previous computation shows that, conditionally on X 0 ,M 0 , . . . , X n-1 ,M n-1 , the law of T n 1 { τ1≥n } is stochastically dominated by the law

2B m 2 , 4σ m T n-1 1 { τ1≥n-1 } .
There exists t 0 > 0 such that, for 0 < t < t 0 , we have ln(1 -t) ≥ -2t.

Therefore, for m large enough so that 4σm -3/4 < t 0 , we have

1 - 4σ m T n-1 1 { τ1≥n-1 } m/2 ≥ exp -4σT n-1 1 { τ1≥n-1 } .
By lemma C.1, we conclude from this inequality that

2B m 2 , 4σ m T n-1 1 { τ1≥n-1 } 2P 4σT n-1 1 { τ1≥n-1 } .
Therefore, for any non-decreasing function φ, we have

E φ T n 1 { τ1≥n } X n-1 , M n-1 , . . . , X 0 , M 0 ≤ E φ Tn-11 { τ 1 ≥n-1 } k=1 Y k T n-1 1 { τ1≥n-1 }
where the random variables (Y k ) k≥1 are independent identically distributed with law ν = 2P 4σ , and they are also independent of the processes (X n ) n∈N , (M n ) n∈N . The conditional expectation is a non-decreasing function of T n-1 1 { τ1≥n-1 } . Taking the expectation with respect to X n-1 , M n-1 , . . . , X 0 , M 0 and using the induction hypothesis, we get

E φ T n 1 { τ1≥n } ≤ E φ Tn-11 { τ 1 ≥n-1 } k=1 Y k ≤ E φ Zn-1 k=1 Y k = E φ Z n .
This completes the induction step.

In order to exploit proposition 5.1, we shall need a bound on τ 1 , which we compute next.

Proposition 5.2 There exist κ > 0,

c 1 > 0, m 1 ≥ 1, such that ∀m ≥ m 1 P τ 1 < κ ln m ≤ 1 m c1 .
Proof. Let (Z n ) n∈N be a Galton-Watson process as in proposition 5.1.

We have, for k ≥ 0,

P (τ 1 = k) = P τ 1 ≥ k, T k > m 1/4 = P T k 1 { τ1≥k } > m 1/4 ≤ P Z k > m 1/4 ≤ m -1/4 E Z k ≤ m -1/4 (8σ) k .
We sum this inequality: for n ≥ 1,

P (τ 1 < n) ≤ m -1/4 n-1 k=0 (8σ) k = m -1/4 (8σ) n -1 8σ -1 .
We choose n = κ ln m, where κ is positive and sufficiently small, and we obtain the desired conclusion.

Bound on N * n

By definition, we have

∀n ≥ 1 N * n = m/2 i=1 1 { Xn(2i-1)=1•••1 } + 1 { Xn(2i)=1•••1 } . Let us define, for 1 ≤ i ≤ m/2, B n (i) = 1 { Xn(2i-1)=1•••1 } + 1 { Xn(2i)=1•••1 } .
Conditionally on X n-1 , the variables B n (i), 1 ≤ i ≤ m/2, are independent and identically distributed. A Master sequence appearing in generation n is either in the progeny of the initial Master sequence, or it has been created through numerous mutations and crossover from 0 • • • 0. The probability of the first scenario will be controlled with the help of T n-1 (the size of the progeny of the initial Master sequence in generation n -1). The second scenario is very unlikely unless n is large. To control its probability, we introduce the time τ 2 , when a mutant, not belonging to the progeny of the initial Master sequence, is at distance less than -√ from the Master sequence. Let us recall that H(u, v) is the Hamming distance between the chromosomes u, v. We set

τ 2 = inf n ≥ 1 : ∃ i ∈ { 1, . . . , m } H(X n (i), 1 • • • 1) ≤ - √ , M n (i) = 0 .
We recall that

τ 1 = inf n ≥ 1 : T n > m 1/4 .
We set also τ 0 = inf n ≥ 1 : N * n = 0 . We shall compute a bound on N * n until time τ = min(τ 0 , τ 1 , τ 2 ).

Proposition 5.3 Let π < 1. We suppose in addition that = m. For m large enough, the process

(N * n 1 { τ ≥n } ) n∈N
is stochastically dominated by a subcritical Galton-Watson process.

Proof. We shall estimate the law of B n (1). The proof is tedious because there are several cases to consider. The chromosomes X n (1), X n (2) are obtained after applying the crossover and the mutation operators on the chromosomes of the population X n-1 having indices

I 1 = S(X n-1 , S 1 n ) , I 2 = S(X n-1 , S 2 n ) .
We denote by Y 1 , Y 2 the chromosomes obtained after crossover from the chromosomes X n-1 (I 1 ), X n-1 (I 2 ), i.e.,

Y 1 = C X n-1 (I 1 ), X n-1 (I 2 ), V 1 n , W 1 n , Y 2 = C X n-1 (I 2 ), X n-1 (I 1 ), V 1 n , W 1 n .
Our goal is to obtain a stochastic bound on N * n 1 { τ ≥n } , so we need only to consider the case where τ ≥ n. Thus, in the following computations, we suppose that τ 2 ≥ n. Let λ > 0 be such that π/σ ≥ exp(-λ). We have then (1

-p M ) = π σ(1 -p C ) ≥ π σ ≥ exp(-λ) .
Notice that λ depends only on π/σ, and not on or p M . By lemma C.1, the binomial law B( , p M ) is then stochastically dominated by the Poisson law P(λ). We will use repeatedly the bound given in lemma C.2:

∀t ≥ λ P U 1,1 n + • • • + U 1, n ≥ t ≤ λe t t .
When using this bound, the value of t will be a function of . We will always take large enough, so that the value of t will be larger than λ. We examine several cases, depending on whether the initial Master sequence belongs to the genealogy of the chromosomes X n-1 (I 1 ), X n-1 (I 2 ):

• M n-1 (I 1 ) = M n-1 (I 2 ) = 0. Since τ 2 ≥ n, then the chromosomes X n-1 (I 1
) and X n-1 (I 2 ) have strictly less than √ ones, therefore the chromosomes Y 1 , Y 2 obtained after crossover have strictly less than 2 √ ones. Thus, for large enough and * = 1 or * = 2,

P M Y * , U 1,1 n , . . . , U 1, n = 1 • • • 1 ≤ P U * ,1 n + • • • + U * , n > -2 √ ≤ λe -2 √ -2 √
.

Therefore

P B n (1) > 0, τ 2 ≥ n M n-1 (I 1 ) = M n-1 (I 2 ) = 0 X n-1 M n-1 ≤ 2 λe -2 √ -2 √ . • M n-1 (I 1 ) = 1, M n-1 (I 2 ) = 0.
We estimate first the probability that B n (1) = 2. Since τ 2 ≥ n, then the chromosome X n-1 (I 2 ) has strictly less than √ ones, therefore at least one of the chromosomes Y 1 , Y 2 obtained after crossover has strictly less than ( + √ )/2 ones. Suppose for instance that it is the case for Y 1 . It is then very unlikely that a Master sequence is created from Y 1 with the help of the mutations. Indeed, for large enough, we have

P M Y 1 , U 1,1 n , . . . , U 1, n = 1 • • • 1, H(Y 1 , 1 • • • 1) > ( - √ )/2 ≤ P U 1,1 n + • • • + U 1, n > ( - √ )/2 ≤ 2λe - √ ( - √ )/2 . Therefore P B n (1) = 2, τ 2 ≥ n M n-1 (I 1 ) = 1, M n-1 (I 2 ) = 0 X n-1 M n-1 ≤ 2 2λe - √ ( - √ )/2
.

We estimate next the probability that B n (1) = 1. Suppose that a crossover occurs between X n-1 (I 1 ), X n-1 (I 2 ), i.e., that V 1 n = 1. Since τ 2 ≥ n, then the chromosome X n-1 (I 2 ) has strictly less than √ ones. After crossover, the probability that one of the two resulting chromosomes Y 1 , Y 2 has at least -√ ones is less than 4/ √ . Indeed, this can happen only if, either on the left of the cutting site, or on its right, there are at most √ zeroes. The most favorable situation is when all the ones in Y 2 are at the end or at the beginning of Y 2 , in which case we have 2 √ cutting sites which lead to the desired result. Now, if a chromosome u is such that

H(u, 1 • • • 1) > √ , then P M u, U 1,1 n , . . . , U 1, n = 1 • • • 1 ≤ P U 1,1 n + • • • + U 1, n > √ ≤ λe √ √ .
From the previous discussion, we conclude that

P B n (1) = 1, V 1 n = 1, τ 2 ≥ n M n-1 (I 1 ) = 1, M n-1 (I 2 ) = 0 X n-1 M n-1 ≤ 4 √ + 2 λe √ √ F m (m) -F m (m -T n-1 ) .
We consider now the case where no crossover occurs between the chromosomes X n-1 (I 1 ), X n-1 (I 2 ), i.e., we have

V 1 n = 0 , Y 1 = X n-1 (I 1 ) , Y 2 = X n-1 (I 2 ) .
We write

P B n (1) = 1, M n-1 (I 1 ) = 1, M n-1 (I 2 ) = 0, V 1 n = 0 , τ 2 ≥ n X n-1 , M n-1 ≤ P M X n-1 (I 1 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 M n-1 (I 1 ) = 1, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 + P M X n-1 (I 2 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 M n-1 (I 2 ) = 0, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 .
We estimate the last term. Since τ 2 ≥ n, then the chromosome Y 2 = X n-1 (I 2 ) has strictly less than √ ones. As before, for large enough, we have

P M X n-1 (I 2 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 M n-1 (I 2 ) = 0, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 ≤ P U 2,1 n + • • • + U 2, n > - √ ≤ λe - √ - √
.

Thus it is very unlikely that a Master sequence is created from Y 2 = X n-1 (I 2 ) with the help of the mutations. The most likely scenario is that the Master sequence comes from Y 1 = X n-1 (I 1 ). We estimate the probability of this scenario, and to do so, we distinguish further two cases, according to whether X n (I 1 ) is a Master sequence or not:

P M X n-1 (I 1 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 M n-1 (I 1 ) = 1, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 = P M X n-1 (I 1 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 X n-1 (I 1 ) = 1 • • • 1, M n-1 (I 1 ) = 1, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 + P M X n-1 (I 1 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 X n-1 (I 1 ) = 1 • • • 1, M n-1 (I 1 ) = 1, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 .
To estimate these probabilities, we make an intermediate conditioning and we obtain

P M X n-1 (I 1 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 X n-1 (I 1 ) = 1 • • • 1, M n-1 (I 1 ) = 1, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 ≤ P M 1 • • • 1, U 1,1 n , . . . , U 1, n = 1 • • • 1 × P X n-1 (I 1 ) = 1 • • • 1 M n-1 (I 1 ) = 1, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 ≤ (1 -p M ) (1 -p C ) F m (m) -F m (m -N * n-1 ) .
Indeed, the number of Master sequences present in X n-1 is N * n-1 and the probability of selecting a Master sequence in

X n-1 is at most (F m (m) - F m (m -N * n-1 )
). In a similar way,

P M X n-1 (I 1 ), U 1,1 n , . . . , U 1, n = 1 • • • 1 X n-1 (I 1 ) = 1 • • • 1, M n-1 (I 1 ) = 1, V 1 n = 0, τ 2 ≥ n X n-1 M n-1 ≤ u =1•••1 P M u, U 1,1 n , . . . , U 1, n = 1 • • • 1 P   X n-1 (I 1 ) = u M n-1 (I 1 ) = 1 τ 2 ≥ n X n-1 M n-1   ≤ p M P X n-1 (I 1 ) = 1 • • • 1 M n-1 (I 1 ) = 1, τ 2 ≥ n X n-1 M n-1 ≤ p M F m (m) -F m (m -T n-1 )
.

Putting together the previous inequalities, we obtain

P B n (1) = 1, M n-1 (I 1 ) = 1, M n-1 (I 2 ) = 0, τ 2 ≥ n X n-1 , M n-1 ≤ 4 √ + 2 λe √ √ F m (m) -F m (m -T n-1 ) + λe - √ - √ + (1-p M ) (1-p C ) F m (m)-F m (m-N * n-1 ) + p M F m (m)-F m (m-T n-1 ) . • M n-1 (I 1 ) = M n-1 (I 2 ) = 1.
In this case, we have

P M n-1 (I 1 ) = 1, M n-1 (I 2 ) = 1 , τ 2 ≥ n X n-1 , M n-1 ≤ F m (m) -F m (m -T n-1 )
.

In conclusion, we obtain the following inequalities:

P B n (1) = 2 , τ 2 ≥ n X n-1 , M n-1 ≤ 2 λe -2 √ -2 √ + 4 2λe - √ ( - √ )/2 + F m (m) -F m (m -T n-1 ) , P B n (1) = 1 , τ 2 ≥ n X n-1 , M n-1 ≤ 2 λe -2 √ -2 √ + 8 √ + 4 λe √ √ F m (m) -F m (m -T n-1 ) + 2 λe - √ - √ + 2(1 -p M ) (1 -p C ) F m (m) -F m (m -N * n-1 ) + 2p M F m (m) -F m (m -T n-1 ) + F m (m) -F m (m -T n-1 )
.

In order to incorporate the event { τ ≥ n } in these inequalities, we condition with respect to the whole history of the process as follows: for * = or * = 2,

P B n (1) = * , τ ≥ n X n-1 , M n-1 , . . . , X 0 , M 0 ≤ 1 { τ ≥n } P B n (1) = * X n-1 , M n-1 .
Let ε > 0 be such that (1 + 5ε)π < 1. We use next the hypothesis on the selection function: there exists c > 0 such that, for m large enough,

1 { τ ≥n } F m (m) -F m (m -T n-1 ) ≤ 1 { τ ≥n } c m T n-1 ≤ c m 3/4 .
Moreover, for m large enough,

1 { τ ≥n } F m (m) -F m (m -N * n-1 ) ≤ 1 { τ ≥n } σ(1 + ε) m N * n-1 .
Thus there exists a constant c > 0 such that, for m, large enough,

1 { τ ≥n } P B n (1) = 2 X n-1 , M n-1 ≤ 1 2 + c 2 m 3/2 , 1 { τ ≥n } P B n (1) = 1 X n-1 , M n-1 ≤ 1 2 + 8 √ c m 3/4 + 2 m σ(1 + ε)1 { τ ≥n } N * n-1 (1 -p M ) (1 -p C ) + 2p M c m 3/4 + c 2 m 3/2 .
We rewrite the previous inequalities in the case = m. First, we have, for a positive constant c,

P B n (1) = 2 , τ ≥ n X n-1 , M n-1 , . . . , X 0 , M 0 ≤ c m 3/2 . Moreover σ(1 -p M ) m ≥ π, whence p M ≤ - 1 m ln(π/σ) .
For m large enough, we have therefore

1 m 2 + 8 √ m c m 3/4 + 2p M c m 3/4 + c 2 m 3/2 ≤ 2 m πε ,
and it follows that

P B n (1) = 1 , τ ≥ n X n-1 , M n-1 , . . . , X 0 , M 0 ≤ 2 m π(1 + 2ε)1 { τ ≥n } N * n-1 .
Coming back to the initial equality for N * n , we conclude that, for m large enough, the law of N * n 1 { τ ≥n } is stochastically dominated by the sum of two independent binomial random variables as follows:

N * n 1 { τ ≥n } B m 2 , 2 m π(1 + 2ε)1 { τ ≥n } N * n-1 + 2B m 2 , c m 3/2 .
For m large, these two binomial laws are in turn stochastically dominated by two Poisson laws. More precisely, for m large enough,

1 - 2 m π(1 + 2ε)1 { τ ≥n } N * n-1 m/2 ≥ exp -π(1 + 3ε)1 { τ ≥n } N * n-1 , 1 -cm -3/2 m/2 ≥ exp(-ε) .
Lemma C.1 yields then that

N * n 1 { τ ≥n } P π(1 + 3ε)N * n-1 1 { τ ≥n } + 2P(ε)
. The point is that we have got rid of the variable m in the upper bound, so we are now in position to compare N * n 1 { τ ≥n } with a Galton-Watson process. Let (Y n ) n≥1 be a sequence of i.i.d. random variables with law P(π(1 + 3ε)), let (Y n ) n≥1 be a sequence of i.i.d. random variables with law P(ε), both sequences being independent. The previous stochastic inequality can be rewritten as

N * n 1 { τ ≥n } N * n-1 1 { τ ≥n } k≥1 Y k + 2Y 1 .
This implies further that

N * n 1 { τ ≥n } N * n-1 1 { τ ≥n-1 } k≥1 Y k + 2Y k . ( )
Let ν * be the law of Y 1 + 2Y 1 and let (Z * n ) n≥0 be a Galton-Watson process starting from Z 0 = 1 with reproduction law ν * . We prove finally that, for m large enough, ∀n ≥ 0

N * n 1 { τ ≥n } Z * n .
We suppose that m is large enough so that the stochastic inequality ( ) holds and we proceed by induction on n. For n = 0, we have

N * 0 1 { τ ≥0 } = 1 ≤ Z * 0 = 1 .
Let n ≥ 1 and suppose that the inequality holds at rank n-1. Inequality ( ) yields

N * n 1 { τ ≥n } N * n-1 1 { τ ≥n-1 } k≥1 Y k + 2Y k Z * n-1 k≥1 Y k + 2Y k = Z * n .
Thus the inequality holds at rank n and the induction is completed. Moreover we have

E(ν * ) = E Y 1 + 2Y 1 = π(1 + 5ε) < 1 .
Thus the Galton-Watson process (Z * n ) n≥0 is subcritical and this completes the proof of proposition 5.3.

We close this section with a bound on τ 2 , which will be useful when applying proposition 5.3.

Lemma 5.4 For m ≥ 2 and for large enough, we have

P τ 2 ≤ 1 5 ln ≤ 1 -exp -m exp -1/4 .
Proof. If τ 2 < n, then, before time n, a chromosome has been created with at least √ ones, and whose genealogy does not contain the initial Master sequence. We shall compute an upper bound on the number of ones appearing in the genealogy of such a chromosome at generation n.

Let us define

∀n ≥ 1 D n = max -H(X n (i), 1 • • • 1) : 1 ≤ i ≤ m, M n (i) = 0 .
The quantity D n is the maximum number of ones in a chromosome of the generation n, which does not belong to the progeny of the initial Master sequence. These ones must have been created by mutation. Let us consider a chromosome of the generation n+1, which does not belong to the progeny of the initial Master sequence. The number of ones in each of its two parents was at most D n . After crossover between these two parents, the number of ones was at most 2D n . After mutation, the number of ones was at most

D n+1 ≤ 2D n + max j=1 U i,j n : 1 ≤ i ≤ m .
We first control the last term. Let n ≥ 1 and let us define the event E(n) by

E(n) = ∀i ∈ { 1, . . . , m } ∀k ∈ { 1, . . . , n } j=1 U i,j k ≤ 1/4 .
We have

P E(n) = 1 -P j=1 U 1,j 1 > 1/4 mn .
The law of the sum j=1 U 1,j 1 is the binomial law B( , p M ). Let λ > 0 be such that π/σ ≥ exp(-λ). We have then

(1 -p M ) = π σ(1 -p C ) ≥ π σ ≥ exp(-λ) .
By lemma C.1, the binomial law B( , p M ) is stochastically dominated by the Poisson law P(λ). Using the bound given in lemma C.2, we obtain that, for 1/4 > λ,

P E(n) ≥ 1 - λe 1/4 1/4 mn
, whence, for large enough,

P E(n) ≥ exp -mn exp -1/4 .
Suppose that the event E(n) occurs. We have then

∀k ∈ { 0, . . . , n -1 } D k+1 ≤ 2D k + 1/4 .
Dividing by 2 k+1 and summing from k = 0 to n -1, we get

D n ≤ 2 n n-1 k=0 1/4 2 k+1 ≤ 2 n 1/4 .
Therefore, if 2 n < 1/4 and if the event E(n) occurs, then τ 2 > n. Taking n = (ln )/5, we obtain the estimate stated in the lemma.

Proof of theorem 2.1

We complete here the proof of theorem 2.1. The hypothesis of theorem 2.1 allows to apply proposition 5.3. Thus there exists a subcritical Galton-Watson process (Z * n ) n≥0 , with reproduction law ν * , which dominates stochastically the process (N * n 1 { τ ≥n } ) n≥0 . A standard result on Galton-Watson processes (see for instance [START_REF] Athreya | Branching processes[END_REF]) ensures the existence of a positive constant c * , which depends only on the law ν * , such that ∀n ≥ 1 P Z * n > 0 ≤ exp(-cn) . Let κ, c 1 be as in proposition 5.2. We suppose that κ < 1/5, so that we can use the estimate of lemma 5.4. We have then

P τ 0 > κ ln m ≤ P τ 0 > κ ln m, τ < κ ln m + P N * κ ln m > 0, τ ≥ κ ln m ≤ P τ 1 < κ ln m + P τ 2 < κ ln m + P Z * κ ln m > 0 ≤ 1 m c1 + 1 -exp(-m exp -m 1/4 + exp(-c * κ ln m ) .
This inequality yields the estimate stated in theorem 2.1.

The quasispecies regime

For λ ∈ R and a population x, we define N (x, λ) as the number of chromosomes in x whose fitness is larger than or equal to λ:

N (x, λ) = card { i ∈ { 1, . . . , m } : f (x(i)) ≥ λ } .
We shall couple the processes (N (X n , λ)) n∈N , λ ∈ R, with a family of Markov chains N n (t, i) n≥t , t ∈ N. We study then dynamics of these Markov chains.

The auxiliary chain

Here, we couple the genetic algorithm with an auxiliary chain. For n ≥ 1, let Γ n : { 1, . . . , m } 2 → { 0, 1 } be the map defined by

∀i, j ∈ { 1, . . . , m } Γ n (i, j) = 1 if I(S j n ) ≥ m -i + 1 0 otherwise
Recall that the map I is defined together with the selection map S. In fact, the map Γ n (i, j) is equal to one if the j-th chromosome chosen during the selection at time n is among the best i chromosomes of generation n. For each n ≥ 1, we define also a map Ψ n : { 0, . . . , m } → { 0, . . . , m } by setting

∀i ∈ { 0, . . . , m } Ψ n (i) = m j=1 Γ n (i, j) (1 -V j/2 n ) k=1 (1 -U j,k n ) .
The map Ψ n (i) counts the number of chromosomes in generation n + 1 which have been obtained by selecting a chromosome among the best i chromosomes of generation n, and for which there was no crossover and no subsequent mutation. For any j, the map i → Γ n (i, j) is non-decreasing, therefore the map i → Ψ n (i) is also non-decreasing. For t ∈ N and i ∈ { 1, . . . , m }, let N n (t, i) n≥t be the Markov chain starting from i at time t and defined by

∀n ≥ t N n+1 (t, i) = Ψ n N n (t, i) .
Since the map Ψ n is non-decreasing, then the coupling defined above between the chains N n (t, i) n≥t , i ∈ { 1, . . . , m }, is monotone, i.e., we have

∀n ≥ t ∀i ≤ j N n (t, i) ≤ N n (t, j) .
This implies in particular that the Markov chain (N n (t, i)) n≥t is monotone (see appendix B for the precise definitions).

Proposition 6.1 For any t ∈ N and λ ∈ R, we have

∀n ≥ t N (X n , λ) ≥ N n t, N (X t , λ) .
Proof.

Let us fix λ ∈ R. At time t, there is equality. We prove the inequality by induction over n. Suppose that the inequality holds at time n ≥ t. The value Ψ n (N (X n , λ)) is a lower bound on the number of chromosomes in generation n + 1 which are an exact copy of one of the chromosomes of generation n which have a fitness larger than or equal to λ.

Therefore N (X n+1 , λ) ≥ Ψ n N (X n , λ) .
Using the inequality at time n and the monotonicity of Ψ n , we get

Ψ n N (X n , λ) ≥ Ψ n N n (t, N (X t , λ)) = N n+1 t, N (X t , λ) .
The induction step is completed.

Transition probabilities of N n

To alleviate the notation, we suppose that the Markov chain N n (t, i) n≥t starts at time 0, we remove t, i from the notation and we write simply (N n ) n≥0 . Let us compute the transition probabilities of (N n ) n≥0 . The null state is absorbing for the Markov chain (N n ) n≥0 . By definition, we have

∀n ≥ 1 N n+1 = m j=1 Γ n (N n , j) (1 -V j/2 n ) k=1 (1 -U j,k n ) .
The random variable N n+1 is a sum of m identically distributed Bernoulli random variables, whose parameter depends on the value of N n . Yet these random variables are not independent, because the crossover creates a correlation between two consecutive chromosomes (through the variable

V j/2 n
). In order to get rid of this correlation, we first count the number of crossover occurring in generation n, and then we sum over the indices where no crossover has taken place. Let B n be the random variable defined by

B n = m 2 - m/2 j=1 V j n .
The law of B n is the binomial law B(m/2, 1-p C ). Conditionally on N n = i, the law of N n+1 is the same as the law of the random variable

2Bn k=1 Y i k ,
where the variables

Y i k , k ∈ N, i ∈ { 1, . . . ,
ε m (i) = F m (m -i + 1) + • • • + F m (m) (1 -p M ) .
Finally, we have for i ∈ { 1, . . . , m } and j ∈ { 0, . . . , m },

P N n+1 = j | N n = i = m/2 b=0 m/2 b (1 -p C ) b p m/2-b C 2b j ε m (i) j (1 -ε m (i)) 2b-j .

Large deviations upper bound

The formula for the transition probabilities is very complicated, so we will study its asymptotics as m goes to ∞. The goal of this section is to prove the large deviations upper bound stated in proposition 6.4. We do not have a genuine large deviations principle for the chain (N n ) n≥0 , because there is some freedom left for the parameters p C , p M , . In order to derive a corresponding lower bound, we would have to fix the limiting value of p C and (1 -p M ) . However we wish to focus on the role of the parameter π, and for our purpose, we need only a large deviations upper bound under the constraint

π = σ(1 -p C )(1 -p M ) .
For p ∈ [0, 1] and t ≥ 0, we define Proof. We need only to distinguish a few cases. For 0 < p < 1, the result is straightforward. If p = 0 and t > 0, or if p = 1 and t < 1, we check that

I(p, t) =        t ln t p + (1 -t) ln 1 -t 1 -p 0 < p < 1, 0 ≤ t ≤ 1 0 t = p = 0 or t = p = 1 +∞ (p ∈ {0, 1}, t = p) or t >
lim inf n→∞ I(p n , t n ) = +∞ .
If p = t = 0 or if p = t = 1, the inequality holds since I(0, 0) = I(1, 1) = 0.

We define, for

s ∈]0, 1], t ∈ [0, 1], V 1 (s, t) = inf 1 2 I 1 -p, β + βI 1 -F (1 -s) π σ(1 -p) , t β : 0 ≤ p ≤ 1 - π σ , t ≤ β ≤ 1 .
We set also V 1 (0, 0) = 0 and V 1 (0, t) = +∞ for t > 0.

Lemma 6.3 The map V 1 (s, t) is sequentially lower semicontinuous in s, t, i.e., for any s, t ∈ [0, 1], any sequences (s n ) n≥1 , (t n ) n≥1 converging towards s, t, we have lim inf

n→∞ V 1 (s n , t n ) ≥ V 1 (s, t) . Proof. Let s, t ∈ [0, 1]. Let (s n ) n≥1 , (t n ) n≥1 be two sequences in [0, 1]
which converge towards s, t. For each n ≥ 1, let p n and β n be such that

0 ≤ p n ≤ 1 -π/σ , t n ≤ β n ≤ 1 , 1 2 I 1 -p n , β n + β n I 1 -F (1 -s n ) π σ(1 -p n ) , t n β n ≤ V 1 (s n , t n ) + 1 n .
By compactness, up to the extraction of a subsequence, we can suppose that there exist p, β, γ such that

0 ≤ p ≤ 1 -π/σ , t ≤ β ≤ 1 , lim n→∞ p n = p , lim n→∞ β n = β , lim n→∞ t n β n = γ .
Using the continuity of F and the lower semicontinuity of I, we obtain

lim inf n→∞ V 1 (s n , t n ) ≥ 1 2 I 1 -p, β + βI 1 -F (1 -s) π σ(1 -p) , γ .
Let us denote by ∆ the righthand quantity. We distinguish several cases:

• t > 0. We have then γ = t/ β, whence ∆ ≥ V 1 (s, t).

• t = 0, β > 0. We have then γ = 0, whence ∆ ≥ V 1 (s, 0).

• t = 0, β = 0, s > 0. We have then ∆ ≥ 1 2 I 1 -p, 0 ≥ V 1 (s, 0). • t = 0, β = 0, s = 0. Obviously, ∆ ≥ V 1 (0, 0) = 0.
In each case, we conclude that ∆ ≥ V 1 (s, t). This shows that V 1 is lower semicontinuous. Proposition 6.4 For any s ∈ [0, 1], any subset U of [0, 1], we have, for

any n ≥ 1, lim sup m→∞ 1 m ln P N n+1 ∈ mU | N n = sm ≤ -inf t∈U V 1 (s, t) . Proof. Let n ≥ 1, let i ∈ { 1, . . . , m } and j ∈ { 0, . . . , m }. From lemma D.1, we obtain that, for any b ≤ m/2, m/2 b (1 -p C ) b p m/2-b C 2b j ε m (i) j (1 -ε m (i)) 2b-j ≤ exp -m 1 2 I 1 -p C , 2b m + 2b m I ε m (i), j 2b + 4 ln m + 6 .
We take the maximum with respect to b, we sum and we get

P N n+1 = j | N n = i ≤ (m + 1) × exp -m min 0≤b≤m/2 1 2 I 1 -p C , 2b m + 2b m I ε m (i), j 2b + 4 ln m + 6 .
We seek next a large deviations upper bound for the transition probabilities. Let s ∈ [0, 1] and let us take i = ms . We first consider the cases s = 0 and s = 1. For s = 0, we have ε m (0) = 0 and

P N n+1 ∈ mU | N n = 0 = 0 if 0 ∈ mU 1 if 0 ∈ mU
and the inequality stated in the lemma holds. Suppose that s = 1. We have then

ε m (m) = (1 -p M ) = π σ(1 -p C )
.

It follows that

P N n+1 ∈ mU | N n = m ≤ (m + 1) 2 exp 4 ln m + 6 × exp -m min 0≤b≤m/2 min j∈mU 1 2 I 1 -p C , 2b m + 2b m I π σ(1 -p C ) , j 2b
≤ (m + 1) 2 exp 4 ln m + 6 exp -m min t∈U V 1 (1, t) .
Taking ln, dividing by m and sending m to ∞, we obtain the desired large deviations upper bound. From now on, we suppose that 0 < s < 1. We have

lim m→+∞ F m (m -sm + 1) + • • • + F m (m) = 1 -F (1 -s) whence ε m ( sm ) ∼ 1 -F (1 -s) (1 -p M ) as m → ∞ . Let us set ε(s) = 1 -F (1 -s) (1 -p M ) .
For any u ∈ [0, 1], we have

I ε m ( sm ), u -I ε(s), u ≤ ln ε(s) ε m ( sm ) + ln 1 -ε(s) 1 -ε m ( sm )
.

In order to bound these terms, we suppose in addition that 0 < s < 1.

Since F is strictly increasing on [0, 1] by hypothesis, then 0 < F (1 -s) < 1. It follows that there exist γ and m 0 (s) such that for m ≥ m 0 (s),

0 < γ < F m (m -sm + 1) + • • • + F m (m) < 1 -γ < 1 . Let us set ∆(s, m) = 1 -F (1 -s) -F m (m -sm + 1) + • • • + F m (m) .
Since, for any a ≤ 1, any x ∈]0, 1[,

∂ ∂x ln(1 -xa) = a 1 -xa ≤ 1 1 -x , we have, for m ≥ m 0 (s), ln 1 -ε(s) 1 -ε m ( sm ) ≤ 1 γ ∆(s, m) .
Similarly, we have

ln ε(s) ε m ( sm ) ≤ 1 γ ∆(s, m) .
These inequalities hold uniformly with respect to the value of (1 -p M ) .

Let now s ∈]0, 1[ and let U be a subset of [0, 1]. Collecting together the previous inequalities, we have, for any m ≥ m 0 (s),

P N n+1 ∈ mU | N n = sm ≤ (m + 1) 2 × exp -m min 0≤b≤m/2 min j∈mU 1 2 I 1 -p C , 2b m + 2b m I 1 -F (1 -s) π σ(1 -p C ) , j 2b
+4 ln m + 6 + 2m γ ∆(s, m) .
We are now in position to replace the discrete variational problem appearing in this inequality by a continuous one. Let V 1 (s, t) be the function defined before lemma 6.3. The previous inequality implies that, for any m ≥ m 0 (s),

P N n+1 ∈ mU | N n = sm ≤ (m + 1) 2 exp -m min t∈U V 1 (s, t) + 4 ln m + 6 + 2m γ ∆(s, m) .
Taking ln, dividing by m and sending m to ∞, we obtain the desired large deviations upper bound.

Proceeding in the same way, we can prove a similar large deviations upper bound for the l-step transition probabilities. For l ≥ 1, we define a function

V l on [0, 1] × [0, 1] by V l (s, t) = inf l-1 k=0 V 1 ρ k , ρ k+1 : ρ 0 = s, ρ l = t, ρ k ∈ [0, 1] for 0 ≤ k < l .
Corollary 6.5 For l ≥ 1, the l-step transition probabilities of (N n ) n≥0 satisfy the following large deviations upper bound: for any s ∈ [0, 1], any subset U of [0, 1], we have lim sup

m→∞ 1 m ln P N n+l ∈ mU | N n = sm ≤ -inf t∈U V l (s, t) .

Dynamics of N n

Let us examine when the rate function V 1 (s, t) vanishes. Let π > 1 and let s, t ∈ [0, 1]. By lemma 6.3, the variational problem defining V 1 (s, t) is well posed, i.e., there exists p * , β * ∈ [0, 1] such that 0

≤ p * ≤ 1 -π/σ, t ≤ β * ≤ 1 and V 1 (s, t) = 1 2 I 1 -p * , β * + β * I 1 -F (1 -s) π σ(1 -p * ) , t β * .
Thus V 1 (s, t) vanishes if and only if

β * = 1 -p * , 1 -F (1 -s) π σ(1 -p * ) = t β * , or equivalently t = 1 -F (1 -s) π σ .
We define a function φ

: [0, 1] → [0, 1] by ∀r ∈ [0, 1] φ(r) = 1 -F (1 -r) π σ .
The Markov chain (N n ) n≥0 can be seen as a random perturbation of the dynamical system associated to the map φ:

z 0 ∈ [0, 1] , ∀n ≥ 1 z n = φ(z n-1 ) .
Since φ is non-decreasing, the sequence (z n ) n∈N is monotonous and it converges to a fixed point of φ. We have supposed that F is convex, so that φ is concave. Moreover we have φ(0) = 0, φ(1) = π/σ < 1 and φ (0) = π, therefore:

• If π < 1, then the function φ admits only one fixed point, 0, and (z n ) n∈N converges to 0;

• If π > 1, the function φ admits two fixed points, 0 and ρ * (π), and (z n ) n∈N converges to ρ * (π) whenever z 0 > 0. We can even compute ρ * (π) for linear ranking and tournament selection: Linear ranking selection. In this case, we have

ρ * (π) = 2η + η + -η -1 - 1 π .
Tournament selection. The non null fixed point is the solution of

1 + ρ * (π) + • • • + ρ * (π) t-1 = σ π .
In the case where t = 2, we obtain

ρ * (π) = σ π -1 .
The natural strategy to study the Markov chain (N n ) n≥0 is to use the Freidlin-Wentzell theory [START_REF] Freidlin | Random perturbations of dynamical systems[END_REF]. The crucial quantity to analyze the dynamics is the following cost function V . We define, for s, t ∈ [0, 1],

V (s, t) = inf l≥1 V l (s, t) = inf l≥1 inf l-1 k=0 V 1 ρ k , ρ k+1 : ρ 0 = s, ρ l = t, ρ k ∈ [0, 1] for 0 ≤ k < l .
Lemma 6.6 Suppose that π > 1. For s, t ∈ [0, 1], we have V (s, t) = 0 if and only if

• either s = t = 0, • or s > 0, t = ρ * (π),
• or there exists l ≥ 1 such that t = φ l (s).

Proof. Throughout the proof, we write simply

ρ * instead of ρ * (π). Let s, t ∈ [0, 1] be such that V (s, t) = 0. For each n ≥ 1, let (ρ n 0 , . . . , ρ n l(n) ) be a sequence of length l(n) in [0, 1] such that ρ n 0 = s, ρ n l(n) = t, l(n)-1 k=0 V 1 ρ n k , ρ n k+1 ≤ 1 n .
If s = 0, then necessarily ρ n 1 = • • • = ρ n l(n) = 0 and t = 0. From now on, we suppose that s > 0. We consider two cases. If the sequence (l(n)) n≥1 is bounded, then we can extract a subsequence

ρ φ(n) 0 , . . . , ρ φ(n) l(φ(n))
such that l(φ(n)) = l does not depend on n and for any k ∈ { 0, . . . , l -1 }, the following limit exists:

lim n→∞ ρ φ(n) k = ρ k .
The map V 1 being lower semicontinuous, we have then

∀k ∈ { 0, . . . , l -1 } V 1 ρ k , ρ k+1 = 0 , whence ∀k ∈ { 0, . . . , l } ρ k = φ k (ρ 0 ) .
Since in addition ρ 0 = s and ρ l = t, we conclude that t = φ l (s). Suppose next that the sequence (l(n)) n≥1 is not bounded. Our goal is to show that t = ρ * . Using Cantor's diagonal procedure, we can extract a subsequence

ρ φ(n) 0 , . . . , ρ φ(n) l(φ(n))
such that, for any k ≥ 0, the following limit exists:

lim n→∞ ρ φ(n) k = ρ k .
The map V 1 being lower semicontinuous, we have then

∀k ≥ 0 V 1 ρ k , ρ k+1 = 0 , whence ∀k ≥ 0 ρ k = φ k (ρ 0 ) .
We have also V 1 ρ * , ρ * = 0. By lemma 6.3, there exist p * , β * such that 0

≤ p * ≤ 1 -π/σ, ρ * ≤ β * ≤ 1 and V 1 (ρ * , ρ * ) = 1 2 I 1 -p * , β * + β * I 1 -F (1 -ρ * ) π σ(1 -p * ) , ρ * β * . Since ρ * is in ]0, 1[, certainly we have β * > 0. Let ε > 0. The map t → β * I 1 -F (1 -ρ * ) π σ(1 -p * ) , t β *
is continuous at ρ * , thus there exists a neighborhood U of ρ * such that

∀ρ ∈ U V 1 (ρ * , ρ) ≤ ε .
Since s > 0, the sequence (φ n (s)) n∈N converges towards ρ * and φ h (s) ∈ U for some h ≥ 1. In particular,

lim n→∞ ρ φ(n) h = φ h (s) ∈ U , so that, for n large enough, ρ φ(n) h is in U and V (ρ * , t) ≤ V 1 ρ * , ρ φ(n) h + V ρ φ(n) h , t ≤ ε + 1 n .
Letting successively n go to ∞ and ε go to 0 we obtain that V (ρ * , t) = 0. Let δ ∈ ]0, ρ * /2[ and let U = ]ρ * -δ, ρ * + δ[. Let α be the infimum

α = inf V 1 ρ 0 , ρ 1 : ρ 0 ∈ U , ρ 1 ∈ U . Since V 1 is lower semicontinuous on the compact set U × [0, 1] \ U , then ∃(ρ * 0 , ρ * 1 ∈ U × [0, 1] \ U α = V 1 ρ * 0 , ρ * 1 .
The function φ is non-decreasing and continuous, therefore

φ U = φ [ρ * -δ, ρ * + δ] = φ(ρ * -δ), φ(ρ * + δ) .
Since ρ * is the unique fixed point of φ in ]0, 1], then φ(ρ) > ρ for ρ ∈]0, ρ * [ and φ(ρ) < ρ for ρ ∈]ρ * , 1[. Therefore we have

ρ * -δ < φ(ρ * -δ) ≤ φ(ρ * + δ) < ρ * + δ .
Thus φ(U ) ⊂ U and necessarily ρ * 1 = φ(ρ * 0 ) and α > 0. It follows that any sequence (ρ 0 , . . . , ρ l ) such that

ρ 0 ∈ U , l-1 k=0 V 1 ρ k , ρ k+1 < α
is trapped in U . As a consequence, a point t satisfying V (ρ * , t) = 0 must belong to U =]ρ * -δ, ρ * + δ[. This is true for any δ > 0, hence for any neighborhood of ρ * , thus t = ρ * .

Creation of a quasispecies

Our goal in this section is to prove a lower bound for the probability of the creation of a quasispecies around the current best fit chromosome in the population. The delicate situation is when there is only one chromosome in the population which has the best fitness. This chromosome might be destroyed or it might invade a positive fraction of the population. We will obtain a lower bound on the fixation probability by estimating the probability that the progeny of the best fit chromosome grows geometrically. The key estimate is stated in the next proposition. Proposition 6.7 Let π > 1 be fixed. There exist

δ 0 > 0 , ρ > 1 , c 0 > 0 , m 0 ≥ 1 ,
which depend on π only, such that: for any set of parameters , p

C , p M satisfying π = σ(1 -p C )(1 -p M ) , we have ∀m ≥ m 0 ∀i ∈ 1, . . . , δ 0 m P N n+1 ≤ ρi N n = i ≤ exp(-c 0 i) .
Proof. We recall that, conditionally on N n = i, the law of N n+1 is the same as the law of the random variable

2Bn k=1 Y i k ,
where the law of B n is the binomial law B(m/2, 1 -p C ), the variables

Y i k , k ∈ N, i ∈ { 1, . . . ,
ε m (i) = F m (m -i + 1) + • • • + F m (m) (1 -p M ) . Let ε > 0 be such that π(1 -ε) 2 > 1 and let l(m, ε) = m 2 (1 -p C )(1 -ε) + 1 + m 4 (1 -p C )ε .
For m large enough, we have

l(m, ε) < m 2 (1 -p C ) .
Let ρ > 1. We write

P N n+1 < ρi N n = i = P 2Bn k=1 Y i k < ρi ≤ P B n ≤ l(m, ε) + P 2l(m,ε) k=1 Y i k < ρi .
We control the first probability with the help of Hoeffding's inequality (see appendix E). The expected value of B n is m(1 -p C )/2 > l(m, ε), thus

P B n ≤ l(m, ε) ≤ exp - 2 m m 2 (1 -p C ) -l(m, ε) 2 .
Recall that 1 -p C > 1/σ. For m large enough, we have

m 2 (1 -p C ) -l(m, ε) ≥ m 2 (1 -p C ) ε 2 -1 ≥ mε 4σ -1 ≥ mε 8σ .
It follows that

P B n ≤ l(m, ε) ≤ exp - m 32
ε 2 σ 2 . To control the second probability, we decompose the sum into i blocks and we use the Tchebytcheff exponential inequality. Each block follows a binomial law, and we bound the Cramér transform of each block by the Cramér transform of a Poisson law having the same mean. More precisely, we choose for the block size

b = 2l(m, ε) - m 4 (1 -p C )ε i + 1 ,
and we define the sum associated to each block of size b:

∀j ∈ { 1, . . . , i } Y j = bj k=b(j-1)+1 Y i k .
Notice that Y 1 follows the binomial law with parameters b, ε m (i). We will next estimate from below the product bε m (i). By the choice of b and l, we have

b ≥ 1 i 2l(m, ε) - m 4 (1 -p C )ε , l(m, ε) ≥ m 2 (1 -p C ) 1 - ε 2 , whence b ≥ m i (1 -p C ) 1 -ε .
Let δ 0 > 0 be such that

δ 0 < 1 4 (1 -p C )ε .
Let m 0 ≥ 1 be associated to ε as in the hypothesis on F m (see section 3.1).

We have, for m ≥ m 0 and i ∈ 1, . . . , δ 0 m ,

ε m (i) ≥ σ(1 -ε) i m (1 -p M )
and we conclude from the previous inequalities that

bε m (i) ≥ (1 -p C )(1 -ε) 2 σ(1 -p M ) = π(1 -ε) 2 .
We choose ρ such that 1 < ρ < π(1 -ε) 2 , this implies in particular that

ρ < E(Y 1 ) = bε m (i) .
We have also that

bi ≤ 2l(m, ε) - m 4 (1 -p C )ε + i ≤ 2l(m, ε) - m 4 (1 -p C )ε + δ 0 m ≤ 2l(m, ε) .
We have then, using Tchebytcheff exponential inequality (see appendix E):

P 2l(m,ε) k=1 Y i k ≤ ρi ≤ P bi k=1 Y i k ≤ ρi ≤ P i j=1 Y j ≤ ρi ≤ P i j=1 -Y j ≥ -ρi ≤ exp -iΛ * -Y 1 (-ρ) , where Λ * -Y 1
is the Cramér transform of -Y 1 . Let Y 1 be a random variable following the Poisson law of parameter bε m (i). By lemma C.3, we have

Λ * -Y 1 (-ρ) ≥ Λ * -Y 1 (-ρ) = ρ ln ρ bε m (i) -ρ + bε m (i) .
The map

λ → ρ ln ρ λ -ρ + λ is non-decreasing on [ρ, +∞[, thus Λ * -Y 1 (-ρ) ≥ ρ ln ρ π(1 -ε) 2 -ρ + π(1 -ε) 2 .
Let us denote by c 0 the righthand quantity. Then c 0 is positive and it depends only on ρ, π and ε. Finally, we have for m ≥ m 0 , i ∈ 1, . . . , δ 0 m ,

P 2l(m,ε) k=1 Y i k ≤ ρi ≤ exp(-c 0 i) whence P N n+1 ≤ ρi N n = i ≤ exp - m 32
ε 2 σ 2 + exp(-c 0 i) .
Let η ∈]0, 1[ be small enough so that

∃ m 1 ∀m ≥ m 1 exp - m 32
ε 2 σ 2 ≤ exp -η mc 0 2 1-exp -η c 0 2 .
For m ≥ max(m 0 , m 1 ) and i ∈ 1, . . . , δ 0 m , we have

P N n+1 ≤ ρi N n = i ≤ exp -η ic 0 2 1 -exp -η c 0 2 + exp -ηic 0 ≤ exp -η ic 0 2
and this inequality yields the claim of the proposition.

We define τ 0 = inf n ≥ 1 : N n = 0 .

For δ > 0, let T (δ) be the first time the process (N n ) n≥0 becomes larger than δm:

T (δ) = inf { n ≥ 0 : N n ≥ δm } .
Proposition 6.8 Let π > 1 be fixed. There exist δ 0 > 0 and p 0 > 0 which depend only on π such that

∀m ≥ 1 P T (δ 0 ) ≤ κ ln m, τ 0 > T (δ 0 ) | N 0 = 1 ≥ p 0 .
Proof. Let T k be the first time the process (N n ) n≥0 hits k:

T k = inf { n ≥ 0 : N n = k } .
Let δ 0 , ρ > 1, c 0 , m 0 be as given in proposition 6.7. We suppose that the process (N n ) n≥0 starts from N 0 = 1. Let E be the event:

E = ∀k ∈ 1, . . . , δ 0 m N T k +1 > ρN T k .
We claim that, on the event E, we have

∀n ≤ T (δ 0 ) N n+1 > ρN n .
Let us prove this inequality by induction on n. We have T 0 = 0 and N 1 > ρN 0 , so that the inequality is true for n = 0. Suppose that the inequality has been proved until rank n < T (δ 0 ), so that

∀k ≤ n N k+1 > ρN k .
This implies in particular that

N 0 < N 1 < . . . < N n < mδ 0 .
Suppose that N n = i. The above inequality implies that T i = n and

N Ti+1 = N n+1 > ρN n ,
so that the inequality still holds at rank n + 1. Iterating the inequality until time T (δ 0 ) -1, we see that

N T (δ0)-1 > ρ T (δ0)-1 .
Moreover N T (δ0)-1 ≤ mδ 0 , thus

T (δ 0 ) ≤ 1 + ln(mδ 0 ) ln ρ .
Let m 1 ≥ 1 and κ > 0 such that

∀m ≥ m 1 1 + ln(mδ 0 ) ln ρ ≤ κ ln m .
The constants m 1 , κ depend only on δ 0 and ρ, and we have

P T (δ 0 ) ≤ κ ln m, τ 0 > T (δ 0 ) | N 0 = 1 ≥ P (E) .
By lemma A.2, the random variables N T k +1 , k ≤ δ 0 m, are independent. To be precise, we cannot directly apply lemma A.2, because the Markov chain (N n ) n≥0 has an absorbing state at 0 and therefore it is not irreducible. So we consider the modified Markov chain ( N n ) n≥0 which has the same transition probabilities as (N n ) n≥0 , except that we set the transition probability from 0 to 1 to be 1. The event we wish to estimate in the lemma has the same probability for both processes. Indeed, we require that T (δ 0 ) ≤ κ ln m and τ 0 > T (δ 0 ), so that the processes do not visit 0 before T (δ 0 ). Using proposition 6.7, we obtain, for m larger than m 0 and m 1 ,

P (E) ≥ δ0m k=1 P N T k +1 > ρN T k ) = δ0m k=1 1 -P N 1 ≤ ρk N 0 = k ≥ δ0m k=1 1 -exp(-c 0 k) ≥ ∞ k=1 1 -exp(-c 0 k) .
The last infinite product is converging. Let us denote its value by p 1 . Let also

p 2 = min P T (δ 0 ) ≤ κ ln m, τ 0 > T (δ 0 ) | N 0 = 1 : m ≤ max(m 0 , m 1 ) .
The value p 2 is positive and the inequality stated in the proposition holds with p 0 = min(p 1 , p 2 ). Lemma 6.9 Let π > 1 be fixed. For any δ > 0, there exist h ≥ 1, c > 0, m 0 ≥ 1, which depend only on δ and π, such that: for any set of parameters

, p C , p M satisfying π = σ(1 -p C )(1 -p M ) , we have, for any m ≥ m 0 , P N 1 > 0, . . . , N h-1 > 0, N h > m(ρ * -δ) | N 0 = mδ ≥ 1 -exp(-cm) .
Proof. Let δ > 0. The sequence (φ n (δ)) n∈N converges to ρ * , thus there exists h ≥ 1 such that φ h (δ) > ρ * -δ. By continuity of the map φ, there exist ρ 0 , ρ 1 , . . . , ρ h > 0 such that ρ 0 = δ, ρ h > ρ * -δ and

∀k ∈ { 1, . . . , h } φ(ρ k-1 ) > ρ k . Now, P N 1 > 0, . . . , N h-1 > 0, N h > m(ρ * -δ) | N 0 = mδ ≥ P ∀k ∈ { 1, . . . , h } N k ≥ mρ k | N 0 = mδ .
Passing to the complementary event, we have

P ∃k ∈ { 1, . . . , h -1 } N k = 0 or N h ≤ m(ρ * -δ) | N 0 = mδ ≤ P ∃k ∈ { 1, . . . , h } N k < mρ k | N 0 = mδ ≤ 1≤k≤h P N 1 ≥ mρ 1 , . . . , N k-1 ≥ mρ k-1 , N k < mρ k | N 0 = mδ ≤ 1≤k≤h i≥mρ k-1 P N k-1 = i, N k < mρ k | N 0 = mδ ≤ 1≤k≤h i≥mρ k-1 P N k < mρ k | N k-1 = i P N k-1 = i | N 0 = mδ ≤ 1≤k≤h P N 1 < mρ k | N 0 = mρ k-1 .
The large deviations upper bound for the transition probabilities of the Markov chain (N n ) n≥0 stated in proposition 6.4 implies that

∀k ∈ { 1, . . . , h } lim sup m→∞ 1 m ln P N 1 < mρ k | N 0 = mρ k-1 ≤ -inf V 1 ρ k-1 , t : t ≤ ρ k < 0 .
Since h is fixed, we conclude that lim sup

m→∞ 1 m ln P ∃k ∈ { 1, . . . , h -1 } N k = 0 or N h ≤ m(ρ * -δ) N 0 = mδ < 0
and this yields the desired estimate.

With the estimate of lemma 6.9, we show that the process is very unlikely to stay a long time in [mδ, m(ρ * -δ)].

Corollary 6.10 Let π > 1 be fixed. For any δ > 0, there exist h ≥ 1, c > 0, m 0 ≥ 1, which depend only on δ and π, such that: for any set of parameters

, p C , p M satisfying π = σ(1 -p C )(1 -p M ) , we have, for any m ≥ m 0 , ∀k ∈ [mδ, m(ρ * -δ)] ∀n ≥ 0 P mδ ≤ N t ≤ m(ρ * -δ) for 0 ≤ t ≤ n | N 0 = k ≤ exp -cm n h .
Proof.

Let i ≥ (ρ * -δ)m . The strategy consists in looking at the portion of the trajectory starting at the last visit to the neighborhood of ρ * before reaching the neighborhood of 0. Accordingly, we define

S = max n ≤ τ δ : N n > (ρ * -δ)m .
Notice that S is not a Markov time. We write, for n, k ≥ 1,

P τ δ ≤ n | N 0 = i = 1≤s<t≤n P τ δ = t, S = s | N 0 = i = 1≤s<t≤n s<t≤s+k P τ δ = t, S = s | N 0 = i + 1≤s<n s+k<t≤n P τ δ = t, S = s | N 0 = i .
Let h ≥ 1 and c > 0 be associated to δ as in corollary 6.10. For 1 ≤ s < n and t > s + k,

P τ δ = t, S = s | N 0 = i = mδ≤j≤(ρ * -δ)m P τ δ = t, S = s, N s+1 = j | N 0 = i ≤ mδ≤j≤(ρ * -δ)m P δm ≤ N r ≤ (ρ * -δ)m for s + 1 ≤ r ≤ t -1 N s+1 = j ≤ m exp -cm t -s -2 h , whence 1≤s<n s+k<t≤n P τ δ = t, S = s | N 0 = i ≤ n t≥k m exp -cm t -1 h . For 1 ≤ s < t ≤ n and t ≤ s + k, P τ δ = t, S = s | N 0 = i ≤ j>(ρ * -δ)m P τ δ = t, S = s, N s = j | N 0 = i ≤ j>(ρ * -δ)m P N t < δm | N s = j ≤ mP N t-s < δm | N 0 = (ρ * -δ)m , whence 1≤s<n s<t≤s+k P τ δ = t, S = s | N 0 = i ≤ n 1≤t≤k mP N t < δm | N 0 = (ρ * -δ)m .
Let h ≥ 1, c > 0 as in lemma 6.9. We suppose that m is large enough so that κ ln m ≥ h. Using again the Markov property, we obtain

P T (ρ * -δ) ≤ κ ln m N 0 = mδ ≥ P N 1 > 0, . . . , N h-1 > 0, N h > m(ρ * -δ) N 0 = mδ ≥ 1 -exp(-cm) .
Putting together the previous inequalities, and using the inequality of proposition 6.8, we conclude that for m large enough,

P T (ρ * -δ) ≤ 2κ ln m N 0 = 1 ≥ 1 -exp(-cm) p 0 .
This implies the result stated in the proposition.

Corollary 6.15 Let π > 1 be fixed. For any V * < V (ρ * , 0), there exists p * > 0, which depends only on V * and π, such that: for any set of parameters , p C , p

M satisfying π = σ(1 -p C )(1 -p M ) , we have ∀m ≥ 1 P τ 0 ≥ exp(mV * ) N 0 = 1 ≥ p * .
Proof. Let V * < V (ρ * , 0). Let δ > 0 and m 0 ≥ 1 be associated to V * as in corollary 6.13. Let κ > 0 and p 1 > 0 be associated to δ as in proposition 6.14. We write

P τ 0 ≥ exp(mV * ) N 0 = 1 ≥ P τ 0 ≥ exp(mV * ), T (ρ * -δ) ≤ κ ln m | N 0 = 1 ≥ i>(ρ * -δ)m P τ 0 ≥ exp(mV * ), T (ρ * -δ) ≤ κ ln m, N T (ρ * -δ) = i | N 0 = 1 ≥ i>(ρ * -δ)m P τ 0 ≥ exp(mV * ) N T (ρ * -δ) = i, τ 0 > T (ρ * -δ) P N T (ρ * -δ) = i, τ 0 > T (ρ * -δ), T (ρ * -δ) ≤ κ ln m | N 0 = 1 ≥ P τ 0 ≥ exp(mV * ) N 0 = (ρ * -δ)m ×P τ 0 > T (ρ * -δ), T (ρ * -δ) ≤ κ ln m | N 0 = 1 .
Since τ 0 ≥ τ δ , we have by corollary 6.13 that for m ≥ m 0 ,

P τ 0 ≥ exp(mV * ) | N 0 = (ρ * -δ)m ≥ 1 -exp(-mδ) ,
whence, by proposition 6.14,

P τ 0 ≥ exp(mV * ) N 0 = 1 ≥ (1 -exp(-mδ)) p 1 .
For m < m 0 , the above probability is still positive, and we obtain the desired conclusion.

≥ 0 N (X n , f * 0 ) ≥ N n 0, 1)
. Let V * > 0 be such that V * < V (ρ * , 0). By corollary 6.15, there exists p * > 0, which depends on π and V * only, such that

∀m ≥ 1 P ∀n ≤ exp(mV * ) N n (0, 1) ≥ 1 ≥ p * .
This yields the conclusion of theorem 2.2.

Proof of theorem 2.3

We apply proposition 6.1 with n = t, starting time s

, λ = Λ X s , ρ * m . By definition of Λ, N X s , Λ X s , ρ * m ≥ ρ * m , therefore ∀t ≥ s N X t , Λ X s , ρ * m ≥ N t s, ρ * m .
If for some time t > s, we have

max 1≤i≤m f X t (i) < Λ X s , ρ * m , then N X t , Λ X s , ρ * m = 0 ,
and from the previous inequality, we conclude that N t s, ρ * m = 0. Yet

P N t s, ρ * m = 0 ≤ P τ 0 ≤ t -s N 0 = ρ * m .
Let V * > 0 be such that V * < V (ρ * , 0). Let δ > 0 as in lemma 6.12. By proposition 6.11, there exists m 0 ≥ 1 such that, for m ≥ m 0 ,

P τ 0 ≤ t -s N 0 = ρ * m ≤ (t -s) exp(-V * m) .
We sum this inequality over s, t such that s < t ≤ exp(V * m/4) to obtain

P ∃ t ≤ exp(V * m/4) max 1≤i≤m f X t (i) < max 0≤s≤t Λ X s , ρ * m ≤ 0≤s<t≤exp(V * m/4) (t -s) exp(-V * m) ≤ exp(-V * m/4) .
This proves theorem 2.3.

Thus, by proposition 6.14, there exist κ > 0 and p 1 > 0 such that, for any x 1 ∈ L γ, 1 , and any m ≥ 1,

P τ L γ, (ρ * -δ)m ≤ κ ln m + 1 X 1 = x 1 ≥ P T (ρ * -δ) ≤ κ ln m + 1 N 1 = 1 ≥ p 1 .
Combining the previous bounds, we get

∀x 0 ∈ L λ, 1 P τ L γ, (ρ * -δ)m ≤ κ ln m + 1 X 0 = x 0 ≥ p 1 1 2m (p M ) ∆(λ,γ) .
We decompose { 1, . . . , n } into subintervals of length κ ln m + 1 and we use the previous estimate: we obtain that for any x 0 ∈ L(λ, 1) and n ≥ 1,

P τ L(λ, 1) c > n, τ L γ, (ρ * -δ)m > n X 0 = x 0 ≤ 1 -p 1 1 2m (p M ) ∆(λ,γ) n κ ln m + 1 .
Let next x 0 ∈ L λ, (ρ * -δ)m . We use proposition 6.11 and the previous estimate: there exists m 0 ≥ 1 such that, for n ≥ 1,

P τ L γ, (ρ * -δ)m > n X 0 = x 0 ≤ P τ L(λ, 1) c ≤ n X 0 = x 0 +P τ L(λ, 1) c > n, τ L γ, (ρ * -δ)m > n X 0 = x 0 ≤ n exp -mV * + exp -p 1 1 2m (p M ) ∆(λ,γ) n κ ln m + 1 .
We choose

κ * = 8κV * p 1 , n = 1 2 κ * (ln m)m 2 (p M ) -∆(λ,γ) ,
and for m large enough, we obtain the estimate stated in the lemma.

Let now λ 0 < • • • < λ r be an increasing sequence such that

λ 0 = min f (u) : u ∈ { 0, 1 } , λ r = max f (u) : u ∈ { 0, 1 } .
Let π > 1, V * < V (ρ * , 0) and let δ, κ * , m 0 as given by lemma 7.1. We write The bound on the expectation of τ * is a consequence of this estimate and lemma A.3. This completes the proof of theorem 2.4. We complete next the proof of theorem 2.5. The proof is a variant of the previous argument. We take c * such that We conclude as before with the help of lemma A.3.

Lemma A.1 For any subsets V, G of E, we have

µ(G) ≤ sup x∈V P τ G < τ V X 0 = x sup y∈G E τ V X 0 = y .
Proof. From the representation formula for the invariant measure, we obtain that

µ(G) ≤ sup x∈V E τ V -1 k=0 1 G (X k ) X 0 = x .
Let us try to bound the last expectation. We denote by E x the expectation for the Markov chain starting from x. We have

E x τ V -1 k=0 1 G (X k ) = E x y∈G 1 τ G <τ V 1 Xτ G =y τ V -1 k=0 1 G (X k ) = y∈G E y τ V -1 k=0 1 G (X k ) P x τ G < τ V , X τ G = y ≤ y∈G E y τ V P x τ G < τ V , X τ G = y ≤ sup y∈G E y τ V P x τ G < τ V .
Taking the supremum over x ∈ V , we obtain the inequality stated in the lemma.

For x ∈ E, we define T (x) = inf n ≥ 0 : X n = x .

Lemma A.2 Let k ≥ 1 and let x 1 , . . . , x k be k distinct points of E. The random variables X T (x1)+1 , . . . , X T (x k )+1 are independent.

Proof. We do the proof by induction over k. For k = 1, there is nothing to prove. Let k ≥ 2 and suppose that the result has been proved until rank k -1. Let x 1 , . . . , x k be k distinct points of E. Let y 1 , . . . , y k be k points of E. Let us set T = min T (x i ) : 1 ≤ i ≤ k . We use the induction hypothesis:

P ∀j = i X T (xj )+1 = y j | X 0 = y i = j =i
p(x j , y j ) .

Reporting in the sum, we get P X T (x1)+1 = y 1 , . . . , X T (x k )+1 = y k = = 1≤i≤k 1≤j≤k p(x j , y j )P T = T (x i ) = 1≤j≤k p(x j , y j ) .

This completes the induction step and the proof. Proof. Reversing the inequality, we have

∀x ∈ E P τ > k | X 0 = x ≤ 1 -β .
Since the bound is uniform with respect to x, we prove by induction on n that ∀x ∈ E ∀n ≥ 1 P τ > nk | X 0 = x ≤ (1 -β) n .

C Stochastic domination

Let µ, ν be two probability measures on R. We say that ν stochastically dominates µ, which we denote by µ ν, if for any non-decreasing positive function f , we have µ(f ) ≤ ν(f ).

Lemma C.1 Let n ≥ 1, p ∈ [0, 1], λ > 0 be such that (1 -p) n ≥ exp(-λ).

Then the binomial law B(n, p) of parameters n, p is stochastically dominated by the Poisson law P(λ) of parameter λ.

Proof. Let X 1 , . . . , X n be independent random variables with common law the Poisson law of parameter -ln(1 -p). Let Y be a further random variable, independent of X 1 , . . . , X n , with law the Poisson law of parameter λ -n ln(1 -p). Obviously, we have

Y + X 1 + • • • + X n ≥ min(X 1 , 1) + • • • + min(X n , 1) .
Moreover, the law of the lefthand side is the Poisson law of parameter λ, while the law of the righthand side is the binomial law B(n, p).

Lemma C. For any α, t ∈ R, Λ αX (t) = Λ X (αt) ≤ np exp(αt) -1 .

Thus, taking λ = np, we conclude that ∀t ∈ R Λ αX (t) ≤ Λ αY (t) .

Taking the Fenchel-Legendre transform, we obtain ∀x ∈ R Λ * αX (x) ≥ Λ * αY (x) as required.

D Binomial estimate

We recall a basic estimate for the binomial coefficients.

Repeat•

  Select two chromosomes from the generation n • Perform the crossover • Perform the mutation • Put the two resulting chromosomes in generation n + 1 Until there are m chromosomes in generation n + 1

≥ 1 -

 1 k , (ρ * -δ)m -τ L λ k-1 , (ρ * -δ)m .Thus, for any starting population x 0 , we haveP τ * ≤ κ * 2 (ln m)m 2 r k=1 (p M ) -∆(λ k-1 ,λ k ) X 0 = x 0 ≥ P ∀k ∈ { 1, . . . , r } τ L λ k , (ρ * -δ)m -τ L λ k-1 , (ρ * -δ)m ≤ κ * 2 (ln m)m 2 (p M ) -∆(λ k-1 ,λ k ) X 0 = x 0 .To control this last probability, we use repeatedly the Markov property and the estimate of lemma 7.1. Finally, we obtainP τ * ≤ κ * 2 (ln m)m 2 r k=1 (p M ) -∆(λ k-1 ,λ k ) X 0 = x 0 ≥ ≥ r k=1 1 -κ * (ln m)m 2 (p M ) -∆(λ k-1 ,λ k ) exp -mV * .We complete now the proof of theorem 2.4. We suppose that m ≥ c * ln and that p M ≥ c * / . Since ∆(λ k-1 , λ k ) ≤ for any k, we have for m large enough∀k ∈ { 1, . . . , r } κ * (ln m)m 2 (p M ) -∆(λ k-1 ,λ k ) ≤ exp 2m/c * .We take c * such that 2/c * < V * /2 and we obtain, for m large enough, ) -∆(λ k-1 ,λ k ) X 0 = x 0 exp -mV * /2

c

  * > κ * , c * > 4 V * , c * > 2γ V * ∆ .We suppose that m ≥ c * ∆ ln and thatp M ≥ c * / . Let k ∈ { 1, . . . , r }. Since ∆(λ k-1 , λ k ) ≤ ∆, we have for m large enough, κ * (ln m)m 2 (p M ) -∆(λ k-1 ,λ k ) ≤ (ln m)m 2 ∆ ≤ exp 2m/c * . m)m 2 γ+∆ X 0 = x 0 ≥ 1 -exp -mV * /2

  Let us computeP X T (x1)+1 = y 1 , . . . , X T (x k )+1 = y k = 1≤i≤k P X T (x1)+1 = y 1 , . . . , X T (x k )+1 = y k , T = T (x i ) = 1≤i≤k P X T (x1)+1 = y 1 , . . . , X T (x k )+1 = y k | T = T (x i ) P T = T (x i ) = 1≤i≤k P ∀j = i X T (xj )+1 = y j , X 1 = y i | X 0 = x i P T = T (x i ) = 1≤i≤k p(x i , y i )P ∀j = i X T (xj )+1 = y j | X 0 = y i P T = T (x i ) .

Lemma A. 3

 3 Let τ be a stopping time associated to the Markov chain (X t ) t≥0 . If there exists an integer k and β positive such that∀x ∈ E P τ ≤ k | X 0 = x ≥ β , then we have ∀x ∈ E E τ | X 0 = x ≤ k β .

Lemma D. 1

 1 For any n ≥ 1, any k ∈ { 0, . . . , n }, we haveln n! k!(n -k)! + k ln k n + (n -k) ln n -k n ≤ 2 ln n + 3 .Proof. The proof is standard (see for instance[START_REF] Ellis | Entropy, large deviations, and statistical mechanics[END_REF]). Setting, for n ∈ N,φ(n) = ln n! -n ln n + n, we have ln n! k!(n -k)! = ln n! -ln k! -ln(n -k)! = n ln n-n+φ(n)-k ln k-k+φ(k) -(n-k) ln(n-k)-(n-k)+φ(n-k) = -k ln k n -(n -k) ln n -k n + φ(n) -φ(k) -φ(n -k) .

  m }, are Bernoulli i.i.d. random variables (independent of B n as well) with parameter

  1 or p > 1 The function I(p, •) is the rate function governing the large deviations of the binomial distribution B(n, p) with parameters n and p. It is standard that I is lower semicontinuous with respect to t, yet we will need a little more, as stated in the next lemma. The map I(p, t) is sequentially lower semicontinuous in p, t, i.e., for any p ∈ [0, 1], t ∈ R + , any sequences (p n ) n≥1 , (t n ) n≥1 converging towards p, t, we have lim inf

	Lemma 6.2

n→∞ I(p n , t n ) ≥ I(p, t) .

  m }, are Bernoulli i.i.d. random variables with parameter

7

  Proof of theorems 2.2, 2.3 2.4, 2.5, 2.6 7.1 Proof of theorem 2.2

	Let f * 0 be as in theorem 2.2. By proposition 6.1, we have
	∀n

  Let Y be a random variable following the Poisson law P(λ). For any t ∈ R, we haveΛ Y (t) = ln E exp(tY ) = ln For any α, t ∈ R, Λ αY (t) = Λ Y (αt) = λ exp(αt) -1 . Let p ∈ [0, 1] and let n ≥ 1.Let X be a random variable following the binomial law B(n, p). Let Y be a random variable following the Poisson law P(np). For any α ∈ R, we have Λ * αX ≥ Λ * αY . Proof. For any t ∈ R, we have Λ X (t) = ln E exp(tX) = n ln 1 -p + p exp(t) ≤ np exp(t) -1 .

	Let us compute the Fenchel-Legendre transform Λ * αY . By definition, for
	x ∈ R,
	Λ * αY (x) = sup
	The maximum is attained at t = (1/α) ln(x/(λα)), hence
		Λ * αY (x) =	x α	ln		x λα	-	x α	+ λ .
	Lemma C.3
	k≥t	λ k k!	exp(-λ) =	k≥t	λ k-t k!	exp(-λ)λ t
							≤	k≥t	t k-t k!	exp(-λ)λ t ≤	λe t
				∞ k=0	λ k k!	exp(-λ + kt) = λ exp(t) -1 .

2 Let λ > 0 and let Y be a random variable with law the Poisson law P(λ) of parameter λ. For any t ≥ λ, we have

P (Y ≥ t) ≤ λe t t .

Proof. We write

P (Y ≥ t) = t .

t∈R tx -λ exp(αt) -1 .

  Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Transition matrix of the SGA . . . . . . . . . . . . . . . . . 4 Coupling for the genetic algorithm 5 The disordered regime 5.1 Genealogy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Bound on T n . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Bound on N * n . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Proof of theorem 2.1 . . . . . . . . . . . . . . . . . . . . . . 6 The quasispecies regime 6.1 The auxiliary chain . . . . . . . . . . . . . . . . . . . . . . . 6.2 Transition probabilities of N n . . . . . . . . . . . . . . . . . 6.3 Large deviations upper bound . . . . . . . . . . . . . . . . . 6.4 Dynamics of N n . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Creation of a quasispecies . . . . . . . . . . . . . . . . . . . 6.6 The catastrophe . . . . . . . . . . . . . . . . . . . . . . . . 7 Proof of theorems 2.2, 2.3 2.4, 2.5, 2.6 7.1 Proof of theorem 2.2 . . . . . . . . . . . . . . . . . . . . . . 7.2 Proof of theorem 2.3 . . . . . . . . . . . . . . . . . . . . . . 7.3 Proof of theorems 2.4, 2.5 . . . . . . . . . . . . . . . . . . . 7.4 Proof of theorem 2.6 . . . . . . . . . . . . . . . . . . . . . .

	Contents
	1 Introduction
	2 Main results
	3 The model
	3.1 A Markov chains
	B Monotonicity
	C Stochastic domination
	D Binomial estimate
	E Exponential inequalities

Proof.

Let k ∈ [mδ, m(ρ * -δ)]. Let δ > 0 and let h ≥ 1 and c > 0 be associated to δ as in lemma 6.9. We divide the interval { 0, . . . , n } into subintervals of length h and we use repeatedly the estimate of lemma 6.9. Let i ≥ 0. We write

Iterating this inequality, we obtain

The claim of the corollary follows by applying this inequality with i equal to the integer part of n/h.

The catastrophe

We have computed the relevant estimates to reach the neighborhood of ρ * . Our next goal is to study the hitting time τ 0 starting from a neighborhood of ρ * . Since we need only a lower bound, we shall study the hitting time of a neighborhood of 0. For δ > 0, we define

Proposition 6.11 Let π > 1 be fixed. For any δ > 0, there exists m 0 ≥ 1, which depend only on δ and π, such that: for any set of parameters , p

Putting together the previous inequalities, we obtain

We choose k large enough so that lim sup

and we use the large deviations upper bound stated in corollary 6.5 to estimate the second sum:

Therefore there exists m 0 ≥ 1 such that,

This proves the proposition. Lemma 6.12 Let V * < V (ρ * , 0). There exists δ > 0 such that

For δ > 0, we have

We bound next V (ρ * , ρ * -δ) and V (δ, 0):

and the righthand terms go to 0 when δ goes to 0. Thus we can choose δ > 0 such that

We have then

and the lemma is proved.

Corollary 6.13 For any V * < V (ρ * , 0), there exist δ > 0 and m 0 ≥ 1 such that

Proof.

Let δ > 0 be associated to V * as in lemma 6.12. We apply proposition 6.11 with δ and n = exp(mV * ): there exists m 0 ≥ 1 such that

This is the desired inequality.

For δ > 0, let T (ρ * -δ) be the first time the process (N n ) n≥0 becomes larger than (ρ * -δ)m:

Proposition 6.14 Let π > 1 be fixed. For any δ > 0, there exist κ > 0 and p 1 > 0, which depend only on π and δ, such that: for any set of parameters , p C , p

Proof. Let κ, δ 0 be given by proposition 6.8. Let δ > 0 be associated to V * as in corollary 6.13. We suppose in addition that δ < δ 0 . We have

Proof of theorems 2.4, 2.5

For E a subset of { 0, 1 } m , we define the entrance time of the genetic algorithm in E as

For λ ∈ R and k ≥ 1, we define L(λ, k) as the set of the populations containing at least k chromosomes with a fitness larger than or equal to λ:

Recall that the quantity ∆(λ, γ) is defined just before theorem 2.4.

). There exist positive constants δ, κ * , m 0 which depend only on π and V * such that

Proof.

Let π > 1. Let V * < V (ρ * , 0). Let δ > 0 and m 0 ≥ 1 be associated to V * as in corollary 6.13. Let p 1 > 0 be associated to δ as in proposition 6.14. Let us fix λ < γ ∈ R. By the very definition of ∆(λ, γ), any chromosome in L(λ) can be transformed with at most ∆(λ, γ) mutations into a chromosome of L(γ), and the corresponding probability is bounded from below by

Let x 0 belong to L λ, 1 . The population x 0 contains at least one chromosome belonging to L(λ). By estimating the probability that this chromosome is selected, that there is no crossover on it, and that it is transformed by mutation into a chromosome in L(γ), we obtain that

The hypothesis on F m (see section 3.1) implies that, for m large enough, F m (m) ≥ σ/(2m). Since we have also π > 1, then

Suppose next that X 1 belongs to L γ, 1 . Then the population X 1 contains at least one chromosome in L(γ), hence N (X 1 , γ) ≥ 1, and by proposition 6.1, we have ∀n ≥ 1 N (X n , γ) ≥ N n 1, 1) .

Proof of theorem 2.6

Let V * < V (ρ * , 0) and let δ > 0 as in lemma 6.12. Let

We apply the estimate on the invariant measure given in lemma A.1 with the following sets:

We obtain

Let x ∈ V and n ≥ 1. We have

We estimate separately each term. Let i = N x, λ * . Then i ≥ (ρ * -δ)m and

From proposition 6.1, if X 0 = x, we have

Applying proposition 6.11, we obtain, for m large enough,

For the second term, we remark that, on the event { n < τ G < τ V }, we have that

We use proposition 6.14 and we decompose { 1, . . . , n } into subintervals of length κ ln m + 1 to conclude that

Putting together the previous inequalities, we have, for n ≥ 1,

n κ ln m+1 .

59

We take n = m 2 and we conclude that, for m large enough,

Let next y ∈ G. Using the bounds obtained in theorem 2.4 with r = 1 and ∆ = , we have

Inspecting the proof of theorem 2.4, we see that we have in fact proved this estimate for τ V (this is a little stronger since τ V ≥ τ * ). Thus, for p M ≥ c * / , m ≥ c * ln and m large enough, we have

We choose c * large enough in order to obtain the conclusion of theorem 2.6.

A Markov chains

We state here some results on Markov chains with finite state space which we use in the main proofs. In the sequel, we consider a discrete time Markov chain (X t ) t≥0 with values in a finite state space E and with transition matrix (p(x, y)) x,y∈E .

Invariant probability measure. If the Markov chain is irreducible and aperiodic, then it admits a unique invariant probability measure µ, i.e., the set of equations

admits a unique solution.

Representation formula. Let us suppose that the Markov chain (X t ) t≥0 is irreducible and aperiodic. Let µ be the invariant probability measure of (X t ) t≥0 . Let V be a non-empty subset of E. We define

We have then, for any subset G of E,

This formula can be found in the book of Freidlin and Wentzell (see chapter 6, section 4 of [START_REF] Freidlin | Random perturbations of dynamical systems[END_REF]), where it is attributed to Khas'minskii, and in the book of Kifer [START_REF] Kifer | Random perturbations of dynamical systems[END_REF][START_REF] Kifer | A discrete-time version of the Wentzell-Freidlin theory[END_REF].

We compute next the expectation of τ as follows: for x ∈ E,

as requested.

B Monotonicity

We first recall some standard definitions concerning monotonicity and coupling for stochastic processes. A classical reference is Liggett's book [START_REF] Thomas | Interacting particle systems[END_REF], especially for applications to particle systems. In the next two definitions, we consider a discrete time Markov chain (X n ) n≥0 with values in a space E. We suppose that the state space E is finite and that it is equipped with a partial order ≤. A function f :

Definition B.1 The Markov chain (X n ) n≥0 is said to be monotone if, for any non-decreasing function f , the function

A natural way to prove monotonicity is to construct an adequate coupling.

Definition B.2 A coupling for the Markov chain (X n ) n≥0 is a family of processes (X x n ) n≥0 indexed by x ∈ E, which are all defined on the same probability space, and such that, for x ∈ E, the process (X x n ) n≥0 is the Markov chain (X n ) n≥0 starting from X 0 = x. The coupling is said to be monotone if

If there exists a monotone coupling, then the Markov chain is monotone.

Comparing the discrete sum ln n! = 1≤k≤n ln k to the integral

E Exponential inequalities

Hoeffding's inequality. We state Hoeffding's inequality for Bernoulli random variables [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]. Suppose that X is a random variable with law the binomial law B(n, p). We have

Tchebytcheff exponential inequality. Let X 1 , . . . , X n be i.i.d. random variables with common law µ. Let Λ be the Log-Laplace of µ, defined by We suppose that µ is integrable and we denote by m its mean, i.e., m = R x dµ(x). We have then