J Stat Phys (2012) 149:964–968 DOI 10.1007/s10955-012-0627-2

Rigorous Self-organised Criticality in the Modified Bak-Sneppen Model Ronald Meester · Anish Sarkar

Received: 7 March 2012 / Accepted: 22 October 2012 / Published online: 7 November 2012 © Springer Science+Business Media New York 2012

Abstract We prove that a modified version of the Bak-Sneppen model obeys power law behaviour for avalanche duration and size. We do this through a coupling with a suitable branching process which is known to have power law behaviour at criticality. Keywords Bak-Sneppen model · Self-organised criticality · Avalanche · Power law 1 Introduction and Main Result The standard Bak-Sneppen model [1] is defined as follows. Consider a system with N species. These species are represented by N vertices on a circle, evenly spaced, say. Each of the species is assigned a so called fitness, a number between 0 and 1. The dynamics of evolution is modeled 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 after each step, the system has N vertices arranged on the circle, each vertex corresponding to a certain fitness. So far, the dynamics does not have any interaction between the species, and does not result in an interesting process. Indeed, if we only replace the species with the lowest fitness, then it is easy to see that the system converges to a situation with all fitnesses equal to 1. 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. This neighbour interaction makes the model very interesting from a mathematical point of view. Simulations (see e.g. [6] and [1]) suggest the following behaviour. In the limit for N → ∞, it appears that the distribution of the fitnesses are independent and uniformly R. Meester () Department of Mathematics, VU Universiteit Amsterdam, Amsterdam, The Netherlands e-mail: [email protected] A. Sarkar Indian Statistical Institute, 7, S. J. S. Sansanwal Marg, New Delhi 110016, India

Rigorous Self-organised Criticality

965

Fig. 1 A snapshot of the Bak-Sneppen model in stationarity

distributed on (f, 1) for some f whose numerical value is supposed to be close to 2/3. (See [8] for a rigorous conditional statement about this.) We refer to Fig. 1 for a snapshot of the fitnesses in the Bak-Sneppen model in stationarity. This threshold value f is the basis for self-organised critical behaviour, according to [1, 2] and [6], as follows. One can look at so called avalanches of fitnesses below this threshold: start counting at a moment that all fitnesses, except one, are above f and finish the counting at the first next moment when all fitnesses are above f . The random number of updates in an avalanche and the number of vertices involved in such an avalanche are both supposed to follow a power law. This is in accordance with the paradigm of self-organised criticality: power law behaviour of various spatial and temporal quantities without any tuning of parameters. As a result, the Bak-Sneppen model has been widely referred to as an archetype model exhibiting self-organised criticality. Progress on rigorous understanding of the stationary distribution of the process was made in [8] and [7], but the suggested power law behaviour of avalanches has not been addressed rigorously so far. In this note we want to point out that power law behaviour of avalanches can be rigorously demonstrated in a modified version of the Bak-Sneppen model. This modification is defined as follows. Consider N particles, each with a fitness, a number between 0 and 1. The dynamics of the process is as follows. At each discrete time step, the particle with the lowest fitness is chosen, together with one other particle, chosen uniformly at random among all remaining particles. (The restriction to update only one extra particle is rather arbitrary. The proof below—suitably reformulated—goes through for multiple choices as well.) The fitnesses of both chosen particles are replaced by new fitnesses, according to independent uniform random variables on (0, 1). We define (the duration of) an avalanche at level t ∈ (0, 1), also referred to as a t avalanche, as follows. Consider an initial configuration of fitnesses in which one particle has fitness 0 and all other particles have fitnesses strictly larger than t . Let AN t denote the

966

R. Meester, A. Sarkar

first time at which all fitnesses are strictly larger than t . The random variable AN t is the duration of a typical avalanche at level t . The number of particles updated in such an avalanche is called the size of an avalanche, and the corresponding random variable is denoted StN . Theorem 1.1 In the modified Bak-Sneppen model, the following hold. (a) For t < 12 , we have for all N ,

  −c1 (t)k P AN , t ≥k ≤e

for some positive constant c1 (t) independent of N . (b) For t > 12 and all k, we have   lim P AN t ≥ k ≥ c2 (t), N→∞

for some positive constant c2 (t). (c) For t = 12 , we have lim lim

k→∞ N→∞

√  N  √ kP At ≥ k = 2/ π.

N The statements in (a)–(c) remain valid when we replace AN t with St .

We prove this result (through a coupling with a suitable branching process) in the next section, but before doing that, we offer a brief discussion. Theorem 1.1 explains why in the modified Bak-Sneppen model, we observe power law behaviour of avalanche duration and size. Indeed, since avalanches at thresholds smaller than 1/2 are exponentially short, the system (of size N for N large) will quickly evolve into a state in which the much slower (power-law) avalanche at threshold 1/2 is dominant. It should be noted that the modified Bak-Sneppen model cannot be defined on infinitely many vertices and hence the only way to formulate power law behaviour, is through the limit N → ∞ as in the theorem. The result, of course, does not show that the original Bak-Sneppen model obeys power laws, but at least it shows that the principle is sound in a rigorous way. Indeed, this is precisely the main contribution of this paper: it is true that a rigorous proof of power law behaviour in the original Bak-Sneppen model is currently beyond reach, but Theorem 1.1 shows that the phenomenon first observed by Bak and Sneppen can be rigorously made sense of in a modified version of the model. We remark that in the literature, some rigorous results are available in related models for evolution of species, for instance [4] and [3]. Besides the fact that their model is quite different, they do not address the problem of power law behaviour of avalanches.

2 Proof of Theorem 1.1 To prove (a), we will couple a t -avalanche in the modified Bak-Sneppen process with an ordinary Galton-Watson branching process. To this end, we first give a precise description of an avalanche which enables us to couple it to a branching process. We have labeled the vertices with numbers 1, . . . , N . The fitness of vertex i is denoted i , hence the state of the process at any time is given by the vector of fitnesses (1 , . . . , N ). We denote by Am the collection of vertices whose fitness at time m (that is, after m steps of the process) is at most t , and we call Am the active vertices at time m. By definition, A0 = {1},

Rigorous Self-organised Criticality

967

since we start the process with all fitnesses equal to 1, except the fitness of vertex 1 which we set to 0. In a recursive fashion, let Am = {x1 , x2 , . . . , xn } be the active vertices at time m. Let i be the index of the particle such that xi is minimal among x1 , . . . , xn (with an arbitrary decision rule in case of ties) and let y be a random vertex in {1, 2, . . . , N } \ {xi }. Both xi and y now receive a new fitness, independently of everything else and uniformly [0, 1] distributed. We obtain Am+1 from Am as follows: if the new fitness of xi is at most t , then / Am+1 . For y, we xi ∈ Am+1 with the new fitness. If the new fitness is larger than t then xi ∈ act similarly: if y ∈ / Am then y ∈ Am+1 if and only if its fitness is at most t . If y ∈ Am then if its new fitness is at most t , y ∈ Am+1 , with the new fitness. If the new fitness is larger than t then y ∈ / Am+1 . We can, alternatively, describe the above dynamics in terms of a suitable Galton-Watson branching process as follows. We start the process with an initial particle labeled (1, 0), the first entry referring to the label of the vertex (1), and the second entry corresponding to its fitness (0). We recursively define the dynamics of the branching process as follows. Suppose after m steps of the process, we have a finite rooted tree such that each leaf of the tree has a label (xi , xi ) where the xi ’s are all different and elements of {1, 2, . . . , N } and all xi ∈ [0, t]. We call the collection of vertices xi at the leaves the set of active vertices. We now choose the leaf with the smallest xi , say (x1 , x1 ), and we let y be a random uniform choice from {1, 2, . . . , N } \ {x1 }. This leaf (x1 , x1 ) initially begets two children with labels (x1 , U ) and (y, V ) respectively, where U and V are independent uniform (0, 1) random variables. The child (x1 , U ) is discarded if U > t and retained otherwise. For the child (y, V ) we act as follows: if the vertex y was not already active, the leaf (y, V ) is attached to (x1 , x1 ) if and only if V ≤ t . If y was already active, we discard the existing leaf having index label y and a new leaf (y, V ) is attached to (x1 , x1 ) if and only if V ≤ t . Without the discarding of repeated leaves, the process described in the previous paragraph is an ordinary Galton-Watson branching process, the only difference being that generations are not built up in the usual order, but rather in an order dictated by the fitnesses. It is clear from the description that the sequence of sets of active vertices in the modified Bak-Sneppen model and in the process with discarding of repeated leaves have the same distribution. Furthermore, the process with discarding of repeated leaves, described above, is clearly dominated stochastically by an ordinary branching process with binomial offspring distribution with parameters 2 and t . In particular, the duration of a t -avalanche is dominated by the total progeny of this Galton-Watson branching process. Writing |LGW | for the total progeny of a branching process with binomial offspring distribution with parameters 2 and t , it is well known that when t < 1/2, the process is subcritical and    (1) P LGW  ≥ k ≤ e−ck , for some constant c = c(t) > 0. Statement (a) in Theorem 1.1 now follows immediately. In order to prove (c), we use the same branching process as above, but this time a simple domination argument does not suffice. We claim that for t = 1/2, √    √ (2) lim kP LGW  ≥ k = 2/ π. k→∞

Indeed, if the probability generating function of |LGW | is given by F√, then we clearly have F (s) = s(1/2 + F (s)/2)2 . Solving, we find F (s) = [(2 − s) − 2 1 − s]/s. A classical computation shows that the generating function of the sequence {P (|LGW | > k) : k ≥ 0} is now given by (1 − F (s))/(1 − s) = 2[−1 + (1 − s)−1/2 ]/s. Taking the coefficient of s k and

968

R. Meester, A. Sarkar

using Stirling’s formula, we obtain (2). (A related computation for P (|LGW | = k) can be found in Theorem 13.1 in [5].) We need to show that the distributions of |LGW | and AN 1/2 are close to each other for large N . To this end, we observe that if the randomly chosen vertex y was not already active, the number of children of any vertex is just binomially distributed with parameters 2 and 1/2. Hence, as long as we never choose a vertex which has already been active in the past, the process with discarding of repeated leaves is just an ordinary critical Galton-Watson branching process. For fixed k, it is clear that when N → ∞, the probability of the event that in the first k steps of the process, we never choose a vertex y which has been active before, tends to 1. GW | is due to the discarding of repeated Since the only difference between AN 1/2 and |L leaves, it suffices to prove that for fixed k, the probability that anything has been discarded in the first k steps of the process, tends to 0 as N → ∞. Hence, the probability that the process with discarding of repeated leaves is identical to the full branching process through the first k steps of the process, tends to 1 as N → ∞, and (c) follows from (2). To prove (b), note that for t > 1/2, the full branching process has positive probability to survive forever. As in the previous case for t = 1/2, the probability that no discarding is necessary in the first k steps of the process tends to 1 as N → ∞. Hence the probability that AN t > k converges, as N → ∞, to the probability that the full branching process survives at least k steps, and this probability is positive as long as t > 1/2. N Finally, since StN ≤ AN t , the corresponding statement in (a) for St follows immediately. N replaced by S note that if we never choose a For the statements in (b) and (c) with AN t t vertex twice, the range and duration are the same. Since this happens, when N → ∞, with probability approaching 1, the final claim of the theorem follows. 

References 1. Bak, P.: How Nature Works. Springer, Berlin (1996) 2. Bak, P., Sneppen, K.: Punctuated equilibrium and criticality in a simple model of evolution. Phys. Rev. Lett. 74, 4083 (1993) 3. Ben-Ari, I., Matzavinos, A., Roitershtein, A.: On a species survival model. Electron. Commun. Probab. 16, 226–233 (2011) 4. Guiol, H., Machado, F.P., Schinazi, R.B.: A stochastic model of evolution. Markov Process. Relat. Fields 17, 253–258 (2011) 5. Harris, T.E.: The Theory of Branching Processes. Springer, Berlin (1963) 6. Jensen, H.J.: In: Self-organized Criticality. Cambridge Lecture Notes in Physics (1998) 7. Meester, R., Znamenski, D.: Limit behavior of the Bak-Sneppen evolution model. Ann. Probab. 31, 1986– 2002 (2003) 8. Meester, R., Znamenski, D.: Critical thresholds and the limit distribution in the Bak-Sneppen evolution model. Commun. Math. Phys. 246, 63–86 (2004)