Exact propagators of one-dimensional self-interacting random walks
Julien Brémont Olivier Bénichou Raphaël Voituriez







Laboratoire de Physique Théorique de la Matière Condensée, CNRS/Sorbonne Université, 
 4 Place Jussieu, 75005 Paris, France
Laboratoire Jean Perrin, CNRS/Sorbonne Université, 
 4 Place Jussieu, 75005 Paris, France
 
Laboratoire de Physique Théorique de la Matière Condensée, CNRS/Sorbonne Université, 
 4 Place Jussieu, 75005 Paris, France
 
Laboratoire de Physique Théorique de la Matière Condensée, CNRS/Sorbonne Université, 
 4 Place Jussieu, 75005 Paris, France
Laboratoire Jean Perrin, CNRS/Sorbonne Université, 
 4 Place Jussieu, 75005 Paris, France


    Self-interacting random walks (SIRWs) show long-range memory effects that result from the interaction of the random walker at time t with the territory already visited at earlier times t'<t. This class of non-Markovian random walks has applications in contexts as diverse as foraging theory, the behaviour of living cells, and even machine learning.  Despite this importance and numerous theoretical efforts, the propagator, which is the distribution of the walker's position and arguably the most fundamental quantity to characterize the process, has so far remained out of reach for all but a single class of SIRW. Here we fill this gap and provide an exact and explicit expression for the propagator of two important classes of SIRWs, namely, the once-reinforced random walk and the polynomially self-repelling walk. These results give access to key observables, such as the diffusion coefficient, which  so far had not been determined. We also uncover an inherently non-Markovian mechanism that tends to drive the walker away from its starting point.


Exact propagators of one-dimensional self-interacting random walks
    R. Voituriez
    April 29, 2024
==================================================================





Consider the once-reinforced random walker (RWer) (X_t) on ℤ. This model, often called SATW (for self-attracting walk)  in the physics literature, is defined as follows. A nearest neighbour RWer starts at X_0=0. If it is on site x at time t and has not yet visited site x+1 (resp. x-1), it  jumps to this unvisited site at time t+1 with probability 1/(1+β) (resp. 1/(1+α)), while it  jumps to the visited site x-1 (resp. x+1) with probability β/(1+β) (resp. α/(1+α)). If it has already visited both x+1 and x-1, it  jumps to either with equal probability. If α>1 (or β>1), the RWer is thus attracted by the visited sites to its right (or left), whereas it is repelled  if α<1 (or β<1); α=β=1 restores the simple random walk (see FIG.<ref>)  This model belongs to the broad class of self-interacting random walks (SIRWs), which are characterized by long-lived  memory effects that emerge
from the interaction of the random walker at time t with all the sites  that it has visited at earlier times t' < t. SIRWs, and in particular SATWs have clear applications
in various examples where a random walker induces non vanishing, local perturbations in its  environment—typically leaving  footprints along
its way  and, in return, is sensitive  to its own footprints,  being either attracted or repelled <cit.>.
Such self-interactions have been reported qualitatively for ants or larger  animals that deposit
chemical cues as they move <cit.> ; they also proved to be relevant to design sampling algorithms <cit.>. Recently, they have  been identified for different types  of living cells <cit.>, whose dynamics was shown to be quantitatively captured by the SATW model. It was found
in vitro in one- and two-dimensional geometries that these cells can chemically and mechanically modify  their local environment.
 In turn,  these non vanishing  footprints were shown to drastically modify the large scale cell dynamics, with
cells being effectively attracted by their footprints and thus preferentially remaining within the previously visited area. 
These experimental findings provide a prototypical example of attractive SATW, for which memory effects were
demonstrated  to have striking consequences on the dynamics of space exploration, such as aging (for d=1,2)  and subdiffusion (for d=2) <cit.>. 


On the theoretical side, SIRW models have attracted a lot of attention in both the mathematics <cit.> and physics <cit.> communities. Related examples of non-Markovian processes, in which the full history of past trajectories determines the future evolution, include self-avoiding walks <cit.>, locally activated RWs <cit.>  and RWs with reinforcement such as the elephant walks <cit.>. A wide variety of observables, such as first-passage properties <cit.> or scaling exponents <cit.> have been calculated for SIRWs. Arguably, the propagator P_α,β(x,t), which is the probability for the RWer to be at site x at time t, is of fundamental importance. However, of all the SIRW models, so far the propagator has  been determined explicitly only for the single example of the so-called "true self-avoiding walk" in <cit.>. This model  relies on the specific choice of self-interactions whose strength at each site depends linearly on the total number of visits up to time t <cit.> and is thus unbounded, in sharp contrast with the SATW. Although it has been known  <cit.> that the SATW is diffusive at long times, and that its propagator satisfies P_α,β(x,t) ∼ p_α,β(x/√(2t))/√(2t) in the scaling limit x, t→∞, x^2/t fixed, even the calculation of the diffusion coefficient has so far remained out of reach.  Progresses have been made, notably in <cit.> and <cit.>, to determine the scaling function p_α,β for the SATW using results from generalised Ray-Knight theory, but these approaches did not provide explicit expressions for the propagator. In this Letter, using a different strategy, we obtain such an expression, and, as by-products, several other important quantities that so far remained unknown. We  first derive an exact expression of the joint distribution π_-m, k(t) of the minimum -m and of the time t needed to reach the maximum k for the SATW. From this quantity, we explicitly obtain the joint distribution of the maximum, the minimum and the position of the RWer at time t. Taking the marginal of this distribution yields the following exact expression for the scaling function p_α,β, which is our main result


    p_α,β(u = x/√(2t)) = (β-1)B(β ,α +1/2)/B(α ,β ) √(π)∑_n=0^∞(1-α/2)_n (β)_n/(1+2β+α/2)_nn+β/2/(n+β-1/2)(n+β+1/2)e^-u^2(2n+β)^2/n! for u ≥ 0


where B(x,y) is the Beta function, and (x)_n = x(x+1) …(x+n-1) is the Pochhammer symbol. The scaling function for u<0 follows from the space-reversal identity P_α,β(x,t) = P_β,α(-x,t). Of note, as shown below, this function also provides the propagator of another class of SIRW, namely the polynomially self-repelling walk (PSRW) <cit.>; it is displayed in FIG. <ref> and compared to  numerical simulations in FIG. <ref>. We provide below the main steps of the derivation of Eq.(<ref>). We obtain several interesting quantities as by-products of our analysis.
First, we obtain a new, exact expression for the splitting probability of SATW, which we give in the SM.
Second, via a mapping to a run-and-tumble particle, we are able to solve an entirely new class of time-inhomogeneous telegrapher's equations. We show in SM that the normalised solution of the following equation

    ∂_L^2 P + 2 ϕμ/sinh L μ∂_L P - ∂_c^2 P = 0, P(c,L=0) = δ(c)

is P(c,L) = (2B(1/2,ϕ))^-1∂_c B ((sinh(μ  c/2)/sinh(μ  L/2))^2,1/2,ϕ) where B(c,a,b) = ∫_0^c t^a-1(1-t)^b-1 dt is the incomplete Beta function. In the limit μ→ 0, we recover a known telegrapher's equation <cit.>.






Joint distribution of the minimum and time to reach the maximum.
Define π_-m, k(t) (resp. π_-m, k(t)) as the probability that the trajectory of the RWer has minimum -m (resp. maximum k) and that it reaches its maximum k (resp. minimum -m) at time t. Note that we underline the last location reached by the RWer. In this section, as a first step to obtain the propagator, we derive an exact expression for this joint distribution, which  is interesting on its own as it  was shown to play an important role in trapping problems <cit.>; in particular it gives access to classical splitting probabilities (see SM). Throughout, we denote the generating function of a given function f(t) by f̂(ξ) = ∑_t=0^∞ξ^t f(t). We will write ξ = (1+s)^-1, and μ = -log((1-√(1-ξ^2))/ξ) s→ 0√(2s). A partition over the events where the RWer reaches either k or -m first yields

    π̂_-m, k+1 = π̂_-m, kF̂^α,β_L(ξ, +|+) + π̂_-m, kF̂^α,β_L(ξ, +|-)

where F̂_L^α,β(+|-) is the generating function of  F_L^α,β(τ=t, ε|ε'), which is  defined as follows. Denote  the span of the RWer at time t (defined as the set of sites visited by the RWer up to time t) as [-m,k], with m,k≥0, and set  L=k+m. We denote by τ the time needed for the RWer starting from the boundary ε = ± of [-m,k] (+ for k, - for -m) to leave [-m,k] through the boundary ε'=± exactly at time τ ; F_L^α,β(τ=t, ε|ε') is then defined as  the distribution of τ. It is a 2× 2 matrix with indices ±, which we call F_L^α,β(t) ; its generating function   
 F̂_L^α,β is derived  in the SM with the help of a renewal equation <cit.>.
Equation (<ref>) (and its counterpart for π̂_-m-1, k) then gives access to the joint distribution  π we are looking for. Making use of the following non trivial symmetry relation proved in SM

    π̂_-m, k/π̂_-m, k = sinh(k μ)/sinh(m μ),

we obtain

    π̂_-m, k = π̂_-m, 1∏_j=1^k-1[sinh mμ/sinh j μF̂^α,β_m+j(+|-) + F̂^α,β_m+j(+|+) ]

where π̂_-m, 1 = F̂_m^α,β(+|-) ∏_j=0^m-1F̂_j^α,β(-|-), which holds for all values of parameters. In particular, in the scaling  regime L→∞, s→ 0, L√(s) fixed, we find 

    F̂_L^α,β∼1_2 + √(2s)[    -β(L√(2s)) α/sinh L√(2s); β/sinh L√(2s)    -α(L√(2s)) ]

where 1_2 is the identity matrix. Taking the scaling limit of (<ref>) with the help of (<ref>), in the regime k,m ≫ 1, s→ 0, L√(s) fixed, we finally obtain (see SM):

    π̂_-m, k∼√(2s)/B(α,β)sinh^β-1 (m√(2s)) sinh^α(k√(2s))/sinh^α+β((k+m)√(2s)).















Joint distribution of minimum, maximum, and position.
Next, we derive the scaling limit  of the  generating function  of the joint distribution Q(k,m,x,t) of the minimum, maximum, and position of the RWer. A partition over the events where  the most recent visited site is either  k or -m yields

    Q̂(k,m,x,ξ) = π̂_k,-mP̂_s^m,k(x|+) + π̂_-m,kP̂_s^m,k(x|-)

where P̂_s^m,k(x|ε) is the generating function of P_s^m,k(x,τ|ε) defined as 
the probability that the RWer is on site x at time t+τ and has not left the span  [-m,k], knowing that it was at  the boundary ε = ± of the span at time t. Using a renewal approach <cit.>, we compute this quantity  in SM and show that, in the scaling limit m, k ≫ 1, s → 0, L√(s) fixed, one has 

    P̂_s^m,k(x|-) ∼2α (sinh(k-x)√(2s))/sinh L√(2s).

Finally, we have obtained all terms in the rhs of (<ref>), which provides an exact determination of Q̂(k,m,x,s) for all values of the parameters. In the asymptotic limit k,m ≫ 1, s → 0, L√(s) fixed, this gives the simpler form


    Q̂(k,m,x,s) ∼2√(2s)/B(α,β)sinh^β (m√(2s)) sinh^α(k√(2s))/sinh^α+β+1((k+m)√(2s))( βsinh(m+x)√(2s)/sinh(m√(2s)) + αsinh(k-x)√(2s)/sinh(k√(2s))).


The joint distribution  Q(k,m,x,t) readily gives access  to the propagator with absorbing boundaries  P̃_a,b(x,t), which is the probability that the RWer, starting at 0 at time t=0, is at x at time t, knowing that it is absorbed if it hits the sites -a,b. For x≥ 0, this can be written as P̃_a,b(x,t) = ∑_k=x^b-1∑_m=0^a-1 Q(k,m,x,t). In the scaling limit, the sums can be written as integrals, which we compute explicitly  for a,b →∞ (see SM) : this limit yields the unconstrained propagator (<ref>), which is the main result of this Letter. Besides its intrinsic importance, this result reveals   several remarkable features of the SATW. Moments of the position X_t.  First, Eq. (<ref>)  gives access to the moments ⟨ X_t^n ⟩ of the position of the RWer at time t.  In the general case α≠β, the mean position ⟨ X_t ⟩ is non-zero ; it is obtained exactly from  (<ref>) and can be written ⟨ X_t ⟩ = g_1(α,β) √(2t) where g_1(α,β) = -g_1(β,α) is explicitly given in the SM and plotted in  FIG. <ref>(a). Note the √(t) scaling of the mean position (expected from the general scaling form of p_α,β), which is at odds with the classical case of diffusion with constant drift.  In limit cases, simple forms of g_1(α,β) can be derived : for α=1, one has  g_1(1,β) = (1-β)/(√(π)β), and  we find the asymptotic behaviour 
g_1(α,β) α→ 0 -1/(α√(π)). 
Next, the variance V(X_t) = ⟨ X^2_t ⟩ - ⟨ X_t ⟩^2t →∞ 2D_α,β t is also obtained from Eq. (<ref>) and defines the diffusion coefficient D_α,β, which  is a symmetric function of α,β given in SM.  Limiting cases yield the simple expressions  D_1,β = (πβ  (β -1)-2(β -1)^2+π)/(2πβ ^2) and
D_α,βα→ 0  (π-2)/(2πα^2). Remarkably,  our approach provides in particular an explicit expression, so far unknown,  in the symmetric case α=β :


    D_α,α = 1/2 + (1-α ) B(α +1/2,α)/B(α ,α )  _4F_3(1-α/2,α/2,α/2,α ;α/2+1,α/2+1,3 α/2+1/2;1)/α ^2
 

where _pF_q is a hypergeometric function. 


Finally, Eq. (<ref>) shows that the propagator is not Gaussian (for (α,β)≠(1,1)), even if it has  a Gaussian tail p_α,β(u) u→∞ e^-u^2 β ^2. Of note, if α = 2n+1 is an odd integer, the Pochhammer symbol ((1-α)/2)_k is zero for k > n, so that   p_α,β is a finite sum of n+1 Gaussian functions.   Non-Gaussianity can be quantified by  the fourth cumulant κ_4(t) = ⟨ X_t^4 ⟩ - 3 ⟨ X_t^2 ⟩^2 = 3g_4(α,β) t^2, where g_4 is a symmetric function given in SM and g_4(1,β) = β^-3(β-1)^2. 
This function is shown FIG. <ref>(b) for α=β.


Non-monotonicity and smoothness of p_α,β(u). A second remarkable  feature of the propagator P_α,β(x,t),  which is not captured by a direct analysis of the moments of X_t, is its non-monotonicity. In fact, for some values of α, β < 1 (repelling SATWs), we find that the distribution has local maxima, or bumps, for non-zero values of x, which we write as x_±(t). While explicit exact expressions for x_± seem out of reach, a good approximation can be obtained  for  α, β small by keeping only the first two terms in the sum (<ref>) defining p_α,β(u). Solving ∂_u p_α,β(u) = 0 with this approximation  then yields

    x_+(t) α, β→ 0√(t/2(1+β)log(1-α) (1-β) (β +2)^3/β^2 (β +3) (α +2 β +1)) ;

 a similar expression for x_- is obtained by swapping α and β. Requiring that the argument of  the log in this expression is greater than 1 provides an explicit  condition on α,β for P_α,β(x,t) to have bumps for x>0 ;  in the SM, we verify that this  condition accurately predicts non monotonicity of the propagator for a broad range of values  of α, β. The accuracy of the approximate prediction  (<ref>) is illustrated in FIG.<ref>. This shows that self-repulsion at the edges of the visited territory, if strong enough, can drive the RWer away from 0 and yield a non monotonic propagator, while preserving the diffusive scaling. We now turn to regularity properties of the scaling function p_α,β. First, note that due to the different definitions for u>0 and u<0 in (<ref>) for α≠β, writing the continuity of p_α,β  at u=0  yields a non trivial identity involving  hypergeometric functions, which we indeed verify up to arbitrary precision numerically (see SM). Second, we show in SM (see  FIG. <ref>) that p_α,β  has a continuous,  vanishing derivative at u=0 for all α, β : this is in contrast with the propagator  of the true self-avoiding walk <cit.>, or locally activated random walks <cit.>, which have  singular derivatives at u=0. 

Extension: polynomially self-repelling walk (PSRW). Last, we obtain the exact propagator of the PSRW introduced in <cit.>. It is defined as a RW on ℤ with jump probabilities

    P_t(x + 1|x) = w(L_t(x+1))/w(L_t(x+1) + w(L_t(x)) = 1-P_t(x-1|x)

where L_t(x) is the number of times the RWer has crossed the unoriented edge {x,x- 1} up to time t, and w(n) n →∞ n^-γ for  0<γ<∞. Although so far no explicit expression could be obtained for the propagator of the PSRW, it was shown in <cit.>  that the scaling variable u = x / √(2t(2γ+1)), in the regime x,t →∞, u fixed, is distributed according to p_1/2,1/2(u). Our explicit expression (<ref>) thus provides readily an exact expression of the propagator of the PSRW as a by-product.  Numerical simulations FIG. <ref>(b) confirm this  result. In particular,  an exact determination of the  diffusion coefficient of the PSRW is deduced from our result (<ref>) for α=β=1/2 and reads 

    D_PSRW = (2γ+1) (1/2 + C + π^2/16),
 
where C is Catalan's constant.

Finally, we have obtained an exact,  explicit expressions for the propagator of two important classes of strongly non Markovian random walks, namely, the once-reinforced random walk (SATW) and the polynomially self-repelling walk (PSRW). These analytic expressions provide benchmark  results which  give access to various observables of broad relevance, such as the diffusion coefficient, which has so far remained undetermined. Our results reveal remarkable features of the SATW, such as a smooth, non monotonic behaviour of the propagator in the case of strong enough self-repulsion induced by the   inherently non-Markovian nature of the dynamics.

10

golestanian1
W. Till Kranz, Anatolij Gelimson, Kun Zhao, Gerard C. L. Wong, and Ramin Golestanian.
Effective dynamics of microorganisms that interact with their own trail.
Phys. Rev. Lett., 117:038101, Jul 2016.

golestanian2
W. Till Kranz and Ramin Golestanian.
Trail-mediated self-interaction.
The Journal of Chemical Physics, 150(21), June 2019.

ants
Audrey Dussutour, Vincent Fourcassié, Dirk Helbing, and Jean-Louis Deneubourg.
Optimal traffic organization in ants under crowded condition.
Nature, 428:70–3, 04 2004.

animals
Luca Giuggioli, Jonathan R. Potts, and Stephen Harris.
Animal interactions and the emergence of territoriality.
PLOS Computational Biology, 7(3):1–9, 03 2011.

maggs
A. C. Maggs.
Non-reversible Monte Carlo: an example of 'true' self-repelling motion, October 2023.
arXiv:2310.19494 [cond-mat].

cellattract
Henrik Flyvbjerg.
Past attractions set future course.
Nature Physics, 17(7):771–772, July 2021.
Publisher: Nature Publishing Group.

naturealex
Joseph d’Alessandro, Alex Barbier-Chebbah, Victor Cellerin, Olivier Benichou, René Mège, Raphaël Voituriez, and Benoit Ladoux.
Cell migration guided by long-lived spatial memory.
Nature Communications, 12, 07 2021.

lucas
Lucas Tröger, Florian Goirand, and Karen Alim.
Size-dependent self-avoidance enables superdiffusive migration in macroscopic unicellulars.
Proceedings of the National Academy of Sciences, 121(13):e2312611121, March 2024.
Publisher: Proceedings of the National Academy of Sciences.

pemantle
Robin Pemantle.
A survey of random processes with reinforcement.
Probability Surveys, 4(none):1 – 79, 2007.

toth96
Bálint Tóth.
Generalized Ray-Knight theory and limit theorems for self-interacting random walks on ℤ.
The Annals of Probability, 24(3):1324–1367, July 1996.
Publisher: Institute of Mathematical Statistics.

carmona-yor
Philippe Carmona, Frédérique Petit, and Marc Yor.
Beta Variables as Times Spent in [0,infty[ by Certain Perturbed Brownian Motions.
Journal of the London Mathematical Society, 58(1):239–256, 08 1998.

diffusive-tsaw
Illés Horváth, Bálint Tóth, and Bálint Vető.
Diffusive limits for “true” (or myopic) self-avoiding random walks and self-repellent brownian polymers in d≥ 3.
Probability Theory and Related Fields, 153(3–4):691–726, April 2011.

dumaz
Laure Dumaz and Bálint Tóth.
Marginal densities of the “true” self-repelling motion.
Stochastic Processes and their Applications, 123(4):1454–1471, April 2013.

parisi
Daniel J. Amit, G. Parisi, and L. Peliti.
Asymptotic behavior of the "true" self-avoiding walk.
Phys. Rev. B, 27:1635–1645, Feb 1983.

prasad
M. A. Prasad, D. P. Bhatia, and D. Arora.
Diffusive behaviour of self-attractive walks.
Journal of Physics A Mathematical General, 29(12):3037–3040, June 1996.

sapo
V B Sapozhnikov.
Self-attracting walk with nu=1/2.
Journal of Physics A: Mathematical and General, 27(6):L151, mar 1994.

alex-anomalous
A. Barbier-Chebbah, O. Benichou, and R. Voituriez.
Anomalous persistence exponents for normal yet aging diffusion.
Phys. Rev. E, 102:062115, Dec 2020.

alexprx
A. Barbier-Chebbah, O. Bénichou, and R. Voituriez.
Self-interacting random walks: Aging, exploration, and first-passage times.
Phys. Rev. X, 12:011052, Mar 2022.

abc
Angela Stevens and Hans G. Othmer.
Aggregation, blowup, and collapse: The abc's of taxis in reinforced random walks.
SIAM Journal on Applied Mathematics, 57(4):1044–1081, 1997.

structural
A. Ordemann, E. Tomer, G. Berkolaiko, S. Havlin, and A. Bunde.
Structural properties of self-attracting walks.
Phys. Rev. E, 64:046117, Sep 2001.

grassberger
Jacob Foster, Peter Grassberger, and Maya Paczuski.
Reinforced walks in two and three dimensions.
New Journal of Physics, 11, 02 2009.

hughes1995random
B.D. Hughes.
Random Walks and Random Environments: Random walks.
Number vol. 1 in Oxford science publications. Clarendon Press, 1995.

larw-pre
Olivier Benichou, Nicolas Meunier, Sidney Redner, and Raphael Voituriez.
Non-Gaussianity and Dynamical Trapping in Locally Activated Random Walks.
February 2012.

larw-new
Julien Brémont, Theresa Jakuszeit, Olivier Bénichou, and Raphael Voituriez.
Aging dynamics of d-dimensional locally activated random walks, 2023.

schutz
Gunter M. Schütz and Steffen Trimper.
Elephants can always remember: Exact long-range memory effects in a non-Markovian random walk.
Physical Review E, 70(4):045101–, October 2004.
Publisher: American Physical Society.

baur
Erich Baur and Jean Bertoin.
Elephant random walks and their connection to pólya-type urns.
Physical Review E, 94(5):052134, November 2016.
Publisher: American Physical Society.

bercu
Bernard Bercu and Lucile Laulin.
On the center of mass of the elephant random walk.
Stochastic Processes and their Applications, 133:111–128, March 2021.

doney
R.A. Doney.
Some calculations for perturbed brownian motion.
Séminaire de probabilités de Strasbourg, 32:231–236, 1998.

davis
Burgess Davis.
Reinforced random walk.
Probability Theory and Related Fields, 84(2):203–229, June 1990.

klinger
J. Klinger, A. Barbier-Chebbah, R. Voituriez, and O. Bénichou.
Joint statistics of space and time exploration of one-dimensional random walks.
Physical Review E, 105(3):034116, March 2022.
Publisher: American Physical Society.

alex
Alex Barbier-Chebbah.
Observables de premier passage de marches aléatoires à renforcement.
Theses, Sorbonne Université, December 2021.

tarres
Pierre Tarrès.
Vertex-reinforced random walk on ℤ eventually gets stuck on five points.
The Annals of Probability, 32(3B), July 2004.

Metzler2014AnomalousDM
Ralf Metzler, Jae-Hyung Jeon, Andrey G. Cherstvy, and Eli Barkai.
Anomalous diffusion models and their properties: non-stationarity, non-ergodicity, and ageing at the centenary of single particle tracking.
Physical chemistry chemical physics : PCCP, 16 44:24128–64, 2014.

ecology
Luca Börger, Benjamin D. Dalziel, and John M. Fryxell.
Are there general mechanisms of animal home range behaviour? a review and prospects for future research.
Ecology Letters, 11(6):637–650, 2008.



in 1,...,15

	[pages=]SM.pdf 


