Reflection principles for biased random walks and application to escape time distributions

We present a reflection principle for an arbitrarybiased continuous time random walk (comprising both Markovian and non-Markovian processes) in the presence of areflecting barrier on semi-infinite and finite chains. For biased walks in the presence of a reflecting barrier this principle (which cannot be derived from combinatorics) is completely different from its familiar form in the presence of an absorbing barrier. The result enables us to obtain closed-form solutions for the Laplace transform of the conditional probability for biased walks on finite chains for all three combinations of absorbing and reflecting barriers at the two ends. An important application of these solutions is the calculation of various first-passage-time and escape-time distributions. We obtain exact results for the characteristic functions of various kinds of escape time distributions for biased random walks on finite chains. For processes governed by a long-tailed event-time distribution we show that the mean time of escape from bounded regions diverges even in the presence of a bias—suggesting, in a sense, the absence of true long-range diffusion in such frozen processes.     

First passage time distributions for finite one-dimensional random walks

We present closed expressions for the characteristic function of the first passage time distribution for biased and unbiased random walks on finite chains and continuous segments with reflecting boundary conditions. Earlier results on mean first passage times for one-dimensional random walks emerge as special cases. The divergences that result as the boundary is moved out to infinity are exhibited explicitly. For a symmetric random walk on a line, the distribution is an elliptic theta function that goes over into the known Lévy distribution with exponent 1/2 as the boundary tends to ∞.     

Damage spreading and criticality in finite random dynamical networks

We systematically study and compare damage spreading at the sparse percolation (SP) limit for random Boolean and threshold networks with perturbations that are independent of the network size N. This limit is relevant to information and damage propagation in many technological and natural networks. Using finite-size scaling, we identify a new characteristic connectivity Ks, at which the average number of damaged nodes d[over ], after a large number of dynamical updates, is independent of N. Based on marginal damage spreading, we determine the critical connectivity Kc(sparse)(N) for finite N at the SP limit and show that it systematically deviates from Kc, established by the annealed approximation, even for large system sizes. Our findings can potentially explain the results recently obtained for gene regulatory networks and have important implications for the evolution of dynamical networks that solve specific tasks.     

Network formed by traces of random walks

We propose a model of time evolving networks in which a kind of transport between vertices generates new edges in the graph. We call the model “Network formed by traces of random walks”, because the transports are represented abstractly by random walks. Our numerical calculations yield several important properties observed commonly in complex networks, although the graph at initial time is only a one-dimensional lattice. For example, the distribution of vertex degree exhibits various behaviors such as exponential, power law like, and bi-modal distribution according to change of probability of extinction of edges. Another property such as strong clustering structure and small mean vertex–vertex distance can also be found. The transports represented by random walks in a framework of strong links between regular lattice is a new mechanisms which yields biased acquisition of links for vertices.     

Finite-size effects in random energy models and in the problem of polymers in a random medium

By the use of traveling wave equations we calculate the finite-size corrections to the free energy of random energy models in their low-temperature phases and in the neighborhood of the transition temperature. We find that although the extensive part of the free energy does not show any critical behavior when the temperature approaches its transition value, the finite-size corrections signal the transition by becoming singular. We obtain a scaling form for these finite-size corrections valid in the limitN andTT _c . By considering a generalized random energy model in the limit of a very large number of steps, we obtain results for the finite-size corrections in the problem of a polymer in a random medium.     

Localization of random walks in one-dimensional random environments

We consider a random walk on the one-dimensional semi-lattice ={0, 1, 2,...}. We prove that the moving particle walks mainly in a finite neighbourhood of a point depending only on time and a realization of the random environment. The size of this neighbourhood is estimated. The limit parameters of the walks are also determined.     

度关联无标度网络上的有倾向随机行走

有倾向随机行走是研究网络上数据包路由策略的有效方法. 由于许多真实技术网络包括互联网都具有负的度关联特征, 因此本文研究这种网络上的有倾向随机行走性质. 研究表明: 在负关联网络上粒子可以在连接度较大的节点上均匀分布, 而连接度小的节点上粒子较少; 负关联网络上随机行走的速度比非关联网络更快; 找到了负关联网络上的最佳倾向性系数, 在此情况下负关联网络上随机行走的速度远快于非关联网络. 负关联网络既可以利用度小的节点容纳粒子, 又可以利用度大的节点快速传输, 这是负关联网络上高行走效率产生的机制.     

A note on occupation times of random walks

In this note I show that some asymptotic results on the average occupancy time of an interval derived for lattice random walks with negative exponential transition probabilities are true for all random walks whose transition probabilities have a finite variance. The proof is based on the continuum limit.     

Asymptotic properties of multistate random walks. I. Theory

A calculation is presented of the long-time behavior of various random walk properties (moments, probability of return to the origin, expected number of distinct sites visited) formultistate random walks on periodic lattices. In particular, we consider inhomogeneous periodic lattices, consisting of a periodically repeated unit cell which contains a finite number of internal states (sites). The results are identical to those for perfect lattices except for a renormalization of coefficients. For walks without drift, it is found that all the asymptotic random walk properties are determined by the diffusion coefficients for the multistate random walk. The diffusion coefficients can be obtained by a simple matrix algorithm presented here. Both discrete and continuous time random walks are considered. The results are not restricted to nearest-neighbor random walks but apply as long as the single-step probability distributions associated with each of the internal states have finite means and variances.     

A simple calculation for the average number of steps to trapping in lattice random walks

We show that the asymptotic results for the average number of steps to trapping at an irreversible trapping site on aD-dimensional finite lattice can be obtained from the generating function for random walks on aninfinite perfect lattice. This introduces a significant simplification into such calculations. An interesting corollary of these calculations is the conclusion that a random walker traverses, on the average, all the distinct nontrapping lattice sites before arriving on the trapping site.This work was supported in part by NSF Grants MPS72-04363-A03 and CHE75-20624.     

Optimizing persistent random searches

We consider a minimal model of persistent random searcher with a short range memory. We calculate exactly for such a searcher the mean first-passage time to a target in a bounded domain and find that it admits a nontrivial minimum as function of the persistence length. This reveals an optimal search strategy which differs markedly from the simple ballistic motion obtained in the case of Poisson distributed targets. Our results show that the distribution of targets plays a crucial role in the random search problem. In particular, in the biologically relevant cases of either a single target or regular patterns of targets, we find that, in strong contrast to repeated statements in the literature, persistent random walks with exponential distribution of excursion lengths can minimize the search time, and in that sense perform better than any Levy walk.     

Open Quantum Random Walks

A new model of quantum random walks is introduced, on lattices as well as on finite graphs. These quantum random walks take into account the behavior of open quantum systems. They are the exact quantum analogues of classical Markov chains. We explore the “quantum trajectory” point of view on these quantum random walks, that is, we show that measuring the position of the particle after each time-step gives rise to a classical Markov chain, on the lattice times the state space of the particle. This quantum trajectory is a simulation of the master equation of the quantum random walk. The physical pertinence of such quantum random walks and the way they can be concretely realized is discussed. Differences and connections with the already well-known quantum random walks, such as the Hadamard random walk, are established.     

Extremal behavior of a coupled continuous time random walk

Coupled continuous time random walks (CTRWs) model normal and anomalous diffusion of random walkers by taking the sum of random jump lengths dependent on the random waiting times immediately preceding each jump. They are used to simulate diffusion-like processes in econophysics such as stock market fluctuations, where jumps represent financial market microstructure like log returns. In this and many other applications, the magnitude of the largest observations (e.g. a stock market crash) is of considerable importance in quantifying risk. We use a stochastic process called a coupled continuous time random maxima (CTRM) to determine the density governing the maximum jump length of a particle undergoing a CTRW. CTRM are similar to continuous time random walks but track maxima instead of sums. The many ways in which observations can depend on waiting times can produce an equally large number of CTRM governing density shapes. We compare densities governing coupled CTRM with their uncoupled counterparts for three simple observation/wait dependence structures.     

The Ising model on random lattices in arbitrary dimensions

We study analytically the Ising model coupled to random lattices in dimension three and higher. The family of random lattices we use is generated by the large N limit of a colored tensor model generalizing the two-matrix model for Ising spins on random surfaces. We show that, in the continuum limit, the spin system does not exhibit a phase transition at finite temperature, in agreement with numerical investigations. Furthermore we outline a general method to study critical behavior in colored tensor models.     

Resilience of the internet to random breakdowns

A common property of many large networks, including the Internet, is that the connectivity of the various nodes follows a scale-free power-law distribution, P(k) = ck(-alpha). We study the stability of such networks with respect to crashes, such as random removal of sites. Our approach, based on percolation theory, leads to a general condition for the critical fraction of nodes, p(c), that needs to be removed before the network disintegrates. We show analytically and numerically that for alpha0.99.     

The two-state random walk

We develop asymptotic results for the two-state random walk, which can be regarded as a generalization of the continuous-time random walk. The two-state random walk is one in which a particle can be in one of two states for random periods of time, each of the states having different spatial transition probabilities. When the sojourn times in each of the states and the second moments of transition probabilities are finite, the state probabilities have an asymptotic Gaussian form. Several known asymptotic results are reproduced, such as the Gaussian form for the probability density of position in continuous-time random walks, the time spent in one of these states, and the diffusion constant of a two-state diffusing particle.     

Exact scaling for the mean first-passage time of random walks on a generalized Koch network with a trap

In this paper,we study the scaling for the mean first-passage time(MFPT) of the random walks on a generalized Koch network with a trap.Through the network construction,where the initial state is transformed from a triangle to a polygon,we obtain the exact scaling for the MFPT.We show that the MFPT grows linearly with the number of nodes and the dimensions of the polygon in the large limit of the network order.In addition,we determine the exponents of scaling efficiency characterizing the random walks.Our results are the generalizations of those derived for the Koch network,which shed light on the analysis of random walks over various fractal networks.     

Distribution of time-averaged observables for weak ergodicity breaking

We find a general formula for the distribution of time-averaged observables for systems modeled according to the subdiffusive continuous time random walk. For Gaussian random walks coupled to a thermal bath we recover ergodicity and Boltzmann's statistics, while for the anomalous subdiffusive case a weakly nonergodic statistical mechanical framework is constructed, which is based on Lévy's generalized central limit theorem. As an example we calculate the distribution of X, the time average of the position of the particle, for unbiased and uniformly biased particles, and show that X exhibits large fluctuations compared with the ensemble average .     

Weak localization of light in superdiffusive random systems

Lévy flights constitute a broad class of random walks that occur in many fields of research, from biology to economy and geophysics. The recent advent of Lévy glasses allows us to study Lévy flights-and the resultant superdiffusion-using light waves. This raises several questions about the influence of interference on superdiffusive transport. Superdiffusive structures have the extraordinary property that all points are connected via direct jumps, which is expected to have a strong impact on interference effects such as weak and strong localization. Here we report on the experimental observation of weak localization in Lévy glasses and compare our results with a recently developed theory for multiple scattering in superdiffusive media. Experimental results are in good agreement with theory and allow us to unveil the light propagation inside a finite-size superdiffusive system.     

Self-avoiding random loops versus Ising model in three dimensions

On the basis of a recently developed lattice model for ensembles of random loops which contains a parameter interpolating between self-avoiding and Ising-like loops, we calculate the average length and the length fluctuations of self-avoiding loops in three dimensions, using analytic as well as Monte Carlo methods, and compare the results with the Ising case. Applying finite-size scaling techniques, we show that the critical behavior of self-avoiding random loops is consistent with universality predictions based on the Ising model.