Exact propagators of one-dimensional self-interacting random walks
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Condensed Matter. The day in condensed matter: materials, phases and the measurements under them.
Kai: We're looking at the paper: "Exact propagators of one-dimensional self-interacting random walks".
Title and authors: Kai: So to start, this paper is titled "Exact propagators of one-dimensional self interacting random walks." And the authors are Julien Br´emont, O. B´enichou, and R. Voituriez from the Laboratoire de Physique Th´eorique de la Mati`ere Condens´ee at CNRS/Sorbonne Universit´e.
Mira: The title tells you exactly what they're delivering: exact expressions for the propagator of SIRWs. It’s focused on two specific models, the once reinforced random walk and the polynomially self repelling walk.
Lev: For an engineer, that means they’ve managed to get a closed-form solution for the probability distribution of where you will be at any given time t, which is much better than getting just some scaling behavior in a limit.
Kai: It’s about moving from just knowing how things behave in a certain limit to having the actual function that describes the whole process, which is what they provide here.
Mira: They are essentially providing the main result, that exact expression for the scaling function p alpha beta u, which is defined by equation one on page two of this work. That's their central finding.
Lev: I’m interested in how they get that expression because getting an explicit formula like that is one thing; making sure it's correct and stable enough to be used for actual calculations is another whole different thing.
The paper's summary: Kai: The summary explains that the authors derive an exact expression for the scaling function p alpha beta u, which describes the distribution of a walker's position scaled by the time and space in a certain way. This function is their main result.
Mira: They also derived something called the joint distribution of the minimum and maximum visited sites, along with their position at time t for both those important classes of SIRWs. That’s pretty detailed information about the entire trajectory history summarized at once.
Lev: So, they aren't just giving you a single piece of data about where you are; they’re giving you the whole picture of how your path has been influenced by its past visits within that span.
Kai: The paper shows how this leads to an exact expression for the scaling function p alpha beta u, which is what they call their main result on page two. It involves complex sums with Beta functions and Pochhammer symbols.
Mira: And beyond just that, they get other important quantities as by products, like the diffusion coefficient and the mean position of the walker at time t. These are things that were previously unknown for these specific models.
Lev: The fact that they get these other quantities as byproducts is interesting because it means you don't have to re-derive all those other fundamental metrics from scratch; you just use this main result to find everything else.
The paper's improvements: Kai: So, the improvements suggested by this work are pretty significant because they give us access to things like the diffusion coefficient, which was previously undetermined for these walks. This is a key observable that we now have a formula for.
Mira: And they provide an explicit expression for the symmetric case, where alpha equals beta. They find an explicit expression for D alpha alpha involving a hypergeometric function pFq, which was previously unknown.
Lev: If you're building hardware, having an exact formula for the diffusion coefficient is crucial because it helps you predict how fast noise or interaction effects will cause the walker to spread over time.
Kai: And they also give us the mean position of the walker at time t, which is non zero whenever alpha is not equal to beta. This means we can quantify exactly how far on average the walker drifts away from its starting point.
Mira: Plus, they tackle the scaling limit where k and m are much larger than one and s goes to zero while L times sqrt s stays fixed. In this limit, the propagator simplifies to a form involving hyperbolic functions.
Lev: That simplification in the scaling limit is what we’ll really want to use for practical applications because it cuts down on the complexity of the full expression when you need a fast estimate for large systems.
Conclusion: Kai: So, to wrap up, this paper "Exact propagators of one-dimensional self interacting random walks" gives us an exact and explicit expression for the propagator of the once reinforced random walk and the polynomially self repelling walk.
Mira: The main result is that exact scaling function p alpha beta u, which describes the distribution of position scaled by time and space, which they derived using a different strategy than previous work.
Lev: And this gives us access to key observables like the diffusion coefficient and mean position of the walker at time t, even when alpha is not equal to beta.
Kai: It also gives us an explicit expression for the symmetric diffusion coefficient D alpha alpha, and they analyzed how it behaves in certain scaling limits involving hyperbolic functions.
Mira: In short, this work provides a complete toolkit for understanding these two important classes of SIRWs by giving us the exact propagator and many other fundamental quantities that were previously out of reach.
Lev: From my side, I just think having this explicit formula is a big step because it moves us from theoretical existence to actual computation for real hardware modeling and error correction overhead analysis.
Kai: Agreed, moving from just saying something exists to actually being able to compute the results is what matters here for experimental validation.
Mira: Yeah, understanding how these long range memory effects manifest in the scaling function really helps us understand how these complex systems behave over time.
Julien Brémont, O. Bénichou, R. Voituriez
Laboratoire de Physique Thẞorique de la Matière Condensẞe, CNRS/Sorbonne Université · Laboratoire Jean Perrin, CNRS/Sorbonne Université
cond-mat.stat-mech, math.PR
Submitted: 2024-04-24
Updated: 2024-04-24
Journal ref: PhysRevLett.133.157101 (2024)
DOI: 10.1103/PhysRevLett.133.157101
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 84/100
The gist: 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′ This…
Key concepts
- Self-Interacting Random Walks (SIRWs)
- These are random walks where the walker's movement depends on where it has previously visited. The walker interacts with its own past trajectory, creating a non-Markovian process that exhibits long-range memory. This is common in systems like foraging or cell behavior.
- Propagator
- The propagator is a mathematical function that describes the evolution of the probability distribution of a random walk over time. By finding an exact expression for it, researchers can precisely model how the walker's position changes and understand its long-term behavior.
- Scaling Function pα,β(u)
- This function describes the shape of the walker's position distribution in a specific scaling limit. Finding its exact form is a main result, as it characterizes the long-range memory effects inherent in these walks and allows for precise calculations of observables.
- Diffusion Coefficient (Dα,β)
- The diffusion coefficient measures how quickly the walker spreads out over time. Determining this coefficient exactly is crucial because it has not been determined previously in these models, providing a fundamental parameter for characterizing the walk's spreading behavior.
Terminology
Summary
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′ 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<ref:2404. p. 015853#pg2> 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<ref:2404. p. 015853#pg2> These results give access to key observables, such as the diffusion coefficient, which so far had not been determined<ref:2404. p. 015853#pg2> We also uncover an inherently non-Markovian mechanism that tends to drive the walker away from its starting point<ref:2404. p. 015853#pg2>
Exact Propagator Derivations
The authors provide an exact and explicit expression for the propagator of two important classes of SIRWs, namely, the once-reinforced random walk (RWer) and the polynomially self-repelling walk (PSRW)<ref:2404.15853#pg2> For the once-reinforced random walk (SATW), an exact expression for the scaling function pα,β is derived as Eq. p. 0(1)<ref:2404. p. 0 p. 0 p. 015853#pg3> This scaling function is given by a complex sum involving Beta functions and Pochhammer symbols<ref:2404. p. 315853#pg3> The joint distribution of the minimum −m and of the time t needed to reach the maximum k for the SATW is derived as Eq. p. 1(1)<ref:2404.15853#pg3> This leads to an exact expression for the scaling function pα,β which is our main result<ref:2404. p. 115853#pg3>
Key Observables and Scaling Limits
The exact propagator (Eq.(1)) provides access to key observables such as the diffusion coefficient<ref:2404. p. 015853#pg10> The mean position ⟨Xt⟩ is non-zero in the general case α ≠ β, and it is obtained exactly from Eq. p. 2(1)<ref:2404.15853#pg10> In the scaling limit k, m ≫ 1, s → 0, L√s fixed, the propagator simplifies to a form involving hyperbolic functions<ref:2404. p. 015853#pg10> The diffusion coefficient Dα,β is also obtained from Eq. p. 2(1) and defines the diffusion coefficient Dα,β<ref:2404. p. 215853#pg10> For the symmetric case α = β, an explicit expression for Dα,α is found involving a hypergeometric function pFq<ref:2404. p. 215853#pg10>
Non-Markovian Features and Regularity
The propagator Pα,β(x, t) is not Gaussian (for (α, β) ≠ (1, 1)), even if it has a Gaussian tail pα,β(u) ∝ u→∞ e−u2β2<ref:2404.15853#pg10> For repelling SATWs with α, β < 1, the distribution can have local maxima or bumps for non-zero values of x, denoted as x±(t)<ref:2404. p. 315853#pg10> The existence of these bumps is governed by the inequality (69): (1 − α)(1 − β)(β + 2)3β/2(β + 3)(α + 2β + 1) > 1<ref:2404. p. 315853#pg10> The derivative of the scaling function pα,β has a vanishing right derivative at u = 0 for all α, β<ref:2404. p. 315853#pg10>
Extension to PSRW and Moments
The exact propagator of the polynomially self-repelling walk (PSRW) is obtained as a by-product of the SATW result<ref:2404.15853#pg10> The diffusion coefficient D P SRW is deduced from our result (10) for α = β = 1/2 and reads DP SRW = (2γ + 1) 1/2 + C + π/2 6<ref:2404. p. 315853#pg10> The moments of the position Xt are also accessible, with the mean position scaling as √t<ref:2404. p. 215853#pg10> The variance V (Xt) is defined by V (Xt) t ∼ 2Dα,βt<ref:2404. p. 215853#pg10>
Regularity Properties of the Scaling Function
The continuity of pα,β at u = 0 implies a non-trivial identity involving hypergeometric functions<ref:2404.15853#pg10> The scaling function pα,β has a continuous, vanishing derivative at u = 0 for all α, β<ref:2404. p. 315853#pg10> The left limit of pα,β at u = 0 is deduced from swapping α and β and implies an identity of hypergeometric functions h(α, β) = h(β, α)<ref:2404. p. 315853#pg10>
Computing the Scaling Function
The scaling function pα,β defined by Pα,β(x, t) ∼ pα,β u = x/√2t in the region x > 0 is obtained by taking the Laplace transform of Qˆ(k, m, x, s) in the scaling limit<ref:2404.15853#pg10> This leads to an exact expression for pα,β defined by Eq. p. 1(56)<ref:2404. p. 0 p. 015853#pg10> The propagator is normalized as R pα,β(u)du = 1<ref:2404. p. 015853#pg10>
Exact Splitting Probability
The exact splitting probability P(reach k before −m) of the SATW is deduced using the expression P(reach k before −m) = 1 - Γ(k + α)Γ(k + m)Γ(m + β) 3F2<ref:2404.15853#pg10> This probability is given by a formula involving Gamma functions and a generalized hypergeometric function<ref:2404. p. 315853#pg10>
Propagator in the Span with Absorption
The probability P m,k s(x, τ ε) that the RWer is at site x at time t + τ and has remained within the interval [−m, k] is given by Eq.(8)<ref:2404. p. 015853#pg10> In the limit k, m ≫ 1, s → 0, L√s fixed, this simplifies to Pˆs,- (x) = 2α sinh(k − x)µ/sinhLµ<ref:2404. p. 215853#pg10>
Moments of the Position Xt
The mean position ⟨Xt⟩+ in the scaling limit is given by k1(α, β) = 2−α(β − 1)Γ β+1/2 Γ(α + β) 3F˜2<ref:2404.15853#pg10> The second moment is given by k2(α, β) = α/ (α + β - √π 2−α-1) (β − 1)Γβ/2 Γ(α + β) 4F˜3<ref:2404. p. 015853#pg10> The variance V (Xt) is given by V (Xt) = k2(α, β) + k2(β, α) - 2(k1(α, β) − k1(β, α)) squared = 2Dα,β<ref:2404. p. 215853#pg10> The fourth cumulant is κ4 = h k4(α, β) + k4(β, α) - (k2(α, β) + k2(β, α)) squared<ref:2404. p. 3 p. 315853#pg10>
Non-monotonicity of pα,β
A non-rigorous criterion for the existence of local maxima at nonzero values of u is (1 − α)(1 − β)(β + 2)3β/2(β + 3)(α + 2β + 1) > 1<ref:2404.15853#pg10> The scaling function pα,β has a vanishing right derivative at u = 0 if and only if u P1/u n=1 n−α →u→0 is O(uα)<ref:2404. p. 315853#pg10>
Regularity of the Scaling Function
The continuity of pα,β at u = 0 yields a non trivial identity involving hypergeometric functions<ref:2404.15853#pg10> The left limit is deduced from swapping α, β and implies an identity h(α, β) = h(β, α)<ref:2404. p. 015853#pg10> The scaling function pα,β has a vanishing right derivative at u = 0<ref:2404. p. 315853#pg10>
The final expression for the propagator in the scaling limit is obtained by Laplace inverting Eq.(56)<ref:2404.15853#pg10> This yields exactly the scaling function pα,β defined by Pα,β(x, t) ∼ pα,β u = x/√2t in the region x > 0<ref:2404. p. 115853#pg10>
Exact Splitting Probability of the SATW
The exact splitting probability P(reach k before −m) is given by 1 - Γ(k + α)Γ(k + m)Γ(m + β) 3F2 B(α, β)Γ(k)Γ(m + 1)Γ(k + m + α + β)<ref:2404.15853#pg10>
Propagator in the Span with Absorption at the Span Boundaries
The propagator Pˆs,−(x ≠ −m, k) simplifies to 2αcsch(µL)(β tanh(µ)csch(µL) sinh(µ(a + x)) + sinh(µ(b − x))(β tanh(µ) coth(µL) + 1)<ref:2404.15853#pg10> In the limit k, m ≫ 1, s → 0, L√s fixed, these simplify to Pˆs,- (x) = 2α sinh(k − x)µ/sinhLµ<ref:2404. p. 215853#pg10>
The mean position ⟨Xt⟩+ in the scaling limit is given by k1(α, β)<ref:2404.15853#pg10> The second moment is given by k2(α, β)<ref:2404. p. 015853#pg10> The variance V (Xt) t = 1/t ⟨X2t⟩ - ⟨Xt⟩ squared = k2(α, β) + k2(β, α) - 2(k1(α, β) - k1(β, α)) squared = 2Dα,β<ref:2404. p. 215853#pg10> The fourth cumulant is κ4 = h k4(α, β) + k4(β, α) - (k2(α, β) + k2(β, α)) squared<ref:2404.15853#pg10> The fourth moment is ⟨X4t⟩ ∼ 3 (k4(α, β) + k4(β, α))t squared<ref:2404. p. 015853#pg10>
A non-rigorous criterion for the existence of local maxima at nonzero values of u is (1 − α)(1 − β)(β + 2)3β/2(β + 3)(α + 2β + 1) > 1<ref:2404.15853#pg10>
The derivative at u = 0 is well-defined and ∂upα,β(u)u=0 = 0<ref:2404.15853#pg10> The continuity of pα,β at u = 0 implies an identity h(α, β) = h(β, α)<ref:2404. p. 315853#pg10>
A non-rigorous criterion for the existence of local maxima at nonzero values of u is (1 − α)(1 − β)(β + 2)3β/2(β + 3)(α + 2β + 1) > 1<ref:2404.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can determine exact propagators for two important classes of self-interacting random walks, namely, the once-reinforced random walk and the polynomially self-repelling walk. This provides access to key observables such as the diffusion coefficient, which had so far not been determined in these models.
-
Improved AI systems can uncover an inherently non-Markovian mechanism that tends to drive the walker away from its starting point in these SIRW models. This understanding is crucial for modeling processes where past trajectory history strongly influences future evolution.
-
Improved AI systems can calculate the exact scaling function p alpha beta u, which is the main result of this Letter (Equation 1). This function describes the distribution of a walker's position and can be used to characterize long-range memory effects in these walks.
-
Improved AI systems can determine moments of the position Xt, including the mean position G1(alpha beta) sqrt(2t), which is non-zero for alpha not equal to beta. This allows for more accurate prediction of the walker's average displacement over time t.
-
Improved AI systems can compute an explicit expression for the diffusion coefficient D alpha beta in the symmetric case alpha = beta, which was previously unknown. This is given by D alpha alpha = 1/2 + (1 - alpha) B(alpha+1/2, 4F3(1-alpha squared, beta squared, beta squared, beta; beta+2/2, beta+2/2, alpha+1/2; 1 / alpha 4).
-
Improved AI systems can analyze the non-monotonicity of the propagator P alpha beta u. This is done by checking the inequality (69), which provides a criterion for the existence of local maxima or bumps in p alpha beta u in the positive half-space u > 0.
Sources
Related papers
- Emergent long-tail dynamics in driven magnets with dynamical frustration
- Statistical Mechanics of Dynamical System Identification
- Second law of thermodynamics in closed quantum many-body systems
- Chemical potentials from structure factors: II. Charged multi-component mixtures
- Genuine quantum scars in Floquet chaotic many-body systems
- Stochastic Thermodynamics for Autoregressive Generative Models: A Non-Markovian Perspective