Universal first-passage statistics in aging media

Evidence and quantification of memory effects in competitive first-passage events

Splitting probabilities quantify the likelihood of a given outcome out of competitive events. This key observable of random walk theory, historically introduced as the gambler's ruin problem, is well understood for memoryless (Markovian) processes. However, in complex systems such as polymer fluids, the motion of a particle should typically be described as a process with memory, for which splitting probabilities are much less characterized analytically. Here, we introduce an analytical approach that provides the splitting probabilities for one-dimensional isotropic non-Markovian Gaussian processes with stationary increments, in the case of two targets. This analysis shows that splitting probabilities are controlled by the out-of-equilibrium trajectories observed after the first passage. This is directly evidenced in a prototypical experimental reaction scheme in viscoelastic fluids. These results are extended to d-dimensional processes in large confining volumes, opening a path toward the study of competitive events in complex media.

Heterogeneous Mean First-Passage Time Scaling in Fractal Media

The mean first passage time (MFPT) of random walks is a key quantity characterizing dynamic processes on disordered media. In a random fractal embedded in the Euclidean space, the MFPT is known to obey the power law scaling with the distance between a source and a target site with a universal exponent. We find that the scaling law for the MFPT is not determined solely by the distance between a source and a target but also by their locations. The role of a site in the first passage processes is quantified by the random walk centrality. It turns out that the site of highest random walk centrality, dubbed as a hub, intervenes in first passage processes. We show that the MFPT from a departure site to a target site is determined by a competition between direct paths and indirect paths detouring via the hub. Consequently, the MFPT displays a crossover scaling between a short distance regime, where direct paths are dominant, and a long distance regime, where indirect paths are dominant. The two regimes are characterized by power laws with different scaling exponents. The crossover scaling behavior is confirmed by extensive numerical calculations of the MFPTs on the critical percolation cluster in two dimensional square lattices.

Record ages of non-Markovian scale-invariant random walks

How long is needed for an observable to exceed its previous highest value and establish a new record? This time, known as the age of a record plays a crucial role in quantifying record statistics. Until now, general methods for determining record age statistics have been limited to observations of either independent random variables or successive positions of a Markovian (memoryless) random walk. Here we develop a theoretical framework to determine record age statistics in the presence of memory effects for continuous non-smooth processes that are asymptotically scale-invariant. Our theoretical predictions are confirmed by numerical simulations and experimental realisations of diverse representative non-Markovian random walk models and real time series with memory effects, in fields as diverse as genomics, climatology, hydrology, geology and computer science. Our results reveal the crucial role of the number of records already achieved in time series and change our view on analysing record statistics.

Leftward, rightward, and complete exit-time distributions of jump processes

First-passage properties of continuous stochastic processes confined in a one-dimensional interval are well described. However, for jump processes (discrete random walks), the characterization of the corresponding observables remains elusive, despite their relevance in various contexts. Here we derive exact asymptotic expressions for the leftward, rightward, and complete exit-time distributions from the interval [0,x] for symmetric jump processes starting from x_{0}=0, in the large x and large time limit. We show that both the leftward probability F_{[under 0]̲,x}(n) to exit through 0 at step n and rightward probability F_{0,[under x]̲}(n) to exit through x at step n exhibit a universal behavior dictated by the large-distance decay of the jump distribution parametrized by the Levy exponent μ. In particular, we exhaustively describe the n≪(x/a_{μ})^{μ} and n≫(x/a_{μ})^{μ} limits and obtain explicit results in both regimes. Our results finally provide exact asymptotics for exit-time distributions of jump processes in regimes where continuous limits do not apply.

Universal exploration dynamics of random walks

The territory explored by a random walk is a key property that may be quantified by the number of distinct sites that the random walk visits up to a given time. We introduce a more fundamental quantity, the time τn required by a random walk to find a site that it never visited previously when the walk has already visited n distinct sites, which encompasses the full dynamics about the visitation statistics. To study it, we develop a theoretical approach that relies on a mapping with a trapping problem, in which the spatial distribution of traps is continuously updated by the random walk itself. Despite the geometrical complexity of the territory explored by a random walk, the distribution of the τn can be accounted for by simple analytical expressions. Processes as varied as regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, fall into the same universality classes.

Splitting Probabilities of Symmetric Jump Processes

We derive a universal, exact asymptotic form of the splitting probability for symmetric continuous jump processes, which quantifies the probability π_{0,[under x]_}(x_{0}) that the process crosses x before 0 starting from a given position x_{0}∈[0,x] in the regime x_{0}≪x. This analysis provides in particular a fully explicit determination of the transmission probability (x_{0}=0), in striking contrast with the trivial prediction π_{0,[under x]_}(0)=0 obtained by taking the continuous limit of the process, which reveals the importance of the microscopic properties of the dynamics. These results are illustrated with paradigmatic models of jump processes with applications to light scattering in heterogeneous media in realistic 3D slab geometries. In this context, our explicit predictions of the transmission probability, which can be directly measured experimentally, provide a quantitative characterization of the effective random process describing light scattering in the medium.

Everlasting impact of initial perturbations on first-passage times of non-Markovian random walks

Persistence, defined as the probability that a signal has not reached a threshold up to a given observation time, plays a crucial role in the theory of random processes. Often, persistence decays algebraically with time with non trivial exponents. However, general analytical methods to calculate persistence exponents cannot be applied to the ubiquitous case of non-Markovian systems relaxing transiently after an imposed initial perturbation. Here, we introduce a theoretical framework that enables the non-perturbative determination of persistence exponents of Gaussian non-Markovian processes with non stationary dynamics relaxing to a steady state after an initial perturbation. Two situations are analyzed: either the system is subjected to a temperature quench at initial time, or its past trajectory is assumed to have been observed and thus known. Our theory covers the case of spatial dimension higher than one, opening the way to characterize non-trivial reaction kinetics for complex systems with non-equilibrium initial conditions.

Joint statistics of space and time exploration of one-dimensional random walks

The statistics of first-passage times of random walks to target sites has proved to play a key role in determining the kinetics of space exploration in various contexts. In parallel, the number of distinct sites visited by a random walker and related observables has been introduced to characterize the geometry of space exploration. Here, we address the question of the joint distribution of the first-passage time to a target and the number of distinct sites visited when the target is reached, which fully quantifies the coupling between the kinetics and geometry of search trajectories. Focusing on one-dimensional systems, we present a general method and derive explicit expressions of this joint distribution for several representative examples of Markovian search processes. In addition, we obtain a general scaling form, which holds also for non-Markovian processes and captures the general dependence of the joint distribution on its space and time variables. We argue that the joint distribution has important applications to various problems, such as a conditional form of the Rosenstock trapping model, and the persistence properties of self-interacting random walks.

Cell migration guided by long-lived spatial memory

Living cells actively migrate in their environment to perform key biological functions-from unicellular organisms looking for food to single cells such as fibroblasts, leukocytes or cancer cells that can shape, patrol or invade tissues. Cell migration results from complex intracellular processes that enable cell self-propulsion, and has been shown to also integrate various chemical or physical extracellular signals. While it is established that cells can modify their environment by depositing biochemical signals or mechanically remodelling the extracellular matrix, the impact of such self-induced environmental perturbations on cell trajectories at various scales remains unexplored. Here, we show that cells can retrieve their path: by confining motile cells on 1D and 2D micropatterned surfaces, we demonstrate that they leave long-lived physicochemical footprints along their way, which determine their future path. On this basis, we argue that cell trajectories belong to the general class of self-interacting random walks, and show that self-interactions can rule large scale exploration by inducing long-lived ageing, subdiffusion and anomalous first-passage statistics. Altogether, our joint experimental and theoretical approach points to a generic coupling between motile cells and their environment, which endows cells with a spatial memory of their path and can dramatically change their space exploration.

Universality Classes of Hitting Probabilities of Jump Processes

Quantifying the efficiency of random target search strategies is a key question of random walk theory, with applications in various fields. If many results do exist for recurrent processes, for which the probability of eventually finding a target in infinite space-so called hitting probability-is one, much less is known in the opposite case of transient processes, for which the hitting probability is strictly less than one. Here, we determine the universality classes of the large distance behavior of the hitting probability for general d-dimensional transient jump processes, which we show are parametrized by a transience exponent that is explicitly given.

Sampling first-passage times of fractional Brownian motion using adaptive bisections

We present an algorithm to efficiently sample first-passage times for fractional Brownian motion. To increase the resolution, an initial coarse lattice is successively refined close to the target, by adding exactly sampled midpoints, where the probability that they reach the target is non-negligible. Compared to a path of N equally spaced points, the algorithm achieves the same numerical accuracy N_{eff}, while sampling only a small fraction of all points. Though this induces a statistical error, the latter is bounded for each bridge, allowing us to bound the total error rate by a number of our choice, say P_{error}^{tot}=10^{-6}. This leads to significant improvements in both memory and speed. For H=0.33 and N_{eff}=2^{32}, we need 5000 times less CPU time and 10000 times less memory than the classical Davies-Harte algorithm. The gain grows for H=0.25 and N_{eff}=2^{42} to 3×10^{5} for CPU and 10^{6} for memory. We estimate our algorithmic complexity as C^{ABSec}(N_{eff})=O[(lnN_{eff})^{3}], to be compared to Davies-Harte, which has complexity C^{DH}(N)=O(NlnN). Decreasing P_{error}^{tot} results in a small increase in complexity, proportional to ln(1/P_{error}^{tot}). Our current implementation is limited to the values of N_{eff} given above, due to a loss of floating-point precision. Our algorithm can be adapted to other extreme events and arbitrary Gaussian processes. It enables one to numerically validate theoretical predictions that were hitherto inaccessible.

Inverse Square Lévy Walks are not Optimal Search Strategies for d≥2

The Lévy hypothesis states that inverse square Lévy walks are optimal search strategies because they maximize the encounter rate with sparse, randomly distributed, replenishable targets. It has served as a theoretical basis to interpret a wealth of experimental data at various scales, from molecular motors to animals looking for resources, putting forward the conclusion that many living organisms perform Lévy walks to explore space because of their optimal efficiency. Here we provide analytically the dependence on target density of the encounter rate of Lévy walks for any space dimension d; in particular, this scaling is shown to be independent of the Lévy exponent α for the biologically relevant case d≥2, which proves that the founding result of the Lévy hypothesis is incorrect. As a consequence, we show that optimizing the encounter rate with respect to α is irrelevant: it does not change the scaling with density and can lead virtually to any optimal value of α depending on system dependent modeling choices. The conclusion that observed inverse square Lévy patterns are the result of a common selection process based purely on the kinetics of the search behavior is therefore unfounded.

First Hitting Times to Intermittent Targets

In noisy environments such as the cell, many processes involve target sites that are often hidden or inactive, and thus not always available for reaction with diffusing entities. To understand reaction kinetics in these situations, we study the first hitting time statistics of a one-dimensional Brownian particle searching for a target site that switches stochastically between visible and hidden phases. At high crypticity, an unexpected rate limited power-law regime emerges for the first hitting time density, which markedly differs from the classic t^{-3/2} scaling for steady targets. Our problem admits an asymptotic mapping onto a mixed, or Robin, boundary condition. Similar results are obtained with non-Markov targets and particles diffusing anomalously.

Survival probability of stochastic processes beyond persistence exponents

For many stochastic processes, the probability [Formula: see text] of not-having reached a target in unbounded space up to time [Formula: see text] follows a slow algebraic decay at long times, [Formula: see text]. This is typically the case of symmetric compact (i.e. recurrent) random walks. While the persistence exponent [Formula: see text] has been studied at length, the prefactor [Formula: see text], which is quantitatively essential, remains poorly characterized, especially for non-Markovian processes. Here we derive explicit expressions for [Formula: see text] for a compact random walk in unbounded space by establishing an analytic relation with the mean first-passage time of the same random walk in a large confining volume. Our analytical results for [Formula: see text] are in good agreement with numerical simulations, even for strongly correlated processes such as Fractional Brownian Motion, and thus provide a refined understanding of the statistics of longest first-passage events in unbounded space.