Lattice random walks for sets of random walkers. First passage times

We have studied the mean first passage time for the first of aset of random walkers to reach a given lattice point on infinite lattices ofD dimensions. In contrast to the well-known result ofinfinite mean first passage times for one random walker in all dimensionsD, we findfinite mean first passage times for certain well-specified sets of random walkers in all dimensions, exceptD = 2. The number of walkers required to achieve a finite mean time for the first walker to reach the given lattice point is a function of the lattice dimensionD. ForD > 4, we find that only one random walker is required to yield a finite first passage time, provided that this random walker reaches the given lattice point with unit probability. We have thus found a simple random walk property which sticks atD > 4.Supported in part by a grant from Charles and Renée Taubman and by the National Science Foundation, Grant CHE78-21460.     

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 ∞.     

The theory of ordered spans of unrestricted random walks

The spans of ann-step random walk on a simple cubic lattice are the sides of the smallest rectangular box, with sides parallel to the coordinate axes, that contains the random walk. Daniels first developed the theory in outline and derived results for the simple random walk on a line. We show that the development of a more general asymptotic theory is facilitated by introducing the spectral representation of step probabilities. This allows us to consider the probability density for spans of random walks in which all moments of single steps may be infinite. The theory can also be extended to continuous-time random walks. We also show that the use of Abelian summation simplifies calculation of the moments. In particular we derive expressions for the span distributions of random walks (in one dimension) with single step transition probabilities of the formP(j) 1/j ¹⁺, where 0<<2. We also derive results for continuous-time random walks in which the expected time between steps may be infinite.     

Multiple trapping of random walkers on periodic lattices

Formulas are obtained for the mean absorption time of a set ofk independent random walkers on periodic space lattices containingq traps. We consider both discrete (here we assume simultaneous stepping) and continuous-time random walks, and find that the mean lifetime of the set of walkers can be obtained, via a convolution-type recursion formula, from the generating function for one walker on the perfect lattice. An analytical solution is given for symmetric walks with nearest neighbor transitions onN-site rings containing one trap (orq equally spaced traps), for both discrete and exponential distribution of stepping times. It is shown that, asN , the lifetime of the walkers is of the form Ta_kN², whereT is the average time between steps. Values ofa _k, 2 Sk 6, are provided.     

A remark on diffusion of directed polymers in random environments

We consider a system of random walks or directed polymers interacting with an environment which is random in space and time. Under minimal assumptions on the distribution of the environment, we prove that this system has diffusive behavior with probability one ifd>2 and <₀, where ₀ is defined in terms of the probability that the symmetric nearest neighbor random walk on thed-dimensional integer lattice ever returns to its starting point. We also obtain a precise estimate for the mean square displacement of this system.     

First passage times for correlated random walks and some generalizations

It is generally difficult to solve Fokker-Planck equations in the presence of absorbing boundaries when both spatial and momentum coordinates appear in the boundary conditions. In this note we analyze a simple, exactly solvable model of the correlated random walk and its continuum analogue. It is shown that one can solve for the moments recursively in one dimension in exact analogy with first passage problems for the Fokker-Planck equation, although the boundary conditions are somewhat more complicated. Further generalizations are suggested to multistate random walks.     

A study on correlated exponential random walks

Based on the linear Boltzmann transport formulation, we investigate the statistics of correlated exponential random walks that are continuous in space and discrete in time. We show that asymptotically, the correlated random walk process is diffusive and derive an effective diffusion constant. We investigate the power spectral characteristics of the associated random forces. We also present some results on the first passage time distribution and establish that asymptotically it reduces to that associated with simple Gaussian walks.     

Non-Hermitian Tridiagonal Random Matrices and Returns to the Origin of a Random Walk

We study a class of tridiagonal matrix models, the q-roots of unity models, which includes the sign (q=2) and the clock (q=) models by Feinberg and Zee. We find that the eigenvalue densities are bounded by and have the symmetries of the regular polygon with 2q sides, in the complex plane. Furthermore, the averaged traces of M ^k are integers that count closed random walks on the line such that each site is visited a number of times multiple of q. We obtain an explicit evaluation for them.     

Escape times in interacting biased random walks

The dynamics ofN particles with hard core exclusion performing biased random walks is studied on a one-dimensional lattice with a reflecting wall. The bias is toward the wall and the particles are placed initially on theN sites of the lattice closest to the wall. ForN=1 the leading behavior of the first passage timeT _FP to a distant sitel is known to follow the Kramers escape time formulaT _FP ^l where is the ratio of hopping rates toward and away from the wall. ForN > 1 Monte Carlo and analytical results are presented to show that for the particle closest to the wall, the Kramers formula generalizes toT _FR ^IN. First passage times for the other particles are studied as well. A second question that is studied pertains to survival timesT _s in the presence of an absorbing barrier placed at sitel. In contrast to the first passage time, it is found thatT _s follows the leading behavior independent ofN.     

Mutual Annihilation of Two Diffusing Particles in One- and Two-Dimensional Lattices

The probabilistic dynamics of a pair of particles which can mutually annihilate in the course of their random walk on a lattice is considered and analytically found for d=1 and d=2. In view of available recent experiments achieved on the femtosecond scale, emphasis is put on the necessity of a full continuous-time, discrete-space solution at all times. Quantities of physical interest are calculated at any time, including the total pair survival probability N(t) and the two-particle correlation function. As a by-product, the lattice version allows for a precise regularization of the continuous-space framework, which is ill-conditionned for d2; this being done, formal generalization to any real dimensionality can be straightforwardly performed.     

Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks

We study numerically the mean access times for random walks on hybrid disordered structures formed by embedding scale-free networks into regular lattices, considering different transition rates for steps across lattice bonds (F) and across network shortcuts (f). For fast shortcuts (f/F≫1) and low shortcut densities, traversal time data collapse onto a universal curve, while a crossover behavior that can be related to the percolation threshold of the scale-free network component is identified at higher shortcut densities, in analogy to similar observations reported recently in Newman-Watts small-world networks. Furthermore, we observe that random walk traversal times are larger for networks with a higher degree of inhomogeneity in their shortcut distribution, and we discuss access time distributions as functions of the initial and final node degrees. These findings are relevant, in particular, when considering the optimization of existing information networks by the addition of a small number of fast shortcut connections.     

Numerical Simulations of Random Walk in Random Environment

This paper is concerned with the numerical simulation of a random walk in a random environment in dimension d = 2. Consider a nearest neighbor random walk on the 2-dimensional integer lattice. The transition probabilities at each site are assumed to be themselves random variables, but fixed for all time. This is the random environment. Consider a parallel strip of radius R centered on an axis through the origin. Let X _R be the probability that the walk that started at the origin exits the strip through one of the boundary lines. Then X _R is a random variable, depending on the environment. In dimension d = 1, the variable X _R converges in distribution to the Bernoulli variable, X = 0, 1 with equal probability, as R . Here the 2-dimensional problem is studied using Gauss-Seidel and multigrid algorithms.     

First passage time and escape time distributions for continuous time random walks

We consider an arbitrary continuous time random walk (ctrw)via unbiased nearest-neighbour jumps on a linear lattice. Solutions are presented for the distributions of the first passage time and the time of escape from a bounded region. A simple relation between the conditional probability function and the first passage time distribution is analysed. So is the structure of the relation between the characteristic functions of the first passage time and escape time distributions. The mean first passage time is shown to diverge for all (unbiased)ctrw’s. The divergence of the mean escape time is related to that of the mean time between jumps. A class ofctrw’s displaying a self-similar clustering behaviour in time is considered. The exponent characterising the divergence of the mean escape time is shown to be (1−H), whereH(0<H<1) is the fractal dimensionality of thectrw.     

Computer Simulations for Some One-Dimensional Models of Random Walks in Fluctuating Random Environment

We report some results of computer simulations for two models of random walks in random environment (rwre) on the one-dimensional lattice for fixed space–time configuration of the environment (“quenched rwre”): a “Markov model” with Markov dependence in time, and a “quasi stationary” model with long range space–time correlations. We compare with the corresponding results for a model with i.i.d. (in space time) environment. In the range of times available to us the quenched distributions of the random walk displacement are far from gaussian, but as the behavior is similar for all three models one cannot exclude asymptotic gaussianity, which is proved for the model with i.i.d. environment. We also report results on the random drift and on some time correlations which show a clear power decay     

First passage time problems in time-dependent fields

This paper discusses the simplest first passage time problems for random walks and diffusion processes on a line segment. When a diffusing particle moves in a time-varying field, use of the adjoint equation does not lead to any simplification in the calculation of moments of the first passage time as is the case for diffusion in a time-invariant field. We show that for a discrete random walk in the presence of a sinusoidally varying field there is a resonant frequency * for which the mean residence time on the line segment is a minimum. It is shown that for a random walk on a line segment of lengthL the mean residence time goes likeL ² for largeL when *, but when =* the dependence is proportional toL. The results of our simulation are numerical, but can be regarded as exact. Qualitatively similar results are shown to hold for diffusion processes by a perturbation expansion in powers of a dimensionless velocity. These results are extended to higher values of this parameter by a numerical solution of the forward equation.     

First passage time densities for random walk spans

A general expression is derived for the Laplace transform of the probability density of the first passage time for the span of a symmetric continuous-time random walk to reach levelS. We show that when the mean time between steps is finite, the mean first passage time toS is proportional toS ₂. When the pausing time density is asymptotic to a stable density we show that the first passage density is also asymptotically stable. Finally when the jump distribution of the random walk has the asymptotic formp(j)A/|j| ₊₁, 0 < < 2 it is shown that the mean first passage time toS goes likeS .     

Two-dimensional oriented self-avoiding walks with parallel contacts

Oriented self-avoiding walks (OSAWs) on a square lattice are studied, with binding energies between steps that are oriented parallel across a face of the lattice. By means of exact enumeration and Monte Carlo simulation, we reconstruct the shape of the partition function and show that this system features of first-order phase transition from a free phase to a tight-spiral phase at _s =log(), where -2.638 is the growth constant for SAWs. With Monte Carlo simulations we show that parallel contacts happen predominantly between a step close to the end of the OSAW and another step nearby; this appears to cause the expected number of parallel contacts to saturate at large lengths of the OSAW.     

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.     

Random walks with short memory

A restricted random walk on ad-dimensional cubic lattice with different probabilities for forward, backward, and sideward steps is studied. The analytic solution for the generating function, exact expressions for the second and fourth moments of displacements, and diffusion and Burnett coefficients are given, as well as a systematic asymptotic expansion for the probability distribution of long walks.This paper is dedicated to Nico van Kampen.     

Random walks on lattices. IV. Continuous-time walks and influence of absorbing boundaries

The general study of random walks on a lattice is developed further with emphasis on continuous-time walks with an asymmetric bias. Continuous time walks are characterized by random pauses between jumps, with a common pausing time distribution(t). An analytic solution in the form of an inverse Laplace transform for P(l, t), the probability of a walker being atl at timet if it started atl _o att=0, is obtained in the presence of completely absorbing boundaries. Numerical results for P(l, t) are presented for characteristically different (t), including one which leads to a non-Gaussian behavior for P(l, t) even for larget. Asymptotic results are obtained for the number of surviving walkers and the mean l showing the effect of the absorption at the boundary.This study was partially supported by ARPA and monitored by ONR(N00014-17-0308).