{'fraction_non_alphanumeric': 0.056613484302624806, 'fraction_numerical': 0.02110138960370561, 'mean_word_length': 3.767720828789531, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The survival probability of a branching random walk in presence of an absorbing wall

A branching random walk in presence of an absorbing wall moving at a constant velocity v undergoes a phase transition as v varies. The problem can be analyzed using the properties of the Fisher-Kolmogorov-Petrovsky-Piscounov (F-KPP) equation. We find that the survival probability of the branching random walk vanishes at a critical velocity v_c of the wall with an essential singularity and we characterize the divergences of the relaxation times for vv_c. At v=v_c the survival probability decays like a stretched exponential. Using the F-KPP equation, one can also calculate the distribution of the population size at time t conditionned by the survival of one individual at a later time T>t. Our numerical results indicate that the size of the population diverges like the exponential of (v_c-v)^{-1/2} in the quasi-stationary regime below v_c. Moreover for v>v_c, our data indicate that there is no quasi-stationary regime.

There has been a long-standing interest in problems of non-equilibrium critical phenomena and phase transition into absorbing states [1,2] (directed percolation or contact processes [3,4], reaction diffusion problems [5,6]). The goal of the present letter is to analyse one such problem, which has been already considered by several authors in the mathematical literature [8,9,10] : a branching random walk in presence of an absorbing moving wall at a constant velocity v. For such a problem, there is an obvious absorbing state (all the particles are absorbed by the wall) and in this letter we analyse the critical behaviour of the survival probability as the velocity v of the wall varies. Our approach is based on an analysis of the Fisher-Kolmogorov-Petrovsky-Piscounov (F-KPP) equation [11,12,13,14,15,16,17] which is known to be related to branching random walks [10,18]. We also show that the F-KPP equation allows us to calculate the properties of the quasi-stationary regime.
In absence of an absorbing wall, a one dimensional branching random walk has a number of descendants which grows exponentially with time and these descendants occupy a region which spreads [10,18] in space at a known velocity v c (which can be calculated from the knowledge of the branching and hopping rates of the walk). In presence of an absorbing wall moving at a constant velocity v, there is a competition between this exponential growth of the number of descendants and the absorption by the wall. One quantity of interest is the survival probability Q(x, t), for a particle starting at t = 0 at distance x from the wall, to have at least one surviving descendant at time t. If v > v c (i.e. if the wall moves faster than the spreading velocity of the population in absence of the wall), Q(x, t) → 0 as t → ∞. In this letter we study the phase transition which takes place at v = v c when v varies [8]. We will show that for v < v c , the survival probability Q(x, t) has a non-zero long time limit which vanishes with an essential singularity as v → v c . We will also show that the characteristic time scale τ (on which Q(x, t) converges exponentially to Q(x, ∞)) diverges like |v − v c | − 3 2 below v c and like |v − v c | −1 above v c . At v = v c , Q(x, t) decays like a stretched exponential as already proved by Kesten [7].
Our motivation for the problem in presence of a moving absorbing wall comes from the interest for simple models of evolution [19,20] proposed recently to study the in vitro evolution of a population of DNA molecules selected according to their ability to bind to some target proteins [21]. In these models, the position of an individual represents its adequacy to the environment (or fitness or ability to bind), meaning that when selection acts, the individuals with lowest x are eliminated first. The branching random walk has the effect of modeling the growth of the population and the mutations through diffusion along the fitness axis. In the models studied in [22,23,24], the size of the population is kept fixed : selection means that whenever new individuals appear in the population, the ones with lowest x are eliminated in order to keep the size of the population constant. Here the role of the wall moving at constant velocity is also to eliminate the less fitted individuals. Thus the size of the population can vary and even vanish. Besides, the models of evolution studied in [19,20] have a broader interest in physics as they are also related to models that appear in the theory of disordered systems [25], in reaction-diffusion problems [26,27] or in particle physics [28,29,30].
In the first part of this letter, we consider a continuous branching random walk in presence of a wall moving at constant velocity v (for the simulations below we will use a discrete space-time version to facilitate the programming). The diffusion is described as follows : during dt, the position of an individual is shifted by an amount η √ dt where η is a random variable of zero mean and of variance 2. For an initial individual at distance x > 0 from the wall at t = 0, one defines the survival probability Q(x, t) that at least one of its descendants is still living at t (i.e. 1 − Q(x, t) is the probability that all the descendance of the individual initially at position x ahead of the wall has been absorbed by the wall). To write the evolution of the probability Q(x, t), it is convenient to decompose the time interval [0, t + dt] into the first time interval dt and a remaining time interval [dt, t + dt]. During the first interval dt, while the wall moves by vdt, the single particle initially at position x diffuses and can branch with probability βdt into two particles, as expressed by the two terms of the following equation : which becomes by taking the limit dt → 0 with the boundary conditions Q(0, t) = 0 and Q(x, 0) = 1. It is important to notice that (2) is exact. The origin of the term Q(x, t) 2 is that after a branching event, the two offspring have independent evolutions and therefore their survival probabilities are uncorrelated.
All the x and t dependence of Q(x, t) can be extracted from the analysis of (2) which is, up to the boundary conditions, the Fisher-KPP equation [11,12] in a moving frame at velocity v.
Q(x, t) is obviously a monotonic function (increasing with x and decreasing with t : it increases if one starts further from the wall and it can only decrease with time). Therefore its t → ∞ limit Q * (x) exists and satisfies which is the usual equation for the shape of a front solution of the F-KPP equation moving at velocity v on the infinite line [16].
On the infinite line [16], for every velocity v, there is (up to a translation) a solution Q v (x) of (3) such that The relation between the decay of Q v (x) as x → −∞ and the velocity is easy to obtain: one assumes that Q v (x) ∼ e γx in the region where Q v (x) ≪ 1 and one gets from (3) that The monotonic decay for v > v c or the damped oscillations v < v c are simply due to the fact that the solutions γ of the equation v(γ) = v are real or complex conjugate γ = γ R ± iγ I . It is also known that, at v = v c , the asymptotic decay has the form where x 0 is arbitrary and With the boundary condition Q * (0) = 0 the solution of (3) is obviously Q * (x) = 0 for v > v c as the wall moves faster than the spreading velocity v c of the population. On the other hand, for v < v c , the solution is the rightmost positive arch of the solution on the infinite line. As v approaches v c , the region where Q * is small and where the quadratic term in (3) can be neglected becomes larger and larger. For 0 < v c − v ≪ 1 the solution Q * can be decomposed into two parts: a region x > L where Q * (x) is of order 1 and resembles the solution Q vc (x) on the infinite line for v = v c (whose asymptotics decay is (5)) and a region 0 < x < L where Q * (x) is small and of the form Q * (x) = C sin(γ I x)e γRx . To match the asymptotic decay of (5) near x = L, one should take This implies that as v → v − c , the survival probability vanishes with an essential singularity One can remark that a shape of Q * (x) made up of two parts is almost exactly the same as the shape of a moving front on the infinite line, in presence of a cut-off [17].
To obtain the long time dependence of Q(x, t) we assume that one can still decompose Q(x, t) into two parts : (this assumption will be tested in the figure 3 below) and a region x > L t where Q(x, t) is not small and resembles (5). One can check that (8) is indeed solution of (3) in the range 0 < x < L t to leading non-vanishing order in As one expects (at least for v < v c ) that L t /L ∼ L t (v c − v) 1/2 → 0 as t → 0, this determines L t and one gets that where the function F (z) satisfies ∂ z F = −1 + F −2 whose solution (given that F (0) = 0) is For large z, one gets F ≃ 1 − 2e −2z−2 . Therefore (10) implies that for v → v − c the convergence time τ of the exponential decay of Q(x, t) towards the fixed profile Q * (x) is For small z, one can expand the solution of (11) F (z) = (3z) 1/3 − 3z/5 + O(z 5/3 ). This leads to L t ≃ (3π 2 /γ c ) 1/3 t 1/3 +O((v−v c )t) and therefore to a stretched exponential decay of Q( At any finite t, one can notice (10,11) that L t can be expanded in powers of v − v c and one can get the whole time dependence for v > v c by an analytic continuation of the case v < v c . In particular, the scaling function F which replaces (10) for v − v c > 0 is related analytically to the function F obtained for v − v c < 0 and (10,11) are replaced by : Clearly F (z) = z + π/2 − 1/z + O(1/z 2 ) for large z. Thus for 0 < v − v c ≪ 1 and (v − v c ) 3/2 t ≫ 1, one has L t ≃ (v − v c )t and for fixed x : Both (13) and (15) agree with earlier results by Kesten [7] and Harris and Harris [8].
To study numerically the time evolution of the survival probability Q(x, t), it is more convenient to use a discrete space time version of the problem. Here we consider the case where x takes only integer values. At every time step, t → t + 1, each individual has k offspring and each offspring has a probability p y of being produced at position x + y. Then the time evolution of Q(x, t) which generalizes (2) is given by (16) and by looking at the region where Q(x, t) ∼ e γx is small, the expression (4) of the velocity v(γ) becomes v(γ) = 1 γ log k y p y e γy .
As before, the spreading velocity v c of the population in absence of the wall is v c = min γ v(γ). In this case one can generalize the above calculations to an arbitrary v(γ) and the results (7,12,13,15) are replaced by the expression of table I. To facilitate the analysis and avoid periodic or aperiodic dependence due to the commensurability of v we decided to fix v = 1 for the velocity of the wall and to vary v c by changing the p y . In all the figures below, we show the case where p 2 = 1/18 + δ, p 1 = 1/18, p 0 = 16/18 − δ. Then by varying δ we can vary v c and therefore the difference v c − v (which vanishes for δ = 0). More precisely, for small v c − v, one has the first-order relation δ ≃ 15(v c − v)/(2 ln 4) in the present case.
In figure 3 we test our assumption (8). For an initial individual at x = 1, i.e. for Q(x, 0) = δ x,1 , we computed Q(x, t) by iterating (16). We plot Q(x, t)e −γ(x−Lt) /L t which according to (8) should depend on x/L t only. In figure 2, we compare the values of Q(1, t) obtained by iterating (16) with the theoretical predictions (8,10). The agreement is excellent.
At t = ∞, the size of the population is either zero (with probability 1 if v ≥ v c and 1 − Q(x, ∞) if v < v c ) or infinite. At large but finite final time T , there are however events corresponding, for example, to having exactly one survivor. One can then try to understand which strategy leads to such events. For v < v c , t ≫ 1 and T − t = t ′ ≫ 1, the system adopts a quasi-stationary regime during which its properties do not depend on the initial conditions (number and positions of the individuals at t = 0). In particular, the average population size at time t conditioned by the survival of only one individual at final time T = t + t ′ , do not depend on t as long as t ≫ 1 and t ′ ≫ 1.
We are now going to sketch how the properties of this quasistationnary regime can be computed from (2) or (16). Details will be published in a future work [31]. Let us introduce the generating function : where f is an arbitrary function, N t is the size of the population at time t and x  (1), one finds that : Therefore 1 − G(x, t; f ) satisfies the F-KPP equation (2) with the boundary conditions G(x = 0, t; f ) = 1 and G(x, t = 0; f ) = e −f (x) . In the discrete space time case, a similar reasoning shows that 1 − G satisfies (16). One can also consider generating functions at two (or more) different times 0 < t < t + t ′ defined as : Like in (18), one can show that 1 − H(x, t, t ′ ; f 1 , f 2 ) as a function of x and t satisfies (1) or (16) with boundary conditions H(x = 0, t, t ′ ; f 1 , f 2 ) = 1 and H(x, 0, t ′ ; f 1 , f 2 ) = e −f1(x) G(x, t ′ ; f 2 ) which, as we have just seen, can also be determined from (1) or (16).
If one chooses f 1 = λ and f 2 = µ, then H(x, t, t ′ ; f 1 , f 2 ) = e −λNt−µN t+t ′ is the generating function of the sizes of the population at two different times. If one expands H to first order in powers of e −µ and of λ H(x, t, t ′ ; λ, µ) ≃H 00 (x, t, t ′ ) + e −µ H 10 (x, t, t ′ )+ λH 01 (x, t, t ′ ) + λe −µ H 11 (x, t, t ′ ) (20) one gets that the average size of the population N t T =t+t ′ at time t conditionned on having a single survivor left at time T = t + t ′ is given by : Numerical values obtained by iterating the equations satisfied by H 00 , H 10 , H 01 and H 11 (derived by replacing H by its expansion (20) into (16)) are shown in figure (4). By pushing further the expansion (20) in powers of λ, one can have access to higher moments of the population size N t .
In figure 4, we see that for v < v c both N t T and N 2 t T / N t 2 T become constant over a very long time interval, indicating that there is a quasi-stationary regime.
As v → v c , the size of the population in this quasistationary regime diverges and the ratio N 2 t T / N t 2 T seems to converge to a value close to 2. This indicates that the fluctuations of the population size N t in the quasi-stationary regime are of the same order as N t itself.
For v < v c in fact, the whole distribution of N t at 0 ≪ t conditionned on the survival of a single individual at T = t + t ′ > t is independent of the position x of the initial individual and reaches a quasi-stationary regime [9] before a final relaxation to the final state containing only one individual. In this quasi-stationary regime one can show from (2) and (20,21) that the average size of the population N t qs can be calculated for v → v c (details will be published in [31]) and one finds For v > v c , no quasi-stationary state is observed (see figure 5). Instead, the evolution of the system conditionned on having a single survivor at a later time T can be divided into two parts. The first one corresponds to a rapid growth of the population, which can be described by the modified dynamics introduced in [8], followed by a regular absorption of individuals by the wall leading to the survival of exactly one individual at T . Numerical results obtained from (16) and (20,21) are presented in figure 5 : they indicate that N t T takes a scaling form In this article, we have seen how a branching random walk in presence of a moving absorbing walk undergoes a phase transition at a critical velocity v c with a survival probability which vanishes with an essential singularity (7) and decays with time like a stretched exponential (13) at the transition. We have also seen how the properties of the quasi-stationary regime [9] can be computed (17)(18)(19)(20)(21) from the travelling wave equation.
It is interesting to notice that several of our results are very reminiscent of what is known of noisy F-KPP like equation [17,26]. First the relation (22) between the size N of the population in the quasi-stationary regime and the velocity can be rewritten as : which is exactly the prediction of the cut-off approximation [17,26,32]. Moreover, for v < v c , the relaxation time τ ∼ (v c − v) −3/2 can be rewritten as : which is exactly what was observed recently for the coalescence times in the genealogies of evolution models [20,33] related to these noisy travelling wave equations.
Our results on the quasi-stationary regime presented here (eq. (22) and figures 4 and 5) are preliminary and will be developed in a forthcoming work [31].
Beyond the understanding of this quasi-stationary regime, it would be interesting to see whether our main results which are based on our guess (8) for the shape of the solution of (2) could be recovered by more standard methods like the renormalization group approach [5] or the phenomenological picture [32] of noisy fronts. Among other possible extensions of the present work, one could try to study how our results would be modified when the position of the wall has a more complicated evolution than a constant velocity [34].  (16,20,21). On the right side, the ratio N 2 t T / Nt 2 T is represented for 0 ≤ t ≤ T for the same values of v − vc < 0. In both cases, the initial individual at t = 0 is at x = 1. A quasi-stationary regime (with constant Nt T and N 2 t T / Nt 2 T ) is observed as soon as T is much larger than the relaxation time τ .