3 0 Non-triviality of a discrete Bak-Sneppen 0 2 n evolution model a J 4 2 Ronald Meester∗and Dmitri Znamenski∗ ] n n February 6, 2008 - s i d . t a m Abstract - d n Considerthefollowing evolution model, proposedin[3]byBak andSneppen. PutN vertices o c [ on a circle, spaced evenly. Each vertex represents a certain species. We associate with each 1 vertex a random variable, representing the ‘state’ or ‘fitness’ of the species, with values in [0,1]. v 0 The dynamics proceeds as follows. Every discrete time step, we choose the vertex with minimal 8 4 fitness, and assign to this vertex, and to its two neighbours, three new independent fitnesses 1 0 with a uniform distribution on [0,1]. A conjecture of physicists, based on simulations, is that 3 0 in the stationary regime, the one-dimensional marginal distributions of the fitnesses converges, / t a when N → ∞, to a uniform distribution on (f,1), for some threshold f < 1. m - In this paper we consider a discrete version of this model, proposed in [2]. In this discrete d n version,thefitnessofavertexcanbeeither0or1. Thesystemevolves accordingtothefollowing o c rules. Each discrete time step, we choose an arbitrary vertex with fitness 0. If all the vertices : v have fitness 1, then we choose an arbitrary vertex with fitness 1. Then we update the fitnesses i X r of this vertex and of its two neighbours by three new independent fitnesses, taking value 0 with a probability 0 < q < 1, and 1 with probability p = 1−q. We show that if q is close enough to one, then the mean average fitness in the stationary regime is bounded away from 1, uniformly in the number of vertices. This is a small step in the direction of the conjecture mentioned above, and also settles a conjecture mentioned in [2]. Our proof is based on a reduction to a continuous time particle system. Key words: species, fitness, evolution, interacting particle system, self-organised criticality, coupling, contact process, stationary distribution. ∗ FacultyofExactSciences,FreeUniversityAmsterdam,deBoelelaan1081,1081HVAmsterdam,TheNetherlands; telephone +31-20-444-76-72,fax +31-444-76-53,e-mail: [email protected] A discrete Bak-Sneppen model 2 1 Introduction The Bak Sneppen model, introduced in [3], has received a lot of attention in the literature, see for instance [1], [8], [14], [4], [5], [11], [9] and [12]. In [1], it is described how Bak and Sneppen were looking for a simple mathematical model which was supposed to exhibit evolutionary behaviour, and which was also supposed to fall into the class of processes showing self-organised critical behaviour. For physicists, self-organised critical behaviour refers to power law decay of temporal and spatial quantities, without fine-tuning of parameters. After many attempts, Bak and Sneppen arrived at the following process. Think of a system with N species. These species are represented by N vertices on a circle, evenly spaced. Now each of these species is assigned a so called ‘fitness’, and in this model, the fitness is a number between 0 and 1. The higher the fitness, the better chance of surviving the species has. The dynamics of evolution is modelled as follows. Every discrete time step, we choose the vertex with minimal fitness, and we think of the corresponding species as disappearing completely. This species is then replaced by a new one, with a fresh and independent fitness, uniformly distributed on [0,1]. So far, the dynamics does not have any interaction between the species, and does not result in an interesting process. Interaction is introduced by also replacing the two neighbours of the vertex with lowest fitness by new species with independent fitnesses. This interaction represents co-evolution of related species: if a certain species becomes extinct, this has an effect on other species as well. The neighbour interaction makes the model very interesting from a mathematical point of view. It is extremely simple to run this model on a computer. Simulations then suggest the following behaviour, for large N (see [8] and [1] for simulation results). It appears that the one-dimensional marginals are uniform (in the limit for N → ∞) on (f,1) for some f whose numerical value is supposed to be close to 2/3. This threshold value f is the basis for self-organised critical behaviour, according to [3], [1] and [8]. Since in the limit there is no mass below f, one can look at so called avalanches of fitnesses below this threshold: start counting at the moment that there is one fitness below f and wait until all fitnesses are above f again. The random number of updates, for instance, counted this way, is suppose to follow a power law, and there is no fine-tuning of parameters. A discrete Bak-Sneppen model 3 It is a challenge to prove any of the above statements. Note that in order to prove power law behaviour, one should first prove the existence of the threshold f with the property that in the limit for N → ∞, all one-dimensional marginals are concentrated on (f,1). Indeed, one can define avalanches corresponding to other thresholds as well, but it is not expected that these avalanches have power law behaviour. This is only expected (and observed) for the self-organised threshold f. Therefore, this should be the starting point of a rigorous mathematical analysis of the model. Simple as the model may appear, it turns out to be very difficult to say anything at all about the limiting one-dimensional distributions. It is therefore natural to try to prove a similar result in a simpler model. In this light, we have chosen to study a discrete version of the model, which was proposed in [2], and which can be described as follows. Fitnesses of species can now only be 0 or 1. The dynamics in this simpler model proceeds as follows: at every discrete time step, we choose an arbitrary vertex with fitness 0. If there is no such vertex, then we choose an arbitrary vertex with fitness 1. We update the fitnesses of this vertex, and of its two neighbours, by three new independent fitnesses, taking value 0 with probability 0 < q < 1, and 1 with probability p = 1−q. This process is called the BS process in this paper. We show that if q is close enough to one, then the mean average fitness in the stationary regime is bounded away from 1, uniformly in the number of vertices. This is a small step in the direction of the conjecture mentioned above, and answers a question which was posed in [2]. It should be noted that this discrete version of the model does not show self-organised critical behaviour. Nevertheless, we think that understanding of the discrete model also increases our under- standing oftheoriginalmodel, if notinatechnical sense, certainlyina conceptualsense. Admittedly, the discrete version suggested here and in [2] is only one out of many possible discrete versions, but we see no reason to complicate matters unnecessarily by choosing more complicated discrete versions. The reader will notice that the proof of our main result is already quite complicated. In order to state our main result, here follows some notation. As before, the number of vertices is denoted by N, and we denote by η (n) the state of the i-th vertex after n updates of the process. N i We will prove the following result. A discrete Bak-Sneppen model 4 Theorem 1.1 If q is close enough to one, then there exists c > 0 such that for any N ∈ N and q i ∈ {1,...,N}, lim P(η (n) = 0) ≥ c . (1.1) N i q n→∞ Notethat lim P(η (n) = 0) exists, because η (n) is a finite state, irreducible and aperiodicMarkov N i N n→∞ chain. In the next section, we reduce the problem to a problem in a continuous time, monotone particle system. In this system we will be able to prove results uniformly in N, by exhibiting graphical representations and an infinite space version of the particle system. 2 Reduction to a monotone continuous time process. In this section we define a useful continuous time stochastic process ξ(t), independent of N. We construct the process ξ(t) via a graphical representation. The graphical representation GR is a random graph on the space-time diagram Z×R+. We define GR via a set of independent so called bundles {Πk}k∈Z, where each bundle Πk consists of eight independent Poisson processes on R, Π = {Π000,Π001,...,Π110,Π111}, k k k k k with parameters q3/(1−q3),q2p/(1−q3),...,p2q/(1−q3),p3/(1−q3) respectively. (We use the factor 1/(1−q3) to rescale time in a convenient way, as will become clear later.) For each process Πσ1,σ2,σ3 k we perform the following procedure. At i-th arrival τσ1,σ2,σ3 of Πσ1,σ2,σ3, i ∈ Z, we draw arrows in k,i k Z×R from (k,τσ1,σ2,σ3) to (k −1,τσ1,σ2,σ3), iff σ = 0, and from (k,τσ1,σ2,σ3) to (k +1,τσ1,σ2,σ3), iff k,i k,i 1 k,i k,i σ = 0. We draw a ∗ in Z×R at every (k+j,τσ1,σ2,σ3) with σ = 1, j = −1,0,1. We say that (x,t ) 3 k,i j 1 is connected to (x,t ) by a time segment, if t < t and there are no ∗’s on (x,t), t ∈ [t ,t ). An open 2 1 2 1 2 pathγ(t)|t2 withtrace(x ,s ),...,(x ,s )isamapfrom[t ,t ]toZsuchthatt = s < ··· < s = t , t1 0 0 n n 1 2 1 0 n 2 γ(t) = x , for t ∈ [s ,s ), 0 ≤ i < n, γ(t ) = x , and every pair (x ,s ), (x ,s ) is connected i i i+1 2 n i i i+1 i+1 either by a time segment or by an arrow. For any finite B ⊂ Z, x,y ∈ B, and t ≤ t ∈ R, write 1 2 (x,t ) (y,t ) in GR| , if there exists an open path γ(t)|t2 in GR with γ(t ) = x, γ(t ) = y, and 1 2 B t1 1 2 γ(t) ∈ B, for all t ∈ [t ,t ]. 1 2 A discrete Bak-Sneppen model 5 time t τ110 * * 2,0 τ000 -2,0 τ010 -1,0 * τ111 * * * 1,0 τ000 0,0 0 -3 -2 -1 0 1 2 Zd Figure 1: The graphical representation GR. (0,0) is connected to (−1,t) by an open path. The trace is (0,0), (0,τ00,000), (−1,τ00,000), (−1,τ−0110,0), (−2,τ−0110,0), (−2,τ−0020,0), (−1,τ−0020,0) (−1,t). For any finite A ⊆ B ⊂ Z and t,s ≥ 0 we denote by ξ(A,t)(s) the random subset of vertices x ∈ B B such that there exists y = y(x) ∈ A, and (y,t) (x,t+s) in GR| . B (A,t) The definition of ξ (s) via the existence of certain open paths implies a number of useful B properties. The first is monotonicity: ξ(A,t)(s) ⊆ ξ(C,t)(s), s ≥ 0 if A ⊆ C, B ⊆ D, (2.1) B D The second is the semigroup property: ({∅},0) (a) ξ (t) = {∅}, t ≥ 0, B (2.2) (b) ξ(ξB(A,t)(s1),t+s1)(s −s ) = ξ(A,t)(s ), if A ⊆ B,0 ≤ s ≤ s . B 2 1 B 2 1 2 The monotonicity property (2.1) allows us to define the process ξ(A,t)(s) for any A ⊆ B ⊆ Z: B (A,t) (A∩B′,t) ξ (s) = lim ξ (s). B B′ B′↑B, (2.3) B′ finite Notethatduetothemonotonicityproperty(2.1), thelimitatther.h.s.isindependent ofthesequence B′ ↑ Z. The process ξ(t) is now defined as follows: ξ(t) = ξ(Z,0)(t), t ≥ 0. (2.4) Z A discrete Bak-Sneppen model 6 We now extract the BS process η (n) from the graphical representation GR as to have η (n) N N and ξ(t) defined on the same probability space. The N vertices are labeled by Λ(N) = {−N′−1,...,N′′+1}, where N′+3+N′′ = N, N′′−1 ≤ N′ ≤ N′′, and the observation site is labeled by 0. We define l(i) and r(i) to be the left and right neighbours of i, respectively, with appropriate boundary conditions: i−1, i ∈ [−N′,N′′ +1], l(i) =  N′′ +1, i = −N′ −1,   i+1, i ∈ [−N′ −1,N′′], r(i) =  −N′ −1, i = N′′ +1.  A state of the BS process is determined by the subset of the vertices in state 0. Thus the state  space S of the BS process consists of the all subsets of Λ(N). If we denote the state of a site i in a N configuration η ∈ S by η , then we have an identity N i η = 1 i ∈/ η . (2.5) i n o This identity is natural because the 0’s play the ‘active’ role in the dynamics of BS process. It is possibly also slighty inconvenient for mathematicians, who are used to work with subsets of sites in state 1, (like in the contact process or in the 1-dim sendpile model, ect.). Indeed, for those processes we would have η = 1 i ∈ η . Nevertherless, we will not reverse the roles of 1’s and 0’s, and will i work with (2.5), becaunse of thoe conventional definition of the BS-model. Wewillnowextract fromGRtwo independent sequences ofrandomvariablesU = (U ), V = (V ), j j andthenwewilldefinetheBSprocessintermsofthosesequences. LetΠ(N)denotethesuperposition of all the Poisson processes associated to the vertices in Λ(N), i.e., with abuse of notation, Π(N) = Π000 ∪Π001 ∪···∪Π110 ∪Π111 . k k k k k∈[Λ(N)(cid:16) (cid:17) Then Π(N) is a Poisson process on R with intensity N/(1−q3). Denote by τ(N) = (τ ,τ ,...) (2.6) 1 2 A discrete Bak-Sneppen model 7 the arrivals of Π(N) after time zero. For every j ∈ N there exists, with probability one, a unique U ∈ Λ(N) and V ∈ {0,1}3 such that τ is the arrival of ΠVj. It is clear that U, V and τ(N) j j j Uj are independent and each consists of i.i.d. random variables. Note that U , j ∈ N is uniformly j distributed, that is, P(U = i) = 1/N, i ∈ Λ(N). The sequence U will be used as a sequence of j random vertices-canditates for the update procedure. The distribution of V is simply the joint j distribution of three independent Bernoulli random variables, taking value 0 with probability q and 1 with probability 1−q. The sequence V will be used to determine the states of the vertices after the updates. We will define η (n) inductively via the (random) increasing sequence (j ) ⊂ N. Let j = 0, N n 0 η (0) = ∅. Let n ∈ N, and suppose that j and η (n−1) are already defined. If η (n−1) = ∅, N n−1 N N then j = j +N +1, η (n) = {U }, i.e. we skip N elements of the sequences U and V, and then n n−1 N jn restart our process from the site U . The reason to skip N elements is that we want to have the jn following property: the more particles in state 1 we have in η (n−1), the more elements of U and N V, in mean, we skip to define η (n). We will use this property later, in the proof of Lemma 2.1. If N η (n−1) 6= ∅, we wait until we choose a vertex in state 0: N j = min j > j |U ∈ η (n−1) , n n−1 j N n o and change the state of site U and its neighbours l(U ) and r(U ) according the value of V = jn jn jn jn (σ ,σ ,σ ), i.e. 1 2 3 σ , i = l U , 1 jn  (cid:16) (cid:17) σ , i = U , η (n) =  2 jn N i    σ3, i = r Ujn , (cid:16) (cid:17) η (n−1) , otherwise.  N i     This finishes the construction of the process η (n).  N We will now introduce an ‘intermediate’ continuous time process ξR(t): N η (0), t ∈ [0,τ ), ξR(t) = N 1 N  η (n(j)), t ∈ [τ ,τ ),j ≥ 1,  N j j+1  A discrete Bak-Sneppen model 8 where (n(j)) is defined as n(j) = max n ∈ N : j ≤ j . n n o It is clear that ξR(t) is a continuous time Markov chain on S . Observe that the processes ξR and N N N η are related via a random time change. If there are many 1’s around, then we typically skip more N steps, so 1’s tend to be preserved in ξR. This intuition is articulated in the following lemma. N Lemma 2.1 We have lim P η (n) = 1 ≤ lim P ξR(t) = 1 . (2.7) N 0 N 0 n→∞ t→∞ (cid:16) (cid:17) (cid:16) (cid:17) Proof: We prove (2.7) in two steps: (a) lim P η (n) = 1 ≤ lim P η (n(j)) = 1 , N 0 N 0 n→∞ j→∞ (2.8) (cid:16) (cid:17) (cid:16) (cid:17) (b) lim P η (n(j)) = 1 = lim P ξR(t) = 1 . N 0 N 0 j→∞ t→∞ (cid:16) (cid:17) (cid:16) (cid:17) We prove (b) first. We write ∞ P(ξR(t) = 1) = P η (n(j)) = 1, and τ ≤ t < τ . N 0 N 0 j j+1 Xj=0 (cid:16) (cid:17) The random variable η (n(j)) is independent of τ and τ . Hence N 0 j j+1 P(ξR(t) = 1)− lim P η (n(j)) = 1 N 0 N 0 j→∞ (cid:12) (cid:16) (cid:17)(cid:12) (cid:12) (cid:12) ∞ (cid:12) (cid:12) = P η (n(j)) = 1 P(τ ≤ t < τ ) − lim P η (n(j)) = 1 N 0 j j+1 N 0 j→∞ (cid:12)Xj=0 n (cid:16) (cid:17) o (cid:16) (cid:17)(cid:12) (cid:12) (cid:12) (cid:12) ∞ (cid:12) ≤ P η (n(j)) = 1 − lim P η (n(j)) = 1 × N 0 N 0 j→∞ Xj=0 (cid:12)(cid:12) (cid:16) (cid:17) (cid:16) (cid:17)(cid:12) (cid:12) (cid:12) ×P(τ ≤ t < τ ) → 0, (cid:12) as t → ∞, (cid:12) j j+1 becauce τ → ∞, as j → ∞ in probability. This proves (b). j For (a), we write p = lim P η (n) = k , k N i n→∞   i∈Λ(N) X   A discrete Bak-Sneppen model 9 and q = lim P η (n(j)) = k . k N i j→∞   i∈Λ(N) X   It is then clear that N kp k P(η (n) = 1) = N 0 N k=0 X and N kq k P(η (n(j)) = 1) = . N 0 N k=0 X Now observe that when there are k < N vertices with fitness 1, the number of trials before we select a vertex with fitness 0 has a geometric distribution with parameter (N −k)/k, hence the expected number of trials is equal to N/(N −k). It follows that for k < N, N p q = N−k k k N−1 N p +(N +1)p l=0 N−l l N and similarly P (N +1)p N q = . N N−1 N p +(N +1)p l=0 N−l l N We write ak = k/N, bk = N/(N −k) forPk < N, and bN = N +1. Then N kq k P(η (n(j)) = 1) = N 0 N k=0 X N−1 k N p +(N +1)p = k=0 N N−k k N N b p P l=0 l l N a b p = k=0 k kPk. N b p P l=0 l l Now observe that for any probability vector p ,...P,p , and non-decreasing sequences 0 ≤ a ≤ ··· ≤ 0 N 0 a and 0 ≤ b ≤ ··· ≤ b , we have N 0 N N N N a p b p ≤ a b p , k k k k k k k ! ! k=0 k=0 k=0 X X X which can be proved by induction. Applying this general fact to the a ’s, b ’s and p ’s above, we find k k k that the last quotient is bounded below by N a p which is just P(η (n) = 1). (Note that here k=0 k k N 0 P A discrete Bak-Sneppen model 10 we have used the fact that we skip N choices if all vertices have fitness 1: this makes the sequence (b ) increasing.) This proves (a). k (cid:3) The next step in the proof of Theorem 1.1 is the following lemma, where we relate the process ξR(t) to the graphical representation GR. To simplify notations further we will write GR instead N N of GR|[−N′,N′′]. Lemma 2.2 For any t ,t ≥ 0, x,y ∈ [−N′,N′′], if ξR(t ) = 0 and (x,t ) (y,t ) in GR , then 1 2 N 1 x 1 2 N ξR(t ) = 0. N 2 y Proof: Let(x,t ) (y,t )inGR ,withtrace(x ,s ),...,(x ,s ),i.e. everypair(x ,s ),(x ,s ) 1 2 N 0 0 n n i i i+1 i+1 is connected either by a time segment or by an arrow. The statement will follow by induction, if we prove that x ∈ ξR(s ) implies x ∈ ξR(s ), for every 0 ≤ i ≤ n − 1. Let x ∈ ξR(s ). i N i i+1 N i+1 i N i If (x ,s ) is connected to (x ,s ) by a time segment, then there are no symbols ‘∗’ on (x ,t), i i i+1 i+1 i t ∈ [s ,s ). Hence, there are no arrivals at the time interval [s ,s ) at Πσ1,1,σ3, Πσ1,σ2,1 and i i+1 i i+1 xi xi−1 Π1,σ2,σ3, (σ ,σ ,σ ) ∈ {0,1}3. Thus, x = x ∈ ξR(s ), because only the above arrivals can delete xi+1 1 2 3 i+1 i N i+1 x from ξR(s ). If x = x +1 and (x ,s ) is connected to (x ,s ) by an arrow, then there is an i N i+1 i+1 i i i i+1 i+1 arrival at Πσ1,σ2,0, for some σ ,σ ∈ {0,1} at time s = s , and hence, x ∈ ξR(s ). Similary, if xi 1 2 i i+1 i+1 N i+1 x = x −1 and (x ,s ) is connected to (x ,s ) by an arrow, then there is an arrival at Π0,σ2,σ3, i+1 i i i i+1 i+1 xi for some σ ,σ ∈ {0,1} at time s = s , and again, x ∈ ξR(s ). 2 3 i i+1 i+1 N i+1 (cid:3) The last two lemmas imply that we have reduced the problem to GR. Therefore, in the next section, we work in this graphical representation. 3 Proof of Theorem 1.1 (A,t) Tosimplify our notationξ (s), wewillskip theupper index (A,t), if A = B andt = 0. Wewill also B skip the lower index B, if B = Z. So for example, we will write ξ(A,t)(s) instead of ξ(A,t)(s), ξ (t) Z [x,∞)