Recurrence and Pólya Number of General One-Dimensional Random Walks

The recurrence properties of random walks can be characterized by Pólya number, i.e., the probability that the walker has returned to the origin at least once. In this paper, we consider recurrence properties for a general 1D random walk on a line, in which at each time step the walker can move to the left or right
with probabilities l and r, or remain at the same position with probability o (l+r+o=1). We calculate Pólya number P of this model and find a simple expression for P as, P=1-Δ, whereΔ is the absolute difference of l and r (Δ=|l-r|). We prove this rigorous expression by the method of creative telescoping, and our result suggests that the walk is recurrent if and only if the left-moving probability l equals to the right-moving probability r.     

Asymptotic solutions of the continuous-time random walk model of diffusion

Asymptotic distributions of the Montroll-Weiss equation for the continuous-time random walk are investigated for long times. It is shown that, for a certain subclass of the hopping waiting time distributions belonging to the domain of attraction of stable distributions, these asymptotic distributions are of stable form. This indicates that the realm of applicability of the diffusion equation is limited. The Montroll-Weiss equation is rederived to include the influence of the initial waiting interval and the role of the stable distributions in physical problems is briefly discussed.     

Random walk in random environment: A counterexample without potential

We describe a family of random walks in random environment which have exponentially decaying correlations, nearest neighbor transition probabilities which are bounded away from 0, and are subdiffusive in any dimensiond<. The random environments have no potential ind>1.     

Tests of the random walk hypothesis for financial data

We propose a method from the viewpoint of deterministic dynamical systems to investigate whether observed data follow a random walk (RW) and apply the method to several financial data. Our method is based on the previously proposed small-shuffle surrogate method. Hence, our method does not depend on the specific data distribution, although previously proposed methods depend on properties of the data distribution. The data we use are stock market (Standard & Poor's 500 in US market and Nikkei225 in Japanese market), exchange rate (British Pound/US dollar and Japanese Yen/US dollar), and commodity market (gold price and crude oil price). We found that these financial data are RW whose first differences are independently distributed random variables or time-varying random variables.     

Laplace operator and random walk on one-dimensional nonhomogeneous lattice

A classical result of probability theory states that under suitable space and time renormalization, a random walk converges to Brownian motion. We prove an analogous result in the case of nonhomogeneous random walk on onedimensional lattice. Under suitable conditions on the nonhomogeneous medium, we prove convergence to Brownian motion and explicitly compute the diffusion coefficient. The proofs are based on the study of the spectrum of random matrices of increasing dimension.     

Fractal behavior in trapping and reaction: A random walk study

We investigate the trapping of a random walker in fractal structures (Sierpinski gaskets) with randomly distributed traps. The survival probability is determined from the number of distinct sites visited in the trap-free fractals. We show that the short-time behavior and the long-time tails of the survival probability are governed by the spectral dimensiond. We interpolate between these two limits by introducing a scaling law. An extension of the theory, which includes a continuous-time random walk on fractals, is discussed as well as the case of direct trapping. The latter case is shown to be governed by the fractal dimensiond.     

Some properties of a fractal-time continuous-time random walk in the presence of traps

The CTRW has often been applied to problems related to transport in a statistically homogeneous disordered medium, which means that there are no traps or reflecting boundaries to be found in the medium. Two physical applications, one to the migration of photons in a turbid medium and the second to the theory of diffusion-controlled reactions in a random medium, suggest that it might be useful to study properties of the CTRW, particularly as they refer to survival probability in the presence of a trap or a trapping surface. We calculate a number of these properties when the pausing-time density is asymptotically proportional to a stable law, i.e.,(t)T ⁺¹ as (t/T), where 0<<1. A forthcoming paper will establish the correspondence between properties of the CTRW and proprties of random walkers on a fractal with trapping boundaries.This paper is dedicated to Jerry Percus on the occasion of his 65th birthday. May he enjoy many more happy and productive years.     

Moments of the Montroll-Weiss continuous-time random walk for arbitrary starting time

The generalized version of the Montroll-Weiss formalism for continuous-time random walks is employed to show that some of the asymptotic results for large times appropriate to the ordinary walk become exact when the start of the observations is arbitrary.     

Distribution functions for random walk processes on networks: An analytic method

A novel analytic method for deriving and analyzing probability distribution functions of variables arising in random walk problems is presented. Applications of the method to quasi-one-dimensional systems show that the generating functions of interest possess simple poles, and no branch cuts outside the unit complex disk. This fact makes it possible to derive closed formulas for the full probability distribution functions and to analyze their properties. We find that transverse structures attached to a one-dimensional backbone can be responsible for the appearance of power laws in observables such as the distribution of first arrival times or the total current moving through a (model) photoexcited dirty semiconductor (our results compare well with experiment). We conclude that in some cases a geometrical effect, e.g., that of a transverse structure, may be indistinguishable from a dynamical effect (long waiting time); we also find universal shapes of distribution functions (humped structures) which are not characterized by power laws. The role of bias in determining properties of quasi-one-dimensional structures is examined. A master equation for generating functions is derived and applied to the computation of currents. Our method is also applied to a fractal structure, yielding nontrivial power laws. In all finite networks considered, all probability distributions decay exponentially for asymptotically long times.For a relatively recent review with some historical background see Ref. 2.     

The 3-dimensional random walk with applications to overstretched DNA and the protein titin

We study the three-dimensional persistent random walk with drift. Then we develop a thermodynamic model that is based on this random walk without assuming the Boltzmann-Gibbs form for the equilibrium distribution. The simplicity of the model allows us to perform all calculations in closed form. We show that, despite its simplicity, the model can be used to describe different polymer stretching experiments. We study the reversible overstretching transition of DNA and the static force-extension relation of the protein titin.     

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.     

On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper''s operator

Harper's operator is the self-adjoint operator on defined by

Full-size image

. We first show that the determination of the spectrum of the transition operator on the Cayley graph of the discrete Heisenberg group in its standard presentation, is equivalent to the following upper bond on the norm of H_θ,: H_{θ,≤ 2(1 + √2 + cos(2πθ))}. We then prove this bound by reducing it to a problem on periodic Jacobi matrices, viewing H_θ, as the image of H_θ = U_θ + _θ^* + V_θ + V_θ^* in a suitable representation of the rotation algebra A_θ. We also use powers of H_θ to obtain various upper and lower bounds on H_θ = maxH_θ,. We show that “Fourier coefficients” of H_θ^k in A_θ have a combinatorial interpretation in terms of paths in the square lattice ². This allows us to give some applications to asymptotics of lattice paths combinatorics.     

Vicious random walkers in the limit of a large number of walkers

The vicious random walker problem on a line is studied in the limit of a large number of walkers. The multidimensional integral representing the probability that thep walkers will survive a timet (denotedP _t ^(p) ) is shown to be analogous to the partition function of a particular one-component Coulomb gas. By assuming the existence of the thermodynamic limit for the Coulomb gas, one can deduce asymptotic formulas forP _t ^(p) in the large-p, large-t limit. A straightforward analysis gives rigorous asymptotic formulas for the probability that after a timet the walkers are in their initial configuration (this event is termed a reunion). Consequently, asymptotic formulas for the conditional probability of a reunion, given that all walkers survive, are derived. Also, an asymptotic formula for the conditional probability density that any walker will arrive at a particular point in timet, given that allp walkers survive, is calculated in the limittp.     

High winding number of topological phase in non-unitary periodic quantum walk

Topological phases and their associated multiple edge states are studied by constructing a one-dimensional non-unitary multi-period quantum walk with parity-time symmetry. It is shown that large topological numbers can be obtained when choosing an appropriate time frame. The maximum value of the winding number can reach the number of periods in the one-step evolution operator. The validity of the bulk–edge correspondence is confirmed, while for an odd-period quantum walk and an even-period quantum walk, they have different configurations of the 0-energy edge state and π-energy edge state. On the boundary, two kinds of edge states always coexist in equal amount for the odd-period quantum walk, however three cases including equal amount, unequal amount or even only one type may occur for the even-period quantum walk.     

The asymptotic behavior of a random walk on a dual-medium lattice

This paper considers the asymptotic distribution for the horizontal displacement of a random walk in a medium represented by a two-dimensional lattice, whose transitions are to nearest-neighbor sites, are symmetric in the horizontal and vertical directions, and depend on the column currently occupied. On either side of a change-point in the medium, the transition probabilities are assumed to obey an asymptotic density condition. The displacement, when suitably normalized, converges to a diffusion process of oscillating Brownian motion type. Various special cases are discussed.     

Molecular phase space transport in water: Non-stationary random walk model

Molecular transport in phase space is crucial for chemical reactions because it defines how pre-reactive molecular configurations are found during the time evolution of the system. Using Molecular Dynamics (MD) simulated atomistic trajectories we test the assumption of the normal diffusion in the phase space for bulk water at ambient conditions by checking the equivalence of the transport to the random walk model. Contrary to common expectations we have found that some statistical features of the transport in the phase space differ from those of the normal diffusion models. This implies a non-random character of the path search process by the reacting complexes in water solutions. Our further numerical experiments show that a significant long period of non-stationarity in the transition probabilities of the segments of molecular trajectories can account for the observed non-uniform filling of the phase space. Surprisingly, the characteristic periods in the model non-stationarity constitute hundreds of nanoseconds, that is much longer time scales compared to typical lifetime of known liquid water molecular structures (several picoseconds).     

On the expected number of distinct points in a subset visited by anN-step random walk

Many investigators have calculated asymptotically valid expressions for the expected number of distinct points visited by ann-step random walk on a lattice. In this note we point out that the same formalism can be used to study the expected number of distinct points in a subset of lattice points. We also calculate the expected occupancy of the subset and give sufficient conditions for the ratio of the two calculated quantities to have the same asymptotic time dependence as for the full lattice. Specific examples are considered.     

Vicious random walkers and a discretization of Gaussian random matrix ensembles

The vicious random walker problem on a one-dimensional lattice is considered. Many walkers take simultaneous steps on the lattice and the configurations in which two of them arrive at the same site are prohibited. It is known that the probability distribution of N walkers after M steps can be written in a determinant form. Using an integration technique borrowed from the theory of random matrices, we show that arbitrary kth order correlation functions of the walkers can be expressed as quaternion determinants whose elements are compactly expressed in terms of symmetric Hahn polynomials.