Universality classes of first-passage-time distribution in confined media

First-passage times to a fractal boundary: Local persistence exponent and its log-periodic oscillations

We investigate the statistics of the first-passage time (FPT) to a fractal self-similar boundary of the Koch snowflake. When the starting position is fixed near the absorbing boundary, the FPT distribution exhibits an apparent power-law decay over a broad range of timescales, culminated by an exponential cutoff. By extensive Monte Carlo simulations, we compute the local persistence exponent of the survival probability and reveal its log-periodic oscillations in time due to self-similarity of the boundary. The effect of the starting point on this behavior is analyzed in depth. Theoretical bounds on the survival probability are derived from the analysis of diffusion in a circular sector. Physical rationales for the refined structure of the survival probability are presented.

Understanding and Quantifying Network Robustness to Stochastic Inputs

A variety of biomedical systems are modeled by networks of deterministic differential equations with stochastic inputs. In some cases, the network output is remarkably constant despite a randomly fluctuating input. In the context of biochemistry and cell biology, chemical reaction networks and multistage processes with this property are called robust. Similarly, the notion of a forgiving drug in pharmacology is a medication that maintains therapeutic effect despite lapses in patient adherence to the prescribed regimen. What makes a network robust to stochastic noise? This question is challenging due to the many network parameters (size, topology, rate constants) and many types of noisy inputs. In this paper, we propose a summary statistic to describe the robustness of a network of linear differential equations (i.e. a first-order mass-action system). This statistic is the variance of a certain random walk passage time on the network. This statistic can be quickly computed on a modern computer, even for complex networks with thousands of nodes. Furthermore, we use this statistic to prove theorems about how certain network motifs increase robustness. Importantly, our analysis provides intuition for why a network is or is not robust to noise. We illustrate our results on thousands of randomly generated networks with a variety of stochastic inputs.

Controlling Uncertainty of Empirical First-Passage Times in the Small-Sample Regime

We derive general bounds on the probability that the empirical first-passage time τ[over ¯]_{n}≡∑_{i=1}^{n}τ_{i}/n of a reversible ergodic Markov process inferred from a sample of n independent realizations deviates from the true mean first-passage time by more than any given amount in either direction. We construct nonasymptotic confidence intervals that hold in the elusive small-sample regime and thus fill the gap between asymptotic methods and the Bayesian approach that is known to be sensitive to prior belief and tends to underestimate uncertainty in the small-sample setting. We prove sharp bounds on extreme first-passage times that control uncertainty even in cases where the mean alone does not sufficiently characterize the statistics. Our concentration-of-measure-based results allow for model-free error control and reliable error estimation in kinetic inference, and are thus important for the analysis of experimental and simulation data in the presence of limited sampling.

Universal cover-time distribution of heterogeneous random walks

The cover-time problem, i.e., the time to visit every site in a system, is one of the key issues of random walks with wide applications in natural, social, and engineered systems. Addressing the full distribution of cover times for random walk on complex structures has been a long-standing challenge and has attracted persistent efforts. Usually it is assumed that the random walk is noncompact, to facilitate theoretical treatments by neglecting the correlations between visits. The known results are essentially limited to noncompact and homogeneous systems, where different sites are on an equal footing and have identical or close mean first-passage times, such as random walks on a torus. In contrast, realistic random walks are prevailingly heterogeneous with diversified mean first-passage times. Does a universal distribution still exist? Here, by considering the most general situations of noncompact random walks, we uncover a generalized rescaling relation for the cover time, exploiting the diversified mean first-passage times that have not been accounted for before. This allows us to concretely establish a universal distribution of the rescaled cover times for heterogeneous noncompact random walks, which turns out to be the Gumbel universality class that is ubiquitous for a large family of extreme value statistics. Our analysis is based on the transfer matrix framework, which is generic in that, besides heterogeneity, it is also robust against biased protocols, directed links, and self-connecting loops. The finding is corroborated with extensive numerical simulations of diverse heterogeneous noncompact random walks on both model and realistic topological structures. Our technical ingredient may be exploited for other extreme value or ergodicity problems with nonidentical distributions.

Diffusive exit rates through pores in membrane-enclosed structures

The function of many membrane-enclosed intracellular structures relies on release of diffusing particles that exit through narrow pores or channels in the membrane. The rate of release varies with pore size, density, and length of the channel. We propose a simple approximate model, validated with stochastic simulations, for estimating the effective release rate from cylinders, and other simple-shaped domains, as a function of channel parameters. The results demonstrate that, for very small pores, a low density of channels scattered over the boundary is sufficient to achieve substantial rates of particle release. Furthermore, we show that increasing the length of passive channels will both reduce release rates and lead to a less steep dependence on channel density. Our results are compared to previously-measured local calcium release rates from tubules of the endoplasmic reticulum, providing an estimate of the relevant channel density responsible for the observed calcium efflux.

Theoretical insights into the full description of DNA target search by subdiffusing proteins

DNA binding proteins (DBPs) diffuse in the cytoplasm to recognise and bind with their respective target sites on the DNA to initiate several biologically important processes. The first passage time distributions (FPTDs) of DBPs are useful in quantifying the timescales of the most-probable search paths in addition to the mean value of the distribution which, strikingly, are decades of order apart in time. However, extremely crowded in vivo conditions or the viscoelasticity of the cellular medium among other factors causes biomolecules to exhibit anomalous diffusion which is usually overlooked in most theoretical studies. We have obtained approximate analytical expressions of a general FPTD and the two characteristic timescales that are valid for any single subdiffusing protein searching for its target in vivo. Our results can be applied to single-particle tracking experiments of target search.

Boundary homogenization for trapping patchy particles

Many systems in chemical and biological physics involve diffusing particles being trapped by absorbing patches on otherwise reflecting surfaces. Such systems are commonly studied by boundary homogenization, in which the heterogenous boundary condition on the patchy surface is replaced by a uniform boundary condition involving a single parameter which encapsulates the effective trapping properties of the surface. In prior works on boundary homogenization, the surface is patchy and the diffusing particles are homogeneous. In this paper, we consider the opposite scenario in which a homogenous surface traps patchy particles, which could model proteins with localized binding sites, cells with membrane receptors, or patchy colloids or nanoparticles. We derive an explicit formula for the effective trapping rate which reveals a fundamental interplay between the translational and rotational diffusivities of the patchy particle, a phenomenon not typically seen in boundary homogenization. Motivated by receptors on the cell membrane, our analysis also allows for the possibility that the patches diffuse on the surface of the particle. We formulate the system in terms of a high-dimensional, time-dependent, anisotropic diffusion equation and employ matched asymptotic analysis to derive the effective trapping rate. We confirm our results by detailed numerical simulations.

Exact results for the first-passage properties in a class of fractal networks

In this work, we consider a class of recursively grown fractal networks G_n(t) whose topology is controlled by two integer parameters, t and n. We first analyse the structural properties of G_n(t) (including fractal dimension, modularity, and clustering coefficient), and then we move to its transport properties. The latter are studied in terms of first-passage quantities (including the mean trapping time, the global mean first-passage time, and Kemeny's constant), and we highlight that their asymptotic behavior is controlled by the network's size and diameter. Remarkably, if we tune n (or, analogously, t) while keeping the network size fixed, as n increases (t decreases) the network gets more and more clustered and modular while its diameter is reduced, implying, ultimately, a better transport performance. The connection between this class of networks and models for polymer architectures is also discussed.

Universal first-passage statistics in aging media

It has been known for a long time that the kinetics of diffusion-limited reactions can be quantified by the time needed for a diffusing molecule to reach a target: the first-passage time (FPT). So far the general determination of the mean first-passage time to a target in confinement has left aside aging media, such as glassy materials, cellular media, or cold atoms in optical lattices. Here we consider general non-Markovian scale-invariant diffusion processes, which model a broad class of transport processes of molecules in aging media, and demonstrate that all the moments of the FPT obey universal scalings with the confining volume with nontrivial exponents. Our analysis shows that a nonlinear scaling with the volume of the mean FPT, which quantities the mean reaction time, is the hallmark of aging and provides a general tool to quantify its impact on reaction kinetics in confinement.

Analysis of fluctuations in the first return times of random walks on regular branched networks

The first return time (FRT) is the time it takes a random walker to first return to its original site, and the global first passage time (GFPT) is the first passage time for a random walker to move from a randomly selected site to a given site. We find that in finite networks, the variance of FRT, Var(FRT), can be expressed as Var(FRT) = 2⟨FRT⟩⟨GFPT⟩ - ⟨FRT⟩² - ⟨FRT⟩, where ⟨·⟩ is the mean of the random variable. Therefore a method of calculating the variance of FRT on general finite networks is presented. We then calculate Var(FRT) and analyze the fluctuation of FRT on regular branched networks (i.e., Cayley tree) by using Var(FRT) and its variant as the metric. We find that the results differ from those in such other networks as Sierpinski gaskets, Vicsek fractals, T-graphs, pseudofractal scale-free webs, (u, v) flowers, and fractal and non-fractal scale-free trees.

Scaling laws for diffusion on (trans)fractal scale-free networks

Fractal (or transfractal) features are common in real-life networks and are known to influence the dynamic processes taking place in the network itself. Here, we consider a class of scale-free deterministic networks, called (u, v)-flowers, whose topological properties can be controlled by tuning the parameters u and v; in particular, for u > 1, they are fractals endowed with a fractal dimension df, while for u = 1, they are transfractal endowed with a transfractal dimension d̃_f. In this work, we investigate dynamic processes (i.e., random walks) and topological properties (i.e., the Laplacian spectrum) and we show that, under proper conditions, the same scalings (ruled by the related dimensions) emerge for both fractal and transfractal dimensions.

Dynamics of comb-of-comb networks

The dynamics of complex networks, a current hot topic in many scientific fields, is often coded through the corresponding Laplacian matrix. The spectrum of this matrix carries the main features of the networks' dynamics. Here we consider the deterministic networks which can be viewed as "comb-of-comb" iterative structures. For their Laplacian spectra we find analytical equations involving Chebyshev polynomials whose properties allow one to analyze the spectra in deep. Here, in particular, we find that in the infinite size limit the corresponding spectral dimension goes as d(s) → 2. The d(s) leaves its fingerprint on many dynamical processes, as we exemplarily show by considering the dynamical properties of polymer networks, including single monomer displacement under a constant force, mechanical relaxation, and fluorescence depolarization.

Sample-dependent first-passage-time distribution in a disordered medium

Above two dimensions, diffusion of a particle in a medium with quenched random traps is believed to be well described by the annealed continuous-time random walk. We propose an approximate expression for the first-passage-time (FPT) distribution in a given sample that enables detailed comparison of the two problems. For a system of finite size, the number and spatial arrangement of deep traps yield significant sample-to-sample variations in the FPT statistics. Numerical simulations of a quenched trap model with power-law sojourn times confirm the existence of two characteristic time scales and a non-self-averaging FPT distribution, as predicted by our theory.

Exact calculations of first-passage properties on the pseudofractal scale-free web

In this paper, we consider discrete time random walks on the pseudofractal scale-free web (PSFW) and we study analytically the related first passage properties. First, we classify the nodes of the PSFW into different levels and propose a method to derive the generation function of the first passage probability from an arbitrary starting node to the absorbing domain, which is located at one or more nodes of low-level (i.e., nodes with large degree). Then, we calculate exactly the first passage probability, the survival probability, the mean, and the variance of first passage time by using the generating functions as a tool. Finally, for some illustrative examples corresponding to given choices of starting node and absorbing domain, we derive exact and explicit results for such first passage properties. The method we propose can as well address the cases where the absorbing domain is located at one or more nodes of high-level on the PSFW, and it can also be used to calculate the first passage properties on other networks with self-similar structure, such as (u, v) flowers and recursive scale-free trees.

Survival probability of a Brownian motion in a planar wedge of arbitrary angle

We study the survival probability and the first-passage time distribution for a Brownian motion in a planar wedge with infinite absorbing edges. We generalize existing results obtained for wedge angles of the form π/n with n a positive integer to arbitrary angles, which in particular cover the case of obtuse angles. We give explicit and simple expressions of the survival probability and the first-passage time distribution in which the difference between an arbitrary angle and a submultiple of π is contained in three additional terms. As an application, we obtain the short-time development of the survival probability in a wedge of arbitrary angle.

Blind and myopic ants in heterogeneous networks

The diffusion processes on complex networks may be described by different Laplacian matrices due to heterogeneous connectivity. Here we investigate the random walks of blind ants and myopic ants on heterogeneous networks: While a myopic ant hops to a neighbor node every step, a blind ant may stay or hop with probabilities that depend on node connectivity. By analyzing the trajectories of blind ants, we show that the asymptotic behaviors of both random walks are related by rescaling time and probability with node connectivity. Using this result, we show how the small eigenvalues of the Laplacian matrices generating the two random walks are related. As an application, we show how the return-to-origin probability of a myopic ant can be used to compute the scaling behaviors of the Edwards-Wilkinson model, a representative model of load balancing on networks.

Fast algorithm for relaxation processes in big-data systems

Relaxation processes driven by a Laplacian matrix can be found in many real-world big-data systems, for example, in search engines on the World Wide Web and the dynamic load-balancing protocols in mesh networks. To numerically implement such processes, a fast-running algorithm for the calculation of the pseudoinverse of the Laplacian matrix is essential. Here we propose an algorithm which computes quickly and efficiently the pseudoinverse of Markov chain generator matrices satisfying the detailed-balance condition, a general class of matrices including the Laplacian. The algorithm utilizes the renormalization of the Gaussian integral. In addition to its applicability to a wide range of problems, the algorithm outperforms other algorithms in its ability to compute within a manageable computing time arbitrary elements of the pseudoinverse of a matrix of size millions by millions. Therefore our algorithm can be used very widely in analyzing the relaxation processes occurring on large-scale networked systems.

Accelerating search kinetics by following boundaries

We derive exact expressions of the mean first-passage time to a bulk target for a random searcher that performs boundary-mediated diffusion in a circular domain. Although nonintuitive for bulk targets, it is found that boundary excursions, if fast enough, can minimize the search time. A scaling analysis generalizes these findings to domains of arbitrary shapes and underlines their robustness. Overall, these results provide a generic mechanism of optimization of search kinetics in interfacial systems, which could have important implications in chemical physics. In the context of animal behavior sciences, it shows that following the boundaries of a domain can accelerate a search process, and therefore suggests that thigmotactism could be a kinetically efficient behavior.

Uniform asymptotic approximation of diffusion to a small target

The problem of the time required for a diffusing molecule, within a large bounded domain, to first locate a small target is prevalent in biological modeling. Here we study this problem for a small spherical target. We develop uniform in time asymptotic expansions in the target radius of the solution to the corresponding diffusion equation. Our approach is based on combining expansions of a long-time approximation of the solution, involving the first eigenvalue and eigenfunction of the Laplacian, with expansions of a short-time correction calculated by a pseudopotential approximation. These expansions allow the calculation of corresponding expansions of the first passage time density for the diffusing molecule to find the target. We demonstrate the accuracy of our method in approximating the first passage time density and related statistics for the spherically symmetric problem where the domain is a large concentric sphere about a small target centered at the origin.

Origin of the hub spectral dimension in scale-free networks

The return-to-origin probability and the first-passage-time distribution are essential quantities for understanding transport phenomena in diverse systems. The behaviors of these quantities typically depend on the spectral dimension d(s). However, it was recently revealed that in scale-free networks these quantities show a crossover between two power-law regimes characterized by d(s) and the so-called hub spectral dimension d(s)((hub)) due to the heterogeneity of connectivities of each node. To understand the origin of d(s)((hub)) from a theoretical perspective, we study a random walk problem on hierarchical scale-free networks by using the renormalization group (RG) approach. Under the RG transformation, not only the system size but also the degree of each node changes due to the scale-free nature of the degree distribution. We show that the anomalous behavior of random walks involving the hub spectral dimension d(s)((hub)) is induced by the conservation of the power-law degree distribution under the RG transformation.

Encounter times in overlapping domains: application to epidemic spread in a population of territorial animals

We develop an analytical method to calculate encounter times of two random walkers in one dimension when each individual is segregated in its own spatial domain and shares with its neighbor only a fraction of the available space, finding very good agreement with numerically exact calculations. We model a population of susceptible and infected territorial individuals with this spatial arrangement, and which may transmit an epidemic when they meet. We apply the results on encounter times to determine analytically the macroscopic propagation speed of the epidemic as a function of the microscopic characteristics: the confining geometry, the animal diffusion constant, and the infection transmission probability.

In vivo facilitated diffusion model

Under dilute in vitro conditions transcription factors rapidly locate their target sequence on DNA by using the facilitated diffusion mechanism. However, whether this strategy of alternating between three-dimensional bulk diffusion and one-dimensional sliding along the DNA contour is still beneficial in the crowded interior of cells is highly disputed. Here we use a simple model for the bacterial genome inside the cell and present a semi-analytical model for the in vivo target search of transcription factors within the facilitated diffusion framework. Without having to resort to extensive simulations we determine the mean search time of a lac repressor in a living E. coli cell by including parameters deduced from experimental measurements. The results agree very well with experimental findings, and thus the facilitated diffusion picture emerges as a quantitative approach to gene regulation in living bacteria cells. Furthermore we see that the search time is not very sensitive to the parameters characterizing the DNA configuration and that the cell seems to operate very close to optimal conditions for target localization. Local searches as implied by the colocalization mechanism are only found to mildly accelerate the mean search time within our model.

Enhanced transport through desorption-mediated diffusion

We present a master equation approach to the study of the bulk-mediated surface diffusion mechanism in a three-dimensional confined domain. The proposed scheme allowed us to evaluate analytically a number of magnitudes that were used to characterize the efficiency of the bulk-mediated surface transport mechanism, for instance, the mean escape time from the domain, and the mean number of distinct visited sites on the confined domain boundary.

First passages in bounded domains: when is the mean first passage time meaningful?

We study the first passage statistics to adsorbing boundaries of a Brownian motion in bounded two-dimensional domains of different shapes and configurations of the adsorbing and reflecting boundaries. From extensive numerical analysis we obtain the probability P(ω) distribution of the random variable ω=τ(1)/(τ(1)+τ(2)), which is a measure for how similar the first passage times τ(1) and τ(2) are of two independent realizations of a Brownian walk starting at the same location. We construct a chart for each domain, determining whether P(ω) represents a unimodal, bell-shaped form, or a bimodal, M-shaped behavior. While in the former case the mean first passage time (MFPT) is a valid characteristic of the first passage behavior, in the latter case it is an insufficient measure for the process. Strikingly we find a distinct turnover between the two modes of P(ω), characteristic for the domain shape and the respective location of absorbing and reflective boundaries. Our results demonstrate that large fluctuations of the first passage times may occur frequently in two-dimensional domains, rendering quite vague the general use of the MFPT as a robust measure of the actual behavior even in bounded domains, in which all moments of the first passage distribution exist.

First passage time for random walks in heterogeneous networks

The first passage time (FPT) for random walks is a key indicator of how fast information diffuses in a given system. Despite the role of FPT as a fundamental feature in transport phenomena, its behavior, particularly in heterogeneous networks, is not yet fully understood. Here, we study, both analytically and numerically, the scaling behavior of the FPT distribution to a given target node, averaged over all starting nodes. We find that random walks arrive quickly at a local hub, and therefore, the FPT distribution shows a crossover with respect to time from fast decay behavior (induced from the attractive effect to the hub) to slow decay behavior (caused by the exploring of the entire system). Moreover, the mean FPT is independent of the degree of the target node in the case of compact exploration. These theoretical results justify the necessity of using a random jump protocol (empirically used in search engines) and provide guidelines for designing an effective network to make information quickly accessible.