Optimal search strategies of space-time coupled random walkers with finite lifetimes

Dynamic redundancy as a mechanism to optimize collective random searches

We explore the case of a group of random walkers looking for a target randomly located in space, such that the number of walkers is not constant but new ones can join the search, or those that are active can abandon it, with constant rates r_{b} and r_{d}, respectively. Exact analytical solutions are provided both for the fastest-first-passage time and for the collective time cost required to reach the target, for the exemplifying case of Brownian walkers with r_{d}=0. We prove that even for such a simple situation there exists an optimal rate r_{b} at which walkers should join the search to minimize the collective search costs. We discuss how these results open a new line to understand the optimal regulation in searches conducted through multiparticle random walks, e.g., in chemical or biological processes.

Constructing efficient strategies for the process optimization by restart

Optimization of the mean completion time of random processes by restart is a subject of active theoretical research in statistical physics and has long found practical application in computer science. Meanwhile, one of the key issues remains largely unsolved: how to construct a restart strategy for a process whose detailed statistics are unknown to ensure that the expected completion time will reduce? Addressing this query here we propose several constructive criteria for the effectiveness of various protocols of noninstantaneous restart in the mean completion time problem and in the success probability problem. Being expressed in terms of a small number of easily estimated statistical characteristics of the original process (MAD, median completion time, low-order statistical moments of completion time), these criteria allow informed restart decision based on partial information.

Bernoulli trial under restarts: A comparative study of resetting transitions

A Bernoulli trial describing the escape behavior of a lamb to a safe haven in pursuit by a lion is studied under restarts. The process ends in two ways: either the lamb makes it to the safe haven (success) or is captured by the lion (failure). We study the first passage properties of this Bernoulli trial and find that only mean first passage time exists. Considering Poisson and sharp resetting, we find that the success probability is a monotonically decreasing function of the restart rate. The mean time, however, exhibits a nonmonotonic dependence on the restart rate taking a minimal value at an optimal restart rate. Furthermore, for sharp restart, the mean time possesses a local and a global minima. As a result, the optimal restart rate exhibits a continuous transition for Poisson resetting while it exhibits a discontinuous transition for sharp resetting as a function of the relative separation of the lion and the lamb. We also find that the distribution of first passage times under sharp resetting exhibits a periodic behavior.

Effects of mortality on stochastic search processes with resetting

We study the first-passage time to the origin of a mortal Brownian particle, with mortality rate μ, diffusing in one dimension. The particle starts its motion from x>0 and it is subject to stochastic resetting with constant rate r. We first unveil the relation between the probability of reaching the target and the mean first-passage time of the corresponding problem in absence of mortality, which allows us to deduce under which conditions the former can be increased by adjusting the restart rate. We then consider the first-passage time conditioned on the event that the particle reaches the target before dying, and provide exact expressions for the mean and the variance as functions of r, corroborated by numerical simulations. By studying the impact of resetting for different mortality regimes, we also show that, if the average lifetime τ_{μ}=1/μ is long enough with respect to the diffusive time scale τ_{D}=x^{2}/(4D), there exist both a resetting rate r_{μ}^{*} that maximizes the probability and a rate r_{m} that minimizes the mean first-passage time. However, the two never coincide for positive μ, making the optimization problem highly nontrivial.

Optimal escape-and-feeding dynamics of random walkers: Rethinking the convenience of ballistic strategies

Excited random walks represent a convenient model to study food intake in a media which is progressively depleted by the walker. Trajectories in the model alternate between (i) feeding and (ii) escape (when food is missed and so it must be found again) periods, each governed by different movement rules. Here, we explore the case where the escape dynamics is adaptive, so at short times an area-restricted search is carried out, and a switch to extensive or ballistic motion occurs later if necessary. We derive for this case explicit analytical expressions of the mean escape time and the asymptotic growth of the depleted region in one dimension. These, together with numerical results in two dimensions, provide surprising evidence that ballistic searches are detrimental in such scenarios, a result which could explain why ballistic movement is barely observed in animal searches at microscopic and millimetric scales, therefore providing significant implications for biological foraging.

Hitting times in turbulent diffusion due to multiplicative noise

We study a distribution of times of the first arrivals to absorbing targets in turbulent diffusion, which is due to a multiplicative noise. Two examples of dynamical systems with a multiplicative noise are studied. The first one is a random process according to inhomogeneous diffusion, which is also known as a geometric Brownian motion in the Black-Scholes model. The second model is due to a random processes on a two-dimensional comb, where inhomogeneous advection is possible only along the backbone, while Brownian diffusion takes place inside the branches. It is shown that in both cases turbulent diffusion takes place as the one-dimensional random process with the log-normal distribution in the presence of absorbing targets, which are characterized by the Lévy-Smirnov distribution for the first hitting times.

Getting around the cell: physical transport in the intracellular world

Eukaryotic cells face the challenging task of transporting a variety of particles through the complex intracellular milieu in order to deliver, distribute, and mix the many components that support cell function. In this review, we explore the biological objectives and physical mechanisms of intracellular transport. Our focus is on cytoplasmic and intra-organelle transport at the whole-cell scale. We outline several key biological functions that depend on physically transporting components across the cell, including the delivery of secreted proteins, support of cell growth and repair, propagation of intracellular signals, establishment of organelle contacts, and spatial organization of metabolic gradients. We then review the three primary physical modes of transport in eukaryotic cells: diffusive motion, motor-driven transport, and advection by cytoplasmic flow. For each mechanism, we identify the main factors that determine speed and directionality. We also highlight the efficiency of each transport mode in fulfilling various key objectives of transport, such as particle mixing, directed delivery, and rapid target search. Taken together, the interplay of diffusion, molecular motors, and flows supports the intracellular transport needs that underlie a broad variety of biological phenomena.

Search processes with stochastic resetting and multiple targets

Search processes with stochastic resetting provide a general theoretical framework for understanding a wide range of naturally occurring phenomena. Most current models focus on the first-passage-time problem of finding a single target in a given search domain. Here we use a renewal method to derive general expressions for the splitting probabilities and conditional mean first passage times (MFPTs) in the case of multiple targets. Our analysis also incorporates the effects of delays arising from finite return times and refractory periods. Carrying out a small-r expansion, where r is the mean resetting rate, we obtain general conditions for when resetting increases the splitting probability or reduces the conditional MFPT to a particular target. This also depends on whether π_{tot}=1 or π_{tot}<1, where π_{tot} is the probability that the particle is eventually absorbed by one of the targets in the absence of resetting. We illustrate the theory by considering two distinct examples. The first consists of an actin-rich cell filament (cytoneme) searching along a one-dimensional array of target cells, a problem for which the splitting probabilities and MFPTs can be calculated explicitly. In particular, we highlight how the resetting rate plays an important role in shaping the distribution of splitting probabilities along the array. The second example involves a search process in a three-dimensional bounded domain containing a set of N small interior targets. We use matched asymptotics and Green's functions to determine the behavior of the splitting probabilities and MFPTs in the small-r regime. In particular, we show that the splitting probabilities and MFPTs depend on the "shape capacitance" of the targets.

Queueing theory of search processes with stochastic resetting

We use queueing theory to develop a general framework for analyzing search processes with stochastic resetting, under the additional assumption that following absorption by a target, the particle (searcher) delivers a packet of resources to the target and the search process restarts at the reset point x_{r}. This leads to a sequence of search-and-capture events, whereby resources accumulate in the target under the combined effects of resource supply and degradation. Combining the theory of G/M/∞ queues with a renewal method for analyzing resetting processes, we derive general expressions for the mean and variance of the number of resource packets within the target at steady state. These expressions apply to both exponential and nonexponential resetting protocols and take into account delays arising from various factors such as finite return times, refractory periods, and delays due to the loading or unloading of resources. In the case of exponential resetting, we show how the resource statistics can be expressed in terms of the MFPTs T_{r}(x_{r}) and T_{r+γ}(x_{r}), where r is the resetting rate and γ is the degradation rate. This allows us to derive various general results concerning the dependence of the mean and variance on the parameters r,γ. Our results are illustrated using several specific examples. Finally, we show how fluctuations can be reduced either by allowing the delivery of multiple packets that degrade independently or by having multiple independent searchers.

Persistent random motion with maximally correlated fluctuations

How often should a random walker change its direction of motion in order to maximize correlation in velocity fluctuations over a finite time interval? We address this optimal diffusion problem in the context of the one-dimensional persistent random walk, where we evaluate the correlation and mutual information in velocity trajectories as a function of the persistence level and the observation time. We find the optimal persistence level corresponds to the average number of direction reversals asymptotically scaling as the square root of the observation time. This square-root scaling law makes the relative growth between the average number of direction reversals and the persistence length invariant with respect to changes in the overall time duration of the random walk.

First-passage properties of mortal random walks: Ballistic behavior, effective reduction of dimensionality, and scaling functions for hierarchical graphs

We consider a mortal random walker on a family of hierarchical graphs in the presence of some trap sites. The configuration comprising the graph, the starting point of the walk, and the locations of the trap sites is taken to be exactly self-similar as one goes from one generation of the family to the next. Under these circumstances, the total probability that the walker hits a trap is determined exactly as a function of the single-step survival probability q of the mortal walker. On the nth generation graph of the family, this probability is shown to be given by the nth iterate of a certain scaling function or map q→f(q). The properties of the map then determine, in each case, the behavior of the trapping probability, the mean time to trapping, the temporal scaling factor governing the random walk dimension on the graph, and other related properties. The formalism is illustrated for the cases of a linear hierarchical lattice and the Sierpinski graphs in two and three Euclidean dimensions. We find an effective reduction of the random walk dimensionality due to the ballistic behavior of the surviving particles induced by the mortality constraint. The relevance of this finding for experiments involving travel times of particles in diffusion-decay systems is discussed.

Multimodal transport and dispersion of organelles in narrow tubular cells

Intracellular components explore the cytoplasm via active motor-driven transport in conjunction with passive diffusion. We model the motion of organelles in narrow tubular cells using analytical techniques and numerical simulations to study the efficiency of different transport modes in achieving various cellular objectives. Our model describes length and time scales over which each transport mode dominates organelle motion, along with various metrics to quantify exploration of intracellular space. For organelles that search for a specific target, we obtain the average capture time for given transport parameters and show that diffusion and active motion contribute to target capture in the biologically relevant regime. Because many organelles have been found to tether to microtubules when not engaged in active motion, we study the interplay between immobilization due to tethering and increased probability of active transport. We derive parameter-dependent conditions under which tethering enhances long-range transport and improves the target capture time. These results shed light on the optimization of intracellular transport machinery and provide experimentally testable predictions for the effects of transport regulation mechanisms such as tethering.

Nonstationary dynamics of encounters: Mean valuable territory covered by a random searcher

Inspired by recent experiments on the organism Caenorhabditis elegans we present a stochastic problem to capture the adaptive dynamics of search in living beings, which involves the exploration-exploitation dilemma between remaining in a previously preferred area and relocating to new places. We assess the question of search efficiency by introducing a new magnitude, the mean valuable territory covered by a Browinan searcher, for the case where each site in the domain becomes valuable only after a random time controlled by a nonhomogeneous rate which expands from the origin outwards. We explore analytically this magnitude for domains of dimensions 1, 2, and 3 and discuss the theoretical and applied (biological) interest of our approach. As the main results here, we (i) report the existence of some universal scaling properties for the mean valuable territory covered as a function of time and (ii) reveal the emergence of an optimal diffusivity which appears only for domains in two and higher dimensions.

Continuous-time random-walk model for anomalous diffusion in expanding media

Expanding media are typical in many different fields, e.g., in biology and cosmology. In general, a medium expansion (contraction) brings about dramatic changes in the behavior of diffusive transport properties such as the set of positional moments and the Green's function. Here, we focus on the characterization of such effects when the diffusion process is described by the continuous-time random-walk (CTRW) model. As is well known, when the medium is static this model yields anomalous diffusion for a proper choice of the probability density function (pdf) for the jump length and the waiting time, but the behavior may change drastically if a medium expansion is superimposed on the intrinsic random motion of the diffusing particle. For the case where the jump length and the waiting time pdfs are long-tailed, we derive a general bifractional diffusion equation which reduces to a normal diffusion equation in the appropriate limit. We then study some particular cases of interest, including Lévy flights and subdiffusive CTRWs. In the former case, we find an analytical exact solution for the Green's function (propagator). When the expansion is sufficiently fast, the contribution of the diffusive transport becomes irrelevant at long times and the propagator tends to a stationary profile in the comoving reference frame. In contrast, for a contracting medium a competition between the spreading effect of diffusion and the concentrating effect of contraction arises. In the specific case of a subdiffusive CTRW in an exponentially contracting medium, the latter effect prevails for sufficiently long times, and all the particles are eventually localized at a single point in physical space. This "big crunch" effect, totally absent in the case of normal diffusion, stems from inefficient particle spreading due to subdiffusion. We also derive a hierarchy of differential equations for the moments of the transport process described by the subdiffusive CTRW model in an expanding medium. From this hierarchy, the full time evolution of the second-order moment is obtained for some specific types of expansion. In the case of an exponential expansion, exact recurrence relations for the Laplace-transformed moments are obtained, whence the long-time behavior of moments of arbitrary order is subsequently inferred. Our analytical and numerical results for both Lévy flights and subdiffusive CTRWs confirm the intuitive expectation that the medium expansion hinders the mixing of diffusive particles occupying separate regions. In the case of Lévy flights, we quantify this effect by means of the so-called "Lévy horizon."

Online games: a novel approach to explore how partial information influences human random searches

Many natural processes rely on optimizing the success ratio of a search process. We use an experimental setup consisting of a simple online game in which players have to find a target hidden on a board, to investigate how the rounds are influenced by the detection of cues. We focus on the search duration and the statistics of the trajectories traced on the board. The experimental data are explained by a family of random-walk-based models and probabilistic analytical approximations. If no initial information is given to the players, the search is optimized for cues that cover an intermediate spatial scale. In addition, initial information about the extension of the cues results, in general, in faster searches. Finally, strategies used by informed players turn into non-stationary processes in which the length of e ach displacement evolves to show a well-defined characteristic scale that is not found in non-informed searches.

Foraging success under uncertainty: search tradeoffs and optimal space use

Understanding the structural complexity and the main drivers of animal search behaviour is pivotal to foraging ecology. Yet, the role of uncertainty as a generative mechanism of movement patterns is poorly understood. Novel insights from search theory suggest that organisms should collect and assess new information from the environment by producing complex exploratory strategies. Based on an extension of the first passage time theory, and using simple equations and simulations, we unveil the elementary heuristics behind search behaviour. In particular, we show that normal diffusion is not enough for determining optimal exploratory behaviour but anomalous diffusion is required. Searching organisms go through two critical sequential phases (approach and detection) and experience fundamental search tradeoffs that may limit their encounter rates. Using experimental data, we show that biological search includes elements not fully considered in contemporary physical search theory. In particular, the need to consider search movement as a non-stationary process that brings the organism from one informational state to another. For example, the transition from remaining in an area to departing from it may occur through an exploratory state where cognitive search is challenged. Therefore, a more comprehensive view of foraging ecology requires including current perspectives about movement under uncertainty.

Optimal search strategies of run-and-tumble walks

The run-and-tumble walk, consisting of randomly reoriented ballistic excursions, models phenomena ranging from gas kinetics to bacteria motility. We evaluate the mean time required for this walk to find a fixed target within a two- or three-dimensional spherical confinement. We find that the mean search time admits a minimum as a function of the mean run duration for various types of boundary conditions and run duration distributions (exponential, power-law, deterministic). Our result stands in sharp contrast to the pure ballistic motion, which is predicted to be the optimal search strategy in the case of Poisson-distributed targets.

Phase transitions in optimal search times: How random walkers should combine resetting and flight scales

Recent works have explored the properties of Lévy flights with resetting in one-dimensional domains and have reported the existence of phase transitions in the phase space of parameters which minimizes the mean first passage time (MFPT) through the origin [L. Kusmierz et al., Phys. Rev. Lett. 113, 220602 (2014)]. Here, we show how actually an interesting dynamics, including also phase transitions for the minimization of the MFPT, can also be obtained without invoking the use of Lévy statistics but for the simpler case of random walks with exponentially distributed flights of constant speed. We explore this dynamics both in the case of finite and infinite domains, and for different implementations of the resetting mechanism to show that different ways to introduce resetting consistently lead to a quite similar dynamics. The use of exponential flights has the strong advantage that exact solutions can be obtained easily for the MFPT through the origin, so a complete analytical characterization of the system dynamics can be provided. Furthermore, we discuss in detail how the phase transitions observed in random walks with resetting are closely related to several ideas recurrently used in the field of random search theory, in particular, to other mechanisms proposed to understand random search in space as mortal random walks or multiscale random walks. As a whole, we corroborate that one of the essential ingredients behind MFPT minimization lies in the combination of multiple movement scales (regardless of their specific origin).

First-passage times in multiscale random walks: The impact of movement scales on search efficiency

An efficient searcher needs to balance properly the trade-off between the exploration of new spatial areas and the exploitation of nearby resources, an idea which is at the core of scale-free Lévy search strategies. Here we study multiscale random walks as an approximation to the scale-free case and derive the exact expressions for their mean-first-passage times in a one-dimensional finite domain. This allows us to provide a complete analytical description of the dynamics driving the situation in which both nearby and faraway targets are available to the searcher, so the exploration-exploitation trade-off does not have a trivial solution. For this situation, we prove that the combination of only two movement scales is able to outperform both ballistic and Lévy strategies. This two-scale strategy involves an optimal discrimination between the nearby and faraway targets which is only possible by adjusting the range of values of the two movement scales to the typical distances between encounters. So, this optimization necessarily requires some prior information (albeit crude) about target distances or distributions. Furthermore, we found that the incorporation of additional (three, four, …) movement scales and its adjustment to target distances does not improve further the search efficiency. This allows us to claim that optimal random search strategies arise through the informed combination of only two walk scales (related to the exploitative and the explorative scales, respectively), expanding on the well-known result that optimal strategies in strictly uninformed scenarios are achieved through Lévy paths (or, equivalently, through a hierarchical combination of multiple scales).