A renormalization result for the intersection local time of lattice random walks ind≧3 dimensions

In this paper we derive some general conditions on stable walks inZ ^d , under which the central limit theorem holds for their normalized intersection local time. In particular, we prove that the process given by the normalized intersection local time of the simple random walk inZ ^d , withd3, is weakly convergent to the standard Brownian motion.BiBoS; SFB 237 Bochum-Essen-Düsseldorf; CERFIM, Locarno.     

The Upper Critical Dimension of the Abelian Sandpile Model

The existing estimation of the upper critical dimension of the Abelian Sandpile Model is based on a qualitative consideration of avalanches as self-avoiding branching processes. We find an exact representation of an avalanche as a sequence of spanning subtrees of two-component spanning trees. Using equivalence between chemical paths on the spanning tree and loop-erased random walks, we reduce the problem to determination of the fractal dimension of spanning subtrees. Then the upper critical dimension d _u=4 follows from Lawler's theorems for intersection probabilities of random walks and loop-erased random walks.     

Propriétés d'intersection des marches aléatoires

We study intersection properties of multi-dimensional random walks. LetX andY be two independent random walks with values in ? ^d (d≦3), satisfying suitable moment assumptions, and letI _n denote the number of common points to the paths ofX andY up to timen. The sequence (I _n ), suitably normalized, is shown to converge in distribution towards the “intersection local time” of two independent Brownian motions. Results are applied to the proof of a central limit theorem for the range of a two-dimensional recurrent random walk, thus answering a question raised by N. C. Jain and W. E. Pruitt.     

Are random walks random?

Random walks have been created using the pseudo-random generators in different computer language compilers (BASIC, PASCAL, FORTRAN, C++) using a Pentium processor. All the obtained paths have apparently a random behavior for short walks (2¹⁴ steps). From long random walks (2³³ steps) different periods have been found, the shortest being 2¹⁸ for PASCAL and the longest 2³¹ for FORTRAN and C++, while BASIC had a 2²⁴ steps period. The BASIC, PASCAL and FORTRAN long walks had even (2 or 4) symmetries. The C++ walk systematically roams away from the origin. Using deviations from the mean-distance rule for random walks, d² ∝ N, a more severe criterion is found, e.g. random walks generated by a PASCAL compiler fulfills this criterion to N < 10 000.     

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     

Intersections of random walks. A direct renormalization approach

Various intersection probabilities of independent random walks ind dimensions are calculated analytically by a direct renormalization method, adapted from polymer physics. This heuristic approach, based on Edwards' continuum model, leads to a straightforward derivation and also to refinements of Lawler's results for the simultaneous intersections of two walks in ⁴, or three walks in ³. These results are generalized toP walks in ^d *, ,P2. Ford<4, an infinite set of universal critical exponents _L ,L1, are derived. They govern the asymptotic probability thatL star walks in ^d , with a common origin, do not intersect before timeS. The _L 's are calculated up to orderO(²), whered=4–. This information is used to calculate the probability that a set of independent random walks in ^d or ^d ,d4, (respectivelyd3) form a given topological networks of multiple intersection points, in the absence of any other double point (respectively triple point). This is generalized to a network in dimension with exclusion ofP-tuple points. The method is quite general and can be used to calculate any critical intersection probability, and provides the probabilist with a large variety of exact results (yet to be proven rigorously).     

Diffusion on two-dimensional percolation clusters with multifractal jump probabilities

By means of Monte Carlo simulations we studied the properties of diffusion limited recombination reactions (DLRR's) and random walks on two dimensional incipient percolation clusters with multifractal jump probabilities. We claim that, for these kind of geometric and energetic heterogeneous substrata, the long time behavior of the particle density in a DLRR is determined by a random walk exponent. It is also suggested that the exploration of a random walk is compact. It is considered a general case of intersection ind euclidean dimension of a random fractal of dimension D_F and a multifractal distribution of probabilities of dimensionsD _q (q real), where the two dimensional incipient percolation clusters with multifractal jump probabilities are particular examples. We argue that the object formed by this intersection is a multifractal of dimensionsD' _q =D _q +D _F -d, for a finite interval ofq.     

Loop-Erased Random Walk on a Torus in Dimensions 4 and Above

We show that the statistics of loop erased random walks above the upper critical dimension, 4, are different between the torus and the full space. The typical length of the path connecting a pair of sites at distance L, which scales as L² in the full space, changes under the periodic boundary conditions to L^d/2. The results are precise for dimensions ≥5; for the dimension d=4 we prove an upper bound, conjecturally sharp up to subpolyonmial factors.     

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.     

Existence of the Harmonic Measure for Random Walks on Graphs and in Random Environments

We give a sufficient condition for the existence of the harmonic measure from infinity of transient random walks on weighted graphs. In particular, this condition is verified by the random conductance model on ? ^d , d≥3, when the conductances are i.i.d. and the bonds with positive conductance percolate. The harmonic measure from infinity also exists for random walks on supercritical clusters of ?². This is proved using results of Barlow (Ann. Probab. 32:3024–3084, 2004) and Barlow and Hambly (Electron. J. Probab. 14(1):1–27, 2009).     

Intersection properties of simple random walks: A renormalization group approach

We study estimates for the intersection probability,g(m), of two simple random walks on lattices of dimensiond=4, 4– as a problem in Euclidean field theory. We rigorously establish a renormalization group flow equation forg(m) and bounds on the -function which show that, ind=4,g(m) tends to zero logarithmically as the killing rate (mass)m tends to zero, and that the fixed point,g*, ind=4– is bounded by const' g*const. Our methods also yield estimates on the intersection probability of three random walks ind=3, 3–. For =0, these results were first obtained by Lawler [1].     

Continuous-Time Quantum Walk on Integer Lattices and Homogeneous Trees

This paper is concerned with the continuous-time quantum walk on ℤ, ℤ ^d , and infinite homogeneous trees. By using the generating function method, we compute the limit of the average probability distribution for the general isotropic walk on ℤ, and for nearest-neighbor walks on ℤ ^d and infinite homogeneous trees. In addition, we compute the asymptotic approximation for the probability of the return to zero at time t in all these cases.     

Entropic repulsion of the lattice free field

Consider the massless free field on thed-dimensional lattice ^d ,d3; that is the centered Gaussian field on with covariances given by the Green function of the simple random walk on ^d . We show that the probability, that all the spins are positive in a box of volumeN ^d , decays exponentially at a rate of orderN ^d–2 logN and compute explicitly the corresponding constant in terms of the capacity of the unit cube. The result is extended to a class of transient random walks with transition functions in the domain of the normal and -stable law.This research was partially supported by the foundation for promotion of research at the Technion.     

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.     

Random walk statistics on fractal structures

We consider some statistical properties of simple random walks on fractal structures viewed as networks of sites and bonds: range, renewal theory, mean first passage time, etc. Asymptotic behaviors are shown to be controlled by the fractal (¯d) and spectral (¯d) dimensionalities of the considered structure. A simple decimation procedure giving the value of (¯d) is outlined and illustrated in the case of the Sierpinski gaskets. Recent results for the trapping problem, the self-avoiding walk, and the true-self-avoiding walk are briefly reviewed. New numerical results for diffusion on percolation clusters are also presented.     

Scaling of Loop-Erased Walks in 2 to 4 Dimensions

We simulate loop-erased random walks on simple (hyper-)cubic lattices of dimensions 2, 3 and 4. These simulations were mainly motivated to test recent two loop renormalization group predictions for logarithmic corrections in d=4, simulations in lower dimensions were done for completeness and in order to test the algorithm. In d=2, we verify with high precision the prediction D=5/4, where the number of steps n after erasure scales with the number N of steps before erasure as n∼N ^D/2. In d=3 we again find a power law, but with an exponent different from the one found in the most precise previous simulations: D=1.6236±0.0004. Finally, we see clear deviations from the naive scaling n∼N in d=4. While they agree only qualitatively with the leading logarithmic corrections predicted by several authors, their agreement with the two-loop prediction is nearly perfect.     

Mean first-passage time for random walks on undirected networks

In this paper, by using two different techniques we derive an explicit formula for the mean first-passage time (MFPT) between any pair of nodes on a general undirected network, which is expressed in terms of eigenvalues and eigenvectors of an associated matrix similar to the transition matrix. We then apply the formula to derive a lower bound for the MFPT to arrive at a given node with the starting point chosen from the stationary distribution over the set of nodes. We show that for a correlated scale-free network of size N with a degree distribution P(d) ∼ d ^−γ , the scaling of the lower bound is N ^1−1/γ . Also, we provide a simple derivation for an eigentime identity. Our work leads to a comprehensive understanding of recent results about random walks on complex networks, especially on scale-free networks.     

The Effect of Disorder on the Free-Energy for the Random Walk Pinning Model: Smoothing of the Phase Transition and Low Temperature Asymptotics

We consider the continuous time version of the Random Walk Pinning Model (RWPM), studied in (Berger and Toninelli (Electron. J. Probab., to appear) and Birkner and Sun (Ann. Inst. Henri Poincaré Probab. Stat. 46:414–441, 2010; ). Given a fixed realization of a random walk Y on ℤ ^d with jump rate ρ (that plays the role of the random medium), we modify the law of a random walk X on ℤ ^d with jump rate 1 by reweighting the paths, giving an energy reward proportional to the intersection time L_t(X,Y)=ò₀^t 1_Xs=Ys dsL_{t}(X,Y)=\int_{0}^{t} \mathbf {1}_{X_{s}=Y_{s}}\,\mathrm {d}s: the weight of the path under the new measure is exp (βL _t (X,Y)), β∈ℝ. As β increases, the system exhibits a delocalization/localization transition: there is a critical value β _c , such that if β>β _c the two walks stick together for almost-all Y realizations. A natural question is that of disorder relevance, that is whether the quenched and annealed systems have the same behavior. In this paper we investigate how the disorder modifies the shape of the free energy curve: (1) We prove that, in dimension d≥3, the presence of disorder makes the phase transition at least of second order. This, in dimension d≥4, contrasts with the fact that the phase transition of the annealed system is of first order. (2) In any dimension, we prove that disorder modifies the low temperature asymptotic of the free energy.     

Diffusion of directed polymers in a strong random environment

We consider a system of random walks or directed polymers interacting with an environment which is random in space and time. It was shown by Imbrie and Spencer that in spatial dimensions three or above the behavior is diffusive if the directed polymer interacts weakly with the environment and if the random environment follows the Bernoulli distribution. Under the same assumption on the random environment as that of Imbrie and Spencer, we establish that in spatial dimensions four or above the behavior is still diffusive even when the directed polymer interacts strongly with the environment. More generally, we can prove that, if the random environment is bounded and if the supremum of the support of the distribution has a positive mass, then there is an integerd ₀ such that in dimensions higher thand ₀ the behavior of the random polymer is always diffusive.     

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.