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.     

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.     

Stochastic flows,reaction — Diffusion processes,and morphogenesis

Recently, anexact procedure has been introduced [C. A. Walsh and J. J. Kozak,Phys. Rev. Lett. 47:1500 (1981)] for calculating the expected walk length 〈n〉 for a walker undergoing random displacements on a finite or infinite (periodic)d-dimensional lattice with traps (reactive sites). The method (which is based on a classification of the symmetry of the sites surrounding the central deep trap and a coding of the fate of the random walker as it encounters a site of given symmetry) is applied here to several problems in lattice statistics for each of whichexact results are presented. First, we assess the importance of lattice geometry in influencing the efficiency of reaction-diffusion processes in simple and multiple trap systems by reporting values of 〈n〉 for square (cubic) versus hexagonal lattices ind=2, 3. We then show how the method may be applied to variable-step (distance-dependent) walks for a single walker on a given lattice and also demonstrate the calculation of the expected walk length 〈n〉 for the case of multiple walkers. Finally, we make contact with recent discussions of “mixing” by showing that the degree of chaos associated with flows in certain lattice systems can be calibrated by monitoring the lattice walks induced by the Poincaré map of a certain parabolic function.     

From random to self-avoiding walks

A brief review will be given of the current situation in the theory of self-avoiding walks (SAWs). The Domb-Joyce model first introduced in 1972 consists of a random walk on a lattice in which eachN step configuration has a weighting factor Π _i=0 ^N?2 Π_j=i+2/N(1?ωδ_ij). Herei andj are the lattice sites occupied by the ith and jth points of the walk. When ω=0 the model reduces to a standard random walk, and when ω=1 it is a self-avoiding walk. The universality hypothesis of critical phenomena will be used to conjecture the behavior of the model as a function ofω for largeN. The implications for the theory of dilute polymer solutions will be indicated.     

Open Quantum Random Walks on the Half-Line: The Karlin–McGregor Formula,Path Counting and Foster’s Theorem

In this work we consider open quantum random walks on the non-negative integers. By considering orthogonal matrix polynomials we are able to describe transition probability expressions for classes of walks via a matrix version of the Karlin–McGregor formula. We focus on absorbing boundary conditions and, for simpler classes of examples, we consider path counting and the corresponding combinatorial tools. A non-commutative version of the gambler’s ruin is studied by obtaining the probability of reaching a certain fortune and the mean time to reach a fortune or ruin in terms of generating functions. In the case of the Hadamard coin, a counting technique for boundary restricted paths in a lattice is also presented. We discuss an open quantum version of Foster’s Theorem for the expected return time together with applications.     

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.     

Lévy Walk with Multiple Internal States

Lévy walk with multiple internal states can effectively model the motion of particles that don’t immediately move back to the directions or areas which they come from. When the Lévy walk behaves superdiffusion, it is discovered that the non-immediately-repeating property, characterized by the constructed transition matrix, has no influence on the particle’s mean square displacement (MSD) or Pearson coefficient. This is a kind of stable property of Lévy walk. However, if the Lévy walk shows the dynamical behaviors of normal diffusion, then the effect of non-immediately-repeating emerges. For the Lévy walk with some particular transition matrices, it may display nonsymmetric dynamics; in these cases, the behaviors of their variances are detailedly discussed, especially some comparisons with the ones of the continuous time random walks are made (a striking difference is the changes of the exponents of the variances). The first passage time distribution and its average of Lévy walks are simulated, the results of which turn out that the first passage time can distinguish Lévy walks with different transition matrices, while the MSD can not.

     

The XXZ Heisenberg model on random surfaces

We consider integrable models, or in general any model defined by an R-matrix, on random surfaces, which are discretized using random Manhattan lattices. The set of random Manhattan lattices is defined as the set dual to the lattice random surfaces embedded on a regular d-dimensional lattice. They can also be associated with the random graphs of multiparticle scattering nodes. As an example we formulate a random matrix model where the partition function reproduces the annealed average of the XXZ Heisenberg model over all random Manhattan lattices. A technique is presented which reduces the random matrix integration in partition function to an integration over their eigenvalues.     

Lattices of matrices

We study a new class of matrix models, formulated on a lattice. On each site are N states with random energies governed by a gaussian random matrix hamiltonian. The states on different sites are coupled randomly. We calculate the density of and correlation between the eigenvalues of the total hamiltonian in the large-N limit. We find that this correlation exhibits the same type of universal behavior we discovered recently. Several derivations of this result are given. This class of random matrices allows us to model the transition between the “localized” and “extended” regimes within the limited context of random matrix theory.     

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.     

Random walks in asymmetric random environments

We consider random walks on Z ^d with transition ratesp(x, y) given by a random matrix. Ifp is a small random perturbation of the simple random walk, we show that the walk remains diffusive for almost all environmentsp ifd>2. The result also holds for a continuous time Markov process with a random drift. The corresponding path space measures converge weakly, in the scaling limit, to the Wiener process, for almost everyp.Dedicated to Joel Lebowitz on his 60th birthdaySupported by NSF-grant DMS-8903041     

Self-avoiding random walk with multiple site weightings and restrictions

We introduce a new class of models for polymer collapse, given by random walks on regular lattices which are weighted according to multiple site visits. A Boltzmann weight omegal is assigned to each (l+1)-fold visited lattice site, and self-avoidance is incorporated by restricting to a maximal number K of visits to any site via setting omegal=0 for l>or=K. In this Letter we study this model on the square and simple cubic lattices for the case K=3. Moreover, we consider a variant of this model, in which we forbid immediate self-reversal of the random walk. We perform simulations for random walks up to n=1024 steps using FlatPERM, a flat histogram stochastic growth algorithm. We find evidence that the existence of a collapse transition depends sensitively on the details of the model and has an unexpected dependence on dimension.     

Irreversibility of a quantum walk induced by controllable decoherence employing random unitary operations

Quantum walk is different from random walk in reversibility and interference. Observation of the reduced re- versibility in a realistic quantum walk is of scientific interest in understanding the unique quantum behavior. We propose an idea to experimentally investigate the decoherence-induced irreversibility of quantum walks with trapped ions in phase space via the average fidelity decay. By introducing two controllable decoherence sources, i.e., the phase damping channel (i.e., dephasing) and the high temperature amplitude reservoir (i.e., dissipation), in the intervals between the steps of quantum walk, we find that the high temperature amplitude reservoir shows more detrimental effects than the phase damping channel on quantum walks. Our study also shows that the average fidelity decay works better than the position variance for characterizing the transition from quantum walks to random walk. Experimental feasibility to monitor the irreversibility is justified using currently available techniques.     

An age-dependent approach to random walks on disordered lattices

We derive a new approach for the stochastic transport in random systems, starting from a phenomenological master equation with random transition rates. Our method combines the effective medium approximation with age-dependent dynamics. Within the framework of our approximation, the static disorder may be described by means of a system of age-dependent master equations. For translationally invariant systems which obey certain separability conditions, the approach is equivalent with the continuous time random walk theory. Moreover, for self-avoiding random walks our effective medium approximation is exact. For non self-avoiding random walks, the approximation neglects the correlations between successive transitions leading to closed paths on the lattice.     

Locally Perturbed Random Walks with Unbounded Jumps

Szász and Telcs (J. Stat. Phys. 26(3), 1981) have shown that for the diffusively scaled, simple symmetric random walk, weak convergence to the Brownian motion holds even in the case of local impurities if d≥2. The extension of their result to finite range random walks is straightforward. Here, however, we are interested in the situation when the random walk has unbounded range. Concretely we generalize the statement of Szász and Telcs (J. Stat. Phys. 26(3), 1981) to unbounded random walks whose jump distribution belongs to the domain of attraction of the normal law. We do this first: for diffusively scaled random walks on Z ^d (d≥2) having finite variance; and second: for random walks with distribution belonging to the non-normal domain of attraction of the normal law. This result can be applied to random walks with tail behavior analogous to that of the infinite horizon Lorentz-process; these, in particular, have infinite variance, and convergence to Brownian motion holds with the superdiffusive \(\sqrt{n\log n}\) scaling.     

Comment on a paper by G. H. Weiss,S. Havlin,and A. Bunde

A simple proof is pointed out for the asymptotic exponential decay of then-step survival probability of a random walk on a finite lattice with traps in the limit asn . Some bounds are mentioned, which are valid for finiten and for symmetric random walks.     

Random walks with ‘spontaneous emission’ on lattices with periodically distributed imperfect traps

We study random walks on d-dimensional lattices with periodically distributed traps in which the walker has a finite probability per step of disappearing from the lattice and a finite probability of escaping from a trap. General expressions are derived for the total probability that the walk ends in a trap and for the moments of the number of steps made before this happens if it does happen. The analysis is extended to lattices with more types of traps and to a model where the trapping occurs during special steps. Finally, the Green's function at the origin G(0; z) for a finite lattice with periodic boundary conditions, which enters into the main expressions, is studied more closely. A generalization of an expression for G(0; 1) for the square lattice given by Montroll to values of z different from, but close to, 1 is derived.     

Random walks on sparsely periodic and random lattices: I. Random walk properties from lattice bond enumeration

We have developed a new technique for calculating certain asymptotic random walk properties on sparsely periodic and related random lattices in two and three dimensions. This technique is based on an ansatz which relates the number of lattice bonds in “irreducible lattice fragments” to the number of steps along these bonds. We show that certain random walk properties can be calculated very simply on the basis of this ansatz and that they depend only on the density of bonds and not on the arrangement of the bonds within the lattice. The random walk properties calculated here (mean square displacements, number of distinct sites visited, probability of return to the origin) are in complete agreement with results obtained earlier via generating function techniques. A subsequent paper contains generating function calculations which verify a number of new results presented here, such as mean occupation frequency of lattice sites, and a proof of our basic assumption on the relation between the number of lattice bonds and random walk steps.     

Survival,Extinction and Approximation of Discrete-time Branching Random Walks

We consider a general discrete-time branching random walk on a countable set X. We relate local, strong local and global survival with suitable inequalities involving the first-moment matrix M of the process. In particular we prove that, while the local behavior is characterized by M, the global behavior cannot be completely described in terms of properties involving M alone. Moreover we show that locally surviving branching random walks can be approximated by sequences of spatially confined and stochastically dominated branching random walks which eventually survive locally if the (possibly finite) state space is large enough. An analogous result can be achieved by approximating a branching random walk by a sequence of multitype contact processes and allowing a sufficiently large number of particles per site. We compare these results with the ones obtained in the continuous-time case and we give some examples and counterexamples.