First-Passage Phenomena and Their Applications

The following sections are included:

• Preface
• Contents

We study some of the salient features of the arrival statistics and exploration properties of mortal random walkers, that is, walkers that may die as they move, or as they wait to move. Such evanescence or death events have profound consequences for quantities such as the number of distinct sites visited which are relevant for the computation of encounter-controlled rates in chemical kinetics. We exploit the observation that well-known methods developed decades ago for immortal walkers are widely applicable to mortal walkers. The particular cases of exponential and power-law evanescence are considered in detail. Finally, we discuss the relevance of our results to the target problem with mortal traps and a particular application thereof, namely, the defect diffusion model. Evanescence of defects is postulated as a possible complementary contribution or perhaps even an alternative to anomalous diffusion to explain observed stretched exponential relaxation behavior.

In the random acceleration process, a point particle is accelerated according to , where the right hand side represents Gaussian white noise with zero mean. We begin with the case of a particle with initial position x₀ and initial velocity v₀ and review the statistics of its first arrival at the origin and its first return to the origin. Multiple returns to the origin, motion with a constant force in addition to a random force, and persistence properties for several boundary conditions at the origin are also considered. Next we review first-exit properties of a randomly accelerated particle from the finite interval 0 < x < 1. Then the close connection between the extreme value statistics of a randomly accelerated particle and its first-passage properties is discussed. Finally some applications where first-passage statistics of the random acceleration process play a role are considered.

Many physical and biological systems can be described in terms of a particle undergoing random displacements. When the spread of these particles at long times asymptotically scales as x²(t) ∼ t^2H, with H ≠ 1/2, the walker diffusion is said to be anomalous, as opposed to regular diffusion, which corresponds to plain Brownian motion. Examples of anomalous diffusion emerge for instance when considering the motion of polymers through nanopores, or the percolation of tracer particles in heterogeneous soils. Determining the first-passage properties of such walkers is particularly difficult, because anomalous particles often display long-range correlations and/or wild distributions of time and space increments. Here we will review some relevant examples of anomalous diffusion and show by which mathematical and numerical tools the corresponding first-passage properties can be assessed.

This chapter discusses intermittent target search strategies, which combine phases of slow motion, allowing a searcher to detect a target, and phases of fast motion during which targets cannot be detected. It is first shown that such intermittent random walks are widely observed at various scales, ranging from animals looking for food to the intermittent transport patterns involved in the search for a specific sequence on DNA by a protein. Next, generic stochastic models are introduced, which show that intermittent random walks are efficient strategies that enable the minimization of the mean first-passage time to a target. This suggests that the intrinsic efficiency of intermittent search strategies could justify their frequent observation in nature.

A sequence of strongly inhomogeneous networks, with increasing sizes, can lead to very different thermodynamic limits, depending on the site chosen as the origin. This singular behavior reflects in remarkable phenomena even at finite sizes. Indeed, the finite networks belonging to such sequences, even with a small number of sites, presents significant inhomogeneities in first-passage related quantities, depending on the starting site of the random walker. This kind of behavior is of primary importance for the understanding of diffusion phenomena on real inhomogeneous systems, which are finite and cannot be univocally described by an infinite structure in the thermodynamic limit. Here, we explore the properties of the above mentioned quantities on a collection of the most typical and known inhomogeneous finite networks, both analytically and numerically, evidencing their unique features.

The following sections are included:

• Introduction
• Random walks on regular and disordered lattice in Euclidean space
• Complex networks
• Probability to return to the origin of random walks in scale-free networks
• First passage time probability of random walks in scalefree networks
• Conclusions
• Acknowledgments
• References

We present a general theory which allows one to accurately evaluate the mean FPT (MFPT) for regular random walks in bounded domains, and its extensions to related first-passage observables like splitting probabilities and occupation times. It is showed that this analytical approach provides a universal scaling dependence of the MFPT on both the volume of the confining domain and the source-target distance in the case of general scale invariant processes. This analysis is applicable to a broad range of stochastic processes characterized by scale invariant properties. The full distribution of the FPT can be obtained using similar tools, and displays universal features. This allows to quantify the fluctuations of the FPT in confinement, and to reveal the key role that can be played by the starting position of the random walker.

Fractional Brownian motion is a generalized Gaussian diffusive process that is found to describe numerous stochastic phenomena in physics and biology. Here we introduce a multi-dimensional fractional Brownian motion (FBM) defined as a superposition of conventional FBM for each coordinate in analogy to multi-dimensional Brownian motion, and study its first passage properties. Starting from the well-established first passage time statistics of one-dimensional FBM and the associated approximation schemes, we explore the first passage time behavior of multi-dimensional FBM and compare these results with simulations. The asymptotic kinetic behavior of diffusion-limited reactions of reactant particles performing FBM in a one- and multi-dimensional space is studied based on the corresponding first passage time statistics.

We study the statistics of the first passage of a random walker to absorbing subsets of the boundary of compact domains in different spatial dimensions. We describe a novel diagnostic method to quantify the trajectory-to-trajectory fluctuations of the first passage, based on the distribution of the so-called uniformity index ω, measuring the similarity of the first passage times of two independent walkers starting at the same location. We show that the characteristic shape of P(ω) exhibits a transition from unimodal to bimodal, depending on the starting point of the trajectories. From the study of different geometries in one, two and three dimensions, we conclude that this transition is a generic property of first passage phenomena in bounded domains. Our results show that, in general, the Mean First Passage Time (MFPT) is a meaningful characteristic measure of the first passage behaviour only when the Brownian walkers start sufficiently far from the absorbing boundary. Strikingly, in the opposite case, the first passage statistics exhibit large trajectory-totrajectory fluctuations and the MFPT is not representative of the actual behaviour.

While records and order statistics of independent and identically distributed (i.i.d.) random variables X₁, …, X_N are fully understood, much less is known for strongly correlated random variables, which is often the situation encountered in statistical physics. Recently, it was shown, in a series of works, that one-dimensional random walk (RW) is an interesting laboratory where the influence of strong correlations on records and order statistics can be studied in detail. We review here recent exact results which have been obtained for these questions about RW, using techniques borrowed from the study of first-passage problems. We also present a brief review of the well known (and not so well known) results for records and order statistics of i.i.d. variables.

We survey recent results on first-passage processes in unbounded cones and their applications to ordering of particles undergoing Brownian motion in one dimension. We first discuss the survival probability S(t) that a diffusing particle, in arbitrary spatial dimension, remains inside a conical domain up to time t. In general, this quantity decays algebraically S ∼ t^−β in the long-time limit. The exponent β depends on the opening angle of the cone and the spatial dimension, and it is root of a transcendental equation involving the associated Legendre functions. The exponent becomes a function of a single scaling variable in the limit of large spatial dimension. We then describe two first-passage problems involving the order of N independent Brownian particles in one dimension where survival probabilities decay algebraically as well. To analyze these problems, we identify the trajectories of the N particles with the trajectory of one particle in N dimensions, confined to within a certain boundary, and we use a circular cone with matching solid angle as a replacement for the confining boundary. For N = 3, the confining boundary is a wedge and the approach is exact. In general, this “cone approximation” gives strict lower bounds as well as useful estimates for the first-passage exponents. Interestingly, the cone approximation becomes asymptotically exact when N → ∞ as it predicts the exact scaling function that governs the spectrum of first-passage exponents.

We review recent work on the analysis of first-passage time problems in stochastic hybrid systems. Typically, one or more continuous variables x evolve according to a piecewise deterministic equation of the form , where n labels a set of discrete states. Transitions between these states are governed by a jump Markov process with transition rates that may depend on x. For example, x could represent the membrane voltage of a neuron and n could be the number of open sodium ion channels. Alternatively, x could represent the position of a molecular motor complex on a microtubular track and n could be the internal velocity state of the complex. In the case of a jump process with fast kinetics, a quasi-steady-state diffusion approximation can be performed. However, such an approximation breaks down when considering the escape from a metastable state, and it is necessary to use WKB methods and singular perturbation theory in order to calculate the mean first passage time. The theory is illustrated using the examples of stochastic ion channels and motor-driven intracellular transport.

Applications of first passage times in stochastic processes arise across a wide range of length and time scales in biological settings. After an initial technical overview, we survey representative applications and their corresponding models. Within models that are effectively Markovian, we discuss canonical examples of first passage problems spanning applications to molecular dissociation and self-assembly, molecular search, transcription and translation, neuronal spiking, cellular mutation and disease, and organismic evolution and population dynamics. In this last application, a simple model for stem-cell aging is presented and some results derived. Various approximation methods and the physical and mathematical subtleties that arise in the chosen applications are also discussed.

The following sections are included:

• Introduction
• The non-perfect detection problem
• Detection mechanisms in velocity models
• Conclusions
• Acknowledgements
• References

The following sections are included:

• Introduction and motivation
• Modelling the search process
• A transform approach when k out of N searchers must be successful
• Search in a non-homogeneous medium
• Future work
• References

Visual search is the study of how humans find desired objects in their visual environment. I provide brief outline of work on visual search, and then describe work on specific topics such as the effects of target prevalence and visual foraging.

Random walks on multidimensional landscapes are important to many areas of science and engineering. In particular, properties of adaptive first-passage trajectories on fitness landscapes determine population fates and thus play a central role in evolutionary biology. The topography of fitness landscapes and its effect on evolutionary dynamics have been extensively studied in the literature. We will survey the current knowledge in this field, focusing on a recently developed systematic approach to characterizing path lengths, mean times, and other statistics of the first-passage path ensemble. This approach, based on general techniques from statistical physics, is applicable to landscapes of arbitrary complexity and structure. It is especially well-suited to quantifying the diversity of stochastic trajectories and repeatability of evolutionary events. We demonstrate this methodology using a biophysical model of protein evolution that describes how proteins maintain folding stability while evolving new functions.

Many problems in finance are related to first passage times. Among all of them, we chose three on which we contributed personally. Our first example relates Kolmogorov-Smirnov like goodness-of-fit tests, modified in such a way that tail events and core events contribute equally to the test (in the standard Kolmogorov-Smirnov, the tails contribute very little to the measure of goodness-of-fit). We show that this problem can be mapped onto that of a random walk inside moving walls. The second example is the optimal time to sell an asset (modelled as a random walk with drift) such that the sell time is as close as possible to the time at which the asset reaches its maximum value. The last example concerns optimal trading in the presence of transaction costs. In this case, the optimal strategy is to wait until the predictor reaches (plus or minus) a threshold value before buying or selling. The value of this threshold is found by mapping the problem onto that of a random walk between two walls.

We present an introduction to level-crossing problems aimed to applications in socio-economic systems. We summarize the general theory of first-passage and exit problems and apply it to diffusions, random diffusions and discontinuous random walks. Some results regarding financial problems, especially related to dangerous fluctuations and risk control are also briefly discussed.

Measurements of spatial diffusion of cold atoms in optical lattices have revealed anomalous super-diffusion, which is controlled by the depth of the optical lattice. We use first passage time statistics to derive the diffusion front of the atoms. In particular, the distributions of areas swept under the first passage curve till its first arrival, and of areas under the Bessel excursion are shown to be powerful tools in the analysis of the atomic cloud. A rather general relation between first passage time statistics and diffusivity is discussed, showing that first passage time analysis is a useful tool in the calculation of transport coefficients. A brief introduction to the semi-classical description of Sisyphus cooling is provided which yields a rich phase diagram for the dynamics.

Understanding the formation of large-scale structures in the Universe is a central problem of modern cosmology. A key element is the formation of dark matter halos, which provide the gravitational potential wells where galaxies and galaxy clusters will later form. The process of formation of dark matter halos via gravitational instability can be formulated as a first-passage time problem, in which one studies the evolution of the smoothed density fluctuations with respect to the smoothing scale, and halo formation takes place when a given barrier is hit. We review this classic approach to halo formation, as well as recent developments in which this first-passage time problem is reformulated in terms of a path integral, which also allows us to include non-markovianity effect intrinsic to the physics of halo formation. This application also provides a vivid example of the generality and elegance of statistical tools such as first-passage time theory.

An enhancement of localized nonlinear modes in coupled systems gives rise to a novel type of escape process. We study a spatially one dimensional set-up consisting of a linearly coupled oscillator chain of N mass-points situated in a metastable nonlinear potential. The Hamilton-dynamics exhibits breather solutions as a result of modulational instability of the phonon states. These breathers localize energy by freezing other parts of the chain. Eventually this localised part of the chain grows in amplitude until it overcomes the critical elongation characterized by the transition state. Doing so, the breathers ignite an escape by pulling the remaining chain over the barrier. Even if the formation of singular breathers is insufficient for an escape, coalescence of moving breathers can result in the required concentration of energy. Compared to a chain system with linear damping and thermal fluctuations the breathers help the chain to overcome the barriers faster in the case of low damping. With larger damping, the decreasing life time of the breathers effectively inhibites the escape process.

We present the principles, mathematical bases, numerical shortcuts and applications of fast random walk (FRW) algorithms. This Monte Carlo technique allows one to simulate individual trajectories of diffusing particles in order to study various probabilistic characteristics (harmonic measure, first passage/exit time distribution, reaction rates, search times and strategies, etc.) and to solve the related partial differential equations. The adaptive character and flexibility of FRWs make them particularly efficient for simulating diffusive processes in porous, multiscale, heterogeneous, disordered or irregularly-shaped media.