BZPEER

preprint2024arXiv

Survival of the flattest in the quasispecies model

Viruses present an amazing genetic variability. An ensemble of infecting viruses, also called a viral quasispecies, is a cloud of mutants centered around a specific genotype. The simplest model of evolution, whose equilibrium state is described by the quasispecies equation, is the Moran--Kingman model. For the sharp peak landscape, we perform several exact computations and we derive several exact formulas. We obtain also an exact formula for the quasispecies distribution, involving a series and the mean fitness. A very simple formula for the mean Hamming distance is derived, which is exact and which do not require a specific asymptotic expansion (like sending the length of the macromolecules to $\infty$ or the mutation probability to $0$ ). We try also to extend these formulas to a general fitness landscape. We obtain an equation involving the covariance of the fitness and the Hamming class number in the quasispecies distribution. With the help of these formulas, we discuss the phenomenon of the error threshold and the notion of quasispecies. We recover the limiting quasipecies distribution in the long chain regime. We go beyond the sharp peak landscape and we consider fitness landscapes having finitely many peaks and a plateau--type landscape. We finally prove rigorously within this framework the possible occurrence of the survival of the flattest, a phenomenon which has been previously discovered by Wilke, Wang, Ofria, Lenski and Adami and which has been investigated in several works.

preprint2021arXiv

Some toy models of self-organized criticality in percolation

We consider the Bernoulli percolation model in a finite box and we introduce an automatic control of the percolation probability, which is a function of the percolation configuration. For a suitable choice of this automatic control, the model is self-critical, i.e., the percolation probability converges to the critical point $p_c$ when the size of the box tends to infinity. We study here three simple examples of such models, involving the size of the largest cluster, the number of vertices connected to the boundary of the box, or the distribution of the cluster sizes.

preprint2021arXiv

The time constant for Bernoulli percolation is Lipschitz continuous strictly above $p_c$

We consider the standard model of i.i.d. first passage percolation on $\mathbb{Z}^d$ given a distribution $G$ on $[0,+\infty]$ ( $+\infty$ is allowed). When $G([0,+\infty]) < p_c(d)$ , it is known that the time constant $μ_G$ exists. We are interested in the regularity properties of the map $G\mapstoμ_G$ . We first study the specific case of distributions of the form $G_p=pδ_1+(1-p)δ_\infty$ for $p>p_c(d)$ . In this case, the travel time between two points is equal to the length of the shortest path between the two points in a bond percolation of parameter $p$ . We show that the function $p\mapsto μ_{G_p}$ is Lipschitz continuous on every interval $[p_0,1]$ , where $p_0>p_c(d)$ .

preprint2020arXiv

A probabilistic proof of Perron's theorem

We present an alternative proof of Perron's theorem, which is probabilistic in nature. It rests on the representation of the Perron eigenvector as a functional of the trajectory of an auxiliary Markov chain.

preprint2016arXiv

A Curie-Weiss model of self-organized criticality

We try to design a simple model exhibiting self-organized criticality, which is amenable to a rigorous mathematical analysis. To this end, we modify the generalized Ising Curie-Weiss model by implementing an automatic control of the inverse temperature. For a class of symmetric distributions whose density satisfies some integrability conditions, we prove that the sum $S_n$ of the random variables behaves as in the typical critical generalized Ising Curie-Weiss model. The fluctuations are of order $n^{3/4}$ , and the limiting law is $C\exp(-λx^4)\,dx$ where $C$ and $λ$ are suitable positive constants.

preprint2016arXiv

Quasispecies on class-dependent fitness landscapes

We study Eigen's quasispecies model in the asymptotic regime where the length of the genotypes goes to infinity and the mutation probability goes to 0. We give several explicit formulas for the stationary solutions of the limiting system of differential equations.

preprint2016arXiv

The quasispecies distribution

The quasispecies model was introduced in 1971 by Manfred Eigen to discuss the first stages of life on Earth. It provides an appealing mathematical framework to study the evolution of populations in biology, for instance viruses. We present briefly the model and we focus on its stationary solutions. These formulae have a surprisingly rich combinatorial structure, involving for instance the Eulerian and Stirling numbers, as well as the up--down coefficients of permutations.

preprint2015arXiv

A lower bound on the two-arms exponent for critical percolation on the lattice

We consider the standard site percolation model on the $d$ -dimensional lattice. A direct consequence of the proof of the uniqueness of the infinite cluster of Aizenman, Kesten and Newman [Comm. Math. Phys. 111 (1987) 505-531] is that the two-arms exponent is larger than or equal to $1/2$ . We improve slightly this lower bound in any dimension $d\geq2$ . Next, starting only with the hypothesis that $θ(p)>0$ , without using the slab technology, we derive a quantitative estimate establishing long-range order in a finite box.

preprint2015arXiv

Critical population and error threshold on the sharp peak landscape for the Wright-Fisher model

We pursue the task of developing a finite population counterpart to Eigen's model. We consider the classical Wright-Fisher model describing the evolution of a population of size $m$ of chromosomes of length $\ell$ over an alphabet of cardinality $κ$ . The mutation probability per locus is $q$ . The replication rate is $σ>1$ for the master sequence and $1$ for the other sequences. We study the equilibrium distribution of the process in the regime where $\ell\to+\infty$ , $m\to+\infty$ , $q\to0$ , $\ell q\to a\in\,]0,+\infty[$ , $\frac{m}{\ell}\toα\in [0,+\infty]$ . We obtain an equation $αψ(a)=\lnκ$ in the parameter space $(a,α)$ separating the regime where the equilibrium population is totally random from the regime where a quasispecies is formed. We observe the existence of a critical population size necessary for a quasispecies to emerge, and we recover the finite population counterpart of the error threshold. The result is the twin brother of the corresponding result for the Moran model. The proof is more complex, and it relies on the Freidlin-Wentzell theory of random perturbations of dynamical systems.

preprint2015arXiv

The quasispecies regime for the simple genetic algorithm with roulette-wheel selection

We introduce a new parameter to discuss the behavior of a genetic algorithm. This parameter is the mean number of exact copies of the best fit chromosomes from one generation to the next. We argue that the genetic algorithm should operate efficiently when this parameter is slightly larger than $1$ . We consider the case of the simple genetic algorithm with the roulette--wheel selection mechanism. We denote by $\ell$ the length of the chromosomes, by $m$ the population size, by $p_C$ the crossover probability and by $p_M$ the mutation probability. We start the genetic algorithm with an initial population whose maximal fitness is equal to $f_0^*$ and whose mean fitness is equal to ${\overline{f_0}}$ . We show that, in the limit of large populations, the dynamics of the genetic algorithm depends in a critical way on the parameter $π\,=\,\big({f_0^*}/{\overline{f_0}}\big) (1-p_C)(1-p_M)^\ell\,.$ Our results suggest that the mutation and crossover probabilities should be tuned so that, at each generation, $\text{maximal fitness} \times (1-p_C) (1-p_M)^\ell > \text{mean fitness}$ .

preprint2014arXiv

A Lower Bound on the Relative Entropy with Respect to a Symmetric Probability

Let $ρ$ and $μ$ be two probability measures on $\mathbb{R}$ which are not the Dirac mass at $0$ . We denote by $H(μ|ρ)$ the relative entropy of $μ$ with respect to $ρ$ . We prove that, if $ρ$ is symmetric and $μ$ has a finite first moment, then $H(μ|ρ)\geq \frac{\displaystyle{(\int_{\mathbb{R}}z\,dμ(z))^2}}{\displaystyle{2\int_{\mathbb{R}}z^2\,dμ(z)}}\,,$ with equality if and only if $μ=ρ$ .

preprint2014arXiv

An Exponential Inequality for Symmetric Random Variables

We prove the following exponential inequality: Let $n\geq 1$ and let $X_1,...,X_n$ be $n$ independent identically distributed symmetric real-valued random variables. For any $x,y>0$ , we have $\mathbb{P}\big({X_1+...+X_n}\geq x,\, {X_1^2+...+X_n^2}\leq y\big)< \exp(-\frac{x^2}{2y})\,.$

preprint2014arXiv

Maximal stream and minimal cutset for first passage percolation through a domain of $\mathbb{R}^d$

We consider the standard first passage percolation model in the rescaled graph $\mathbb{Z}^d/n$ for $d\geq2$ and a domain $Ω$ of boundary $Γ$ in $\mathbb{R}^d$ . Let $Γ^1$ and $Γ^2$ be two disjoint open subsets of $Γ$ , representing the parts of $Γ$ through which some water can enter and escape from $Ω$ . A law of large numbers for the maximal flow from $Γ^1$ to $Γ^2$ in $Ω$ is already known. In this paper we investigate the asymptotic behavior of a maximal stream and a minimal cutset. A maximal stream is a vector measure $\vecμ_n^{\max}$ that describes how the maximal amount of fluid can cross $Ω$ . Under conditions on the regularity of the domain and on the law of the capacities of the edges, we prove that the sequence $(\vecμ_n^{\max})_{n\geq1}$ converges a.s. to the set of the solutions of a continuous deterministic problem of maximal stream in an anisotropic network. A minimal cutset can been seen as the boundary of a set $E_n^{\min}$ that separates $Γ^1$ from $Γ^2$ in $Ω$ and whose random capacity is minimal. Under the same conditions, we prove that the sequence $(E_n^{\min})_{n\geq1}$ converges toward the set of the solutions of a continuous deterministic problem of minimal cutset. We deduce from this a continuous deterministic max-flow min-cut theorem and a new proof of the law of large numbers for the maximal flow. This proof is more natural than the existing one, since it relies on the study of maximal streams and minimal cutsets, which are the pertinent objects to look at.

preprint2014arXiv

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 $\ell$ the length of the chromosomes, by $m$ the population size, by $p_C$ the crossover probability and by $p_M$ the mutation probability. We introduce a parameter $σ$ , called the selection drift, 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-p_C)(1-p_M)^\ell\,.$ 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-p_C)(1-p_M)^\ell$ should be slightly larger than $1$ ; $p_M$ should be of order $1/\ell$ ; $m$ should be larger than $\ell\ln\ell$ ; the running time should be of exponential order in $m$ . The first condition requires that $\ell p_M +p_C< \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.

preprint2014arXiv

Weak shape theorem in first passage percolation with infinite passage times

We consider the model of i.i.d. first passage percolation on $\mathbb{Z}^d$ : we associate with each edge $e$ of the graph a passage time $t(e)$ taking values in $[0,+\infty]$ , such that $\mathbb{P}[t(e)<+\infty] >p_c(d)$ . Equivalently, we consider a standard (finite) i.i.d. first passage percolation model on a super-critical Bernoulli percolation performed independently. We prove a weak shape theorem without any moment assumption. We also prove that the corresponding time constant is positive if and only if $\mathbb{P}[t(e)=0]<p_c(d)$ .

preprint2013arXiv

Nucleation and growth for the Ising model in $d$ dimensions at very low temperatures

This work extends to dimension $d\geq3$ the main result of Dehghanpour and Schonmann. We consider the stochastic Ising model on ${\mathbb{Z}}^d$ evolving with the Metropolis dynamics under a fixed small positive magnetic field $h$ starting from the minus phase. When the inverse temperature $β$ goes to $\infty$ , the relaxation time of the system, defined as the time when the plus phase has invaded the origin, behaves like $\exp({βκ_d})$ . The value $κ_d$ is equal to $κ_d=\frac{1}{d+1}(Γ_1+\cdots+Γ_d),$ where $Γ_i$ is the energy of the $i$ -dimensional critical droplet of the Ising model at zero temperature and magnetic field $h$ .

preprint2013arXiv

The travel time in a finite box in supercritical Bernoulli percolation

We consider the standard site percolation model on the three dimensional cubic lattice. Starting solely with the hypothesis that $θ(p)>0$ , we prove that, for any $α>0$ , there exists $κ>0$ such that, with probability larger than $1-1/n^α$ , every pair of vertices inside the box $Λ(n)$ are joined by a path having at most $κ(\ln n)^2$ closed sites.

preprint2012arXiv

Critical population and error threshold on the sharp peak landscape for a Moran model

The goal of this work is to propose a finite population counterpart to Eigen's model, which incorporates stochastic effects. We consider a Moran model describing the evolution of a population of size $m$ of chromosomes of length $\ell$ over an alphabet of cardinality $κ$ . The mutation probability per locus is $q$ . We deal only with the sharp peak landscape: the replication rate is $σ>1$ for the master sequence and 1 for the other sequences. We study the equilibrium distribution of the process in the regime where $\ell, m\to +\infty$ , $q\to 0$ , $\ell q \to a$ , $m/\ell\toα$ . We obtain an equation $αϕ(a)=\lnκ$ in the parameter space $(a,α)$ separating the regime where the equilibrium population is totally random from the regime where a quasispecies is formed. We observe the existence of a critical population size necessary for a quasispecies to emerge and we recover the finite population counterpart of the error threshold. These results are supported by computer simulations.

preprint2012arXiv

Upper large deviations for the maximal flow through a domain of $\bolds{\mathbb{R}^d}$ in first passage percolation

We consider the standard first passage percolation model in the rescaled graph $\mathbb {Z}^d/n$ for $d\geq2$ and a domain $Ω$ of boundary $Γ$ in $\mathbb {R}^d$ . Let $Γ^1$ and $Γ^2$ be two disjoint open subsets of $Γ$ representing the parts of $Γ$ through which some water can enter and escape from $Ω$ . We investigate the asymptotic behavior of the flow $ϕ_n$ through a discrete version $Ω_n$ of $Ω$ between the corresponding discrete sets $Γ^1_n$ and $Γ^2_n$ . We prove that under some conditions on the regularity of the domain and on the law of the capacity of the edges, the upper large deviations of $ϕ_n/n^{d-1}$ above a certain constant are of volume order, that is, decays exponentially fast with $n^d$ . This article is part of a larger project in which the authors prove that this constant is the a.s. limit of $ϕ_n/n^{d-1}$ .

preprint2011arXiv

Cramér's theorem for asymptotically decoupled fields

We give a general setting for Cramér's large deviations theorem for the empirical means of a field of random vectors, which contains Cramér's theorem for i.i.d. random vectors and Sanov's theorem for asymptotically decoupled measures. ----- Nous établissons un cadre général pour le théorème de Cramér sur les grandes déviations des moyennes empiriques d'un champ de vecteurs aléatoires, cadre qui contient le théorème de Cramér pour des vecteurs aléatoires i.i.d. et le théorème de Sanov pour les mesures asymptotiquement découplées.

preprint2010arXiv

Critical control of a genetic algorithm

Based on speculations coming from statistical mechanics and the conjectured existence of critical states, I propose a simple heuristic in order to control the mutation probability and the population size of a genetic algorithm.

Raphaël Cerf

Research overview

Is this your work?

21 publications

Survival of the flattest in the quasispecies model

Some toy models of self-organized criticality in percolation

The time constant for Bernoulli percolation is Lipschitz continuous strictly above $p_c$

A probabilistic proof of Perron's theorem

A Curie-Weiss model of self-organized criticality

Quasispecies on class-dependent fitness landscapes

The quasispecies distribution

A lower bound on the two-arms exponent for critical percolation on the lattice

Critical population and error threshold on the sharp peak landscape for the Wright-Fisher model

The quasispecies regime for the simple genetic algorithm with roulette-wheel selection

A Lower Bound on the Relative Entropy with Respect to a Symmetric Probability

An Exponential Inequality for Symmetric Random Variables

Maximal stream and minimal cutset for first passage percolation through a domain of $\mathbb{R}^d$

The quasispecies regime for the simple genetic algorithm with ranking selection

Weak shape theorem in first passage percolation with infinite passage times

Nucleation and growth for the Ising model in $d$ dimensions at very low temperatures

The travel time in a finite box in supercritical Bernoulli percolation

Critical population and error threshold on the sharp peak landscape for a Moran model

Upper large deviations for the maximal flow through a domain of $\bolds{\mathbb{R}^d}$ in first passage percolation

Cramér's theorem for asymptotically decoupled fields

Critical control of a genetic algorithm

See the researcher in context

Building this map preview

Raphaël Cerf

Research overview

Is this your work?

21 publications

Survival of the flattest in the quasispecies model

Some toy models of self-organized criticality in percolation

The time constant for Bernoulli percolation is Lipschitz continuous strictly above pcp_cpc​

A probabilistic proof of Perron's theorem

A Curie-Weiss model of self-organized criticality

Quasispecies on class-dependent fitness landscapes

The quasispecies distribution

A lower bound on the two-arms exponent for critical percolation on the lattice

Critical population and error threshold on the sharp peak landscape for the Wright-Fisher model

The quasispecies regime for the simple genetic algorithm with roulette-wheel selection

A Lower Bound on the Relative Entropy with Respect to a Symmetric Probability

An Exponential Inequality for Symmetric Random Variables

Maximal stream and minimal cutset for first passage percolation through a domain of Rd\mathbb{R}^dRd

The quasispecies regime for the simple genetic algorithm with ranking selection

Weak shape theorem in first passage percolation with infinite passage times

Nucleation and growth for the Ising model in ddd dimensions at very low temperatures

The travel time in a finite box in supercritical Bernoulli percolation

Critical population and error threshold on the sharp peak landscape for a Moran model

Upper large deviations for the maximal flow through a domain of $\bolds{\mathbb{R}^d}$ in first passage percolation

Cramér's theorem for asymptotically decoupled fields

Critical control of a genetic algorithm

See the researcher in context

Building this map preview

The time constant for Bernoulli percolation is Lipschitz continuous strictly above $p_c$

Maximal stream and minimal cutset for first passage percolation through a domain of $\mathbb{R}^d$

Nucleation and growth for the Ising model in $d$ dimensions at very low temperatures