First passage time problems for one-dimensional random walks

This note contains a development of the theory of first passage times for one-dimensional lattice random walks with steps to nearest neighbor only. The starting point is a recursion relation for the densities of first passage times from the set of lattice points. When these densities are unrestricted, the formalism allows us to discuss first passage times of continuous time random walks. When they are negative exponential densities we show that the resulting equation is the adjoint of the master equation. This is the lattice analog of a correspondence well known for systems describable by a Fokker-Planck equation. Finally we discuss first passage problems for persistent random walks in which at each step the random walker continues in the same direction as the preceding step with probability a or reverses direction with probability 1–     

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

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.     

When a Random Walk of Fixed Length can Lead Uniformly Anywhere Inside a Hypersphere

A variation of the Pearson-Rayleigh random walk in which the steps are i.i.d. random vectors of exponential length and uniform orientation is considered. Conditioned on the total path length, the probability density function of the position of the walker after n steps is determined analytically in one and two dimensions. It is shown that in two dimensions n = 3 marks a critical transition point in the behavior of the random walk. By taking less than three steps and walking a total length l, one is more likely to end the walk near the boundary of the disc of radius l, while by taking more than three steps one is more likely to end near the origin. Somehow surprisingly, by taking exactly three steps one can end uniformly anywhere inside the disc of radius l. This means that conditioned on l, the sum of three vectors of exponential length and uniform direction has a uniform probability density. While the presented analytic approach provides a complete solution for all n, it becomes intractable in higher dimensions. In this case, it is shown that a necessary condition to have a uniform density in dimension d is that 2(d + 2)/d is an integer, equal to n + 1.     

Area Distribution for Directed Random Walks

We study the probability distribution for the area under a directed random walk in the plane. The walk can serve as a simple model for avalanches based on the idea that the front of an avalanche can be described by a random walk and the size is given by the area enclosed. This model captures some of the qualitative features of earthquakes, avalanches, and other self-organized critical phenomena in one dimension. By finding nonlinear functional relations for the generating functions we calculate directly the exponent in the size distribution law and find it to be 4/3.     

SLE on Doubly-Connected Domains and the Winding of Loop-Erased Random Walks

Two-dimensional loop-erased random walks (LERWs) are random planar curves whose scaling limit is known to be a Schramm-Loewner evolution SLE _κ with parameter κ=2. In this note, some properties of an SLE _κ trace on doubly-connected domains are studied and a connection to passive scalar diffusion in a Burgers flow is emphasised. In particular, the endpoint probability distribution and winding probabilities for SLE₂ on a cylinder, starting from one boundary component and stopped when hitting the other, are found. A relation of the result to conditioned one-dimensional Brownian motion is pointed out. Moreover, this result permits to study the statistics of the winding number for SLE₂ with fixed endpoints. A solution for the endpoint distribution of SLE₄ on the cylinder is obtained and a relation to reflected Brownian motion pointed out.     

Behavior of general one-dimensional diffusion processes

We develop simple rigorous techniques to estimate the behavior of general one-dimensional diffusion processes. Any one-dimensional diffusion process (with drift) can be mapped onto a symmetric diffusion through an explicit change of variable. For such processes we can estimate explicitly the diffusion exponent, the recurrence properties, and the large fluctuations. In a second part, we apply these results to different models (including the Sinaï random walk: diffusion in a random drift) and we show how the main features of the diffusion can be readily handled.     

Persistent random walks in a one-dimensional random environment

Central limit theorems are obtained for persistent random walks in a onedimensional random environment. They also imply the central limit theorem for the motion of a test particle in an infinite equilibrium system of point particles where the free motion of particles is combined with a random collision mechanism and the velocities can take on three possible values.Work supported by the Central Research Fund of the Hungarian Academy of Sciences (grant No. 476/82).     

On the validity of the Onsager-Machlup postulate for nonlinear stochastic processes

It is shown that: (i) the Onsager-Machlup postulate applies to nonlinear stochastic processes over a time scale that, while being much longer than the correlation times of the random forces, is still much shorter than the time it takes for the nonlinear distortion to become visible; (ii) these are also the conditions for the validity of the generalized Fokker-Planck equation; and (iii) when the fine details of the space-time structure of the stochastic processes are unimportant, the generalized Fokker-Planck equation can be replaced by the ordinary Fokker-Planck equation.     

A hierarchical model for random walks in random media

We show that the random walk generated by a hierarchical Laplacian in ^d has standard diffusive behavior. Moreover, we show that this behavior is stable under a class of random perturbations that resemble an off-diagonal disordered lattice Laplacian. The density of states and its asymptotic behavior around zero energy are computed: singularities appear in one and two dimensions.     

First passage time and extremum properties of Markov and independent processes

It was shown by Newell in 1962 that the extreme value and first passage time distributions of various types of common Markov processes asymptotically approach those for independent random variables. In view of the great simplification this occasions in the calculation of a number of important properties of Markov processes, it is clearly of interest to determine in some detail the conditions on both the time and space variables under which this equivalence holds. In this paper we investigate and establish these conditions for Markov processes described by the Fokker-Planck equation and express them in simple analytic forms which are directly related to the coefficients of the Fokker-Planck equation. To demonstrate the usefulness of these conditions, we apply them to two representative examples of Fokker-Planck equations, the Ornstein-Uhlenbeck process and the Montroll-Shuler model for harmonic oscillator dissociation. It is shown very clearly in these examples that the extreme value and first passage time     

The shapes of bowed interfaces in the two-dimensional Ising model

We show that properly normalized net energy fluctuations associated with interfaces in two-dimensional Ising models are described, asymptotically, by random walk partition functions. Two examples are investigated: one is a droplet on a wall, and the other is two nearby, ideally parallel interfaces; the mean shapes of the interfaces in both cases prove to be elliptic, bowed outward from the wall or from each other, the semiminor axis of the latter ellipse being 1/2 that of the former, in accord with random walk results.     

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.     

The Langevin equation on Lie algebras: Maxwell-Boltzmann is not always the equilibrium

We give a geometric formulation of the Fokker-Planck-Kramer equations for a particle moving on a Lie algebra under the influence of a dissipative and a random force. Special cases of interest are fluid mechanics, the Stochastic Loewner equation and the rigid body. We find that the Boltzmann distribution, although a static solution, is not normalizable when the algebra is not unimodular. This is because the invariant measure of integration in momentum space is not the standard one. We solve the special case of the upper half-plane (hyperboloid) explicitly: there is another equilibrium solution to the Fokker-Planck equation, which is integrable. It breaks rotation invariance.     

Asymptotic properties of multistate random walks. II. Applications to inhomogeneous periodic and random lattices

The previously developed formalism for the calculation of asymptotic properties of multistate random walks is used to study random walks on several inhomogeneous periodic lattices, where the periodically repeated unit cell contains a number of inequivalent sites, as well as on lattices with a random distribution of inequivalent sites. We concentrate on the question whether the random walk properties depend on the spatial arrangement of the sites in the unit cell, or only on the number density of the different types of sites. Specifically we consider lattices with periodic and random arrangements of columns and lattices with periodic and random arrangements of anisotropic scatterers.     

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.     

Chaos in discrete maps,deterministic scattering,and nondifferentiable functions

Arguments in favor of the nondifferentiability with respect to initial data of some functions associated with deterministic discrete-time dynamical systems are presented. A correspondence between a discrete-time dynamical system and a deterministic scattering model is found and used to interpret nondifferentiability conditions. A connection with random walks is also found.     

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.     

Diffusion of directed polymers in a random environment

We consider a system of random walks or directed polymers interacting weakly with an environment which is random in space and time. In spatial dimensionsd>2, we establish that the behavior is diffusive with probability one. The diffusion constant is not renormalized by the interaction.