Return Probability of Quantum and Correlated Random Walks

The analysis of the return probability is one of the most essential and fundamental topics in the study of classical random walks. In this paper, we study the return probability of quantum and correlated random walks in the one-dimensional integer lattice by the path counting method. We show that the return probability of both quantum and correlated random walks can be expressed in terms of the Legendre polynomial. Moreover, the generating function of the return probability can be written in terms of elliptic integrals of the first and second kinds for the quantum walk.     

Persistent Random Walks in Stationary Environment

We study the behavior of persistent random walks (RW) on the integers in a random environment. A complete characterization of the almost sure limit behavior of these processes, including the law of large numbers, is obtained. This is done in a general situation where the environmental sequence of random variables is stationary and ergodic. Szász and Tóth obtained a central limit theorem when the ratio /, of right- and left-transpassing probabilities satisfies /a<1 a.s. (for a given constant a). We consider the case where / has wider fluctuations; we shall observe that an unusual situation arises: the RW may converge a.s. to infinity even with zero drift. Then, we obtain nonclassical limiting distributions for the RW. Proofs are based on the introduction of suitable branching processes in order to count the steps performed by the RW.     

Random Walks on a Fractal Solid

It is established that the trapping of a random walker undergoing unbiased, nearest-neighbor displacements on a triangular lattice of Euclidean dimension d=2 is more efficient (i.e., the mean walklength n before trapping of the random walker is shorter) than on a fractal set, the Sierpinski tower, which has a Hausdorff dimension D exactly equal to the Euclidean dimension of the regular lattice. We also explore whether the self similarity in the geometrical structure of the Sierpinski lattice translates into a self similarity in diffusional flows, and find that expressions for n having a common analytic form can be obtained for sites that are the first- and second-nearest-neighbors to a vertex trap.     

Random Walks with Invariant Loop Probabilities: Stereographic Random Walks

Random walks with invariant loop probabilities comprise a wide family of Markov processes with site-dependent, one-step transition probabilities. The whole family, which includes the simple random walk, emerges from geometric considerations related to the stereographic projection of an underlying geometry into a line. After a general introduction, we focus our attention on the elliptic case: random walks on a circle with built-in reflexing boundaries.     

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.     

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.     

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.     

Stationary Probability and First-Passage Time of Biased Random Walk

In this paper, we consider the stationary probability and first-passage time of biased random walk on 1D chain, where at each step the walker moves to the left and right with probabilities p and q respectively (0≤p, q≤1, p+q=1). We derive exact analytical results for the stationary probability and first-passage time as a function of p and q for the first time. Our results suggest that the first-passage time shows a double power-law F~(N-1)^γ, where the exponent γ=2 for N<|p-q|^-1 and γ=1 for N>|p-q|^-1. Our study sheds useful insights into the biased random-walk process.     

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     

Mean Hitting Time for Random Walks on a Class of Sparse Networks

For random walks on a complex network, the configuration of a network that provides optimal or suboptimal navigation efficiency is meaningful research. It has been proven that a complete graph has the exact minimal mean hitting time, which grows linearly with the network order. In this paper, we present a class of sparse networks G(t) in view of a graphic operation, which have a similar dynamic process with the complete graph; however, their topological properties are different. We capture that G(t) has a remarkable scale-free nature that exists in most real networks and give the recursive relations of several related matrices for the studied network. According to the connections between random walks and electrical networks, three types of graph invariants are calculated, including regular Kirchhoff index, M-Kirchhoff index and A-Kirchhoff index. We derive the closed-form solutions for the mean hitting time of G(t), and our results show that the dominant scaling of which exhibits the same behavior as that of a complete graph. The result could be considered when designing networks with high navigation efficiency.     

The Einstein Relation for Random Walks on Graphs

This paper investigates the Einstein relation; the connection between the volume growth, the resistance growth and the expected time a random walk needs to leave a ball on a weighted graph. The Einstein relation is proved under different set of conditions. In the simplest case it is shown under the volume doubling and time comparison principles. This and the other set of conditions provide the basic framework for the study of (sub-) diffusive behavior of the random walks on weighted graphs.     

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.     

Nonequilibrium Time Reversibility with Maps and Walks

Time-reversible dynamical simulations of nonequilibrium systems exemplify both Loschmidt’s and Zermélo’s paradoxes. That is, computational time-reversible simulations invariably produce solutions consistent with the irreversible Second Law of Thermodynamics (Loschmidt’s) as well as periodic in the time (Zermélo’s, illustrating Poincaré recurrence). Understanding these paradoxical aspects of time-reversible systems is enhanced here by studying the simplest pair of such model systems. The first is time-reversible, but nevertheless dissipative and periodic, the piecewise-linear compressible Baker Map. The fractal properties of that two-dimensional map are mirrored by an even simpler example, the one-dimensional random walk, confined to the unit interval. As a further puzzle the two models yield ambiguities in determining the fractals’ information dimensions. These puzzles, including the classical paradoxes, are reviewed and explored here.     

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.     

A Note on Transience Versus Recurrence for a Branching Random Walk in Random Environment

We consider a branching random walk in random environment on ^d where particles perform independent simple random walks and branch, according to a given offspring distribution, at a random subset of sites whose density tends to zero at infinity. Given that initially one particle starts at the origin, we identify the critical rate of decay of the density of the branching sites separating transience from recurrence, i.e., the progeny hits the origin with probability <1 resp. =1. We show that for d3 there is a dichotomy in the critical rate of decay, depending on whether the mean offspring at a branching site is above or below a certain value related to the return probability of the simple random walk. The dichotomy marks a transition from local to global behavior in the progeny that hits the origin. We also consider the situation where the branching sites occur in two or more types, with different offspring distributions, and show that the classification is more subtle due to a possible interplay between the types. This note is part of a series of papers by the second author and various co-authors investigating the problem of transience versus recurrence for random motions in random media.     

Twice Scattered Particles in a Plane Are Uniformly Distributed

It was recently shown (Physica A 216:299–315, 1995) that in two dimensions the sum of three vectors each of whose lengths is exponentially distributed, whose direction is uniformly distributed and such that the sum of their lengths is l, is uniformly distributed on a disk of radius l. We state here this random walk result in terms of scattering of particles as follows: in two dimensions twice isotropically scattered particles by random (i.e., Poisson distributed) scatterers are uniformly distributed. We show that there is no other dimension d and no other number of scatterings s for which the corresponding result (i.e., uniform distribution on a d-dimensional sphere after s scatterings) holds.     

Random walk with persistence

The exact analytic result is obtained for the Fourier transform of the generating functionF(R,s)= _n=0 s ⁿ P(R,n), whereP(R,n) is the probability density for the end-to-end distanceR inn steps of a random walk with persistence. The moments R ²(n), R ⁴(n), and R ⁶(n) are calculated and approximate results forP(R,n) and R ^–1(n) are given.     

Random walk representations of the Heisenberg model

We develop random walk representations for the spin-S Heisenberg ferromagnet with nearest neighbor interactions. We show that the spin-S Heisenberg model is a diffusion with local times controlled by the spin-S Ising model. As a consequence, expectations for the Heisenberg model conditioned on zero diffusion are shown to be Ising expectations.