The drift of a one-dimensional self-avoiding random walk

Summary We prove that a self-avoiding random walk on the integers with bounded increments grows linearly. We characterize its drift in terms of the Frobenius eigenvalue of a certain one parameter family of primitive matrices. As an important tool, we express the local times as a two-block functional of a certain Markov chain, which is of independent interest.     

Biased random walk in a one-dimensional percolation model

We consider random walk with a nonzero bias to the right, on the infinite cluster in the following percolation model: take i.i.d. bond percolation with retention parameter p$p$ on the so-called infinite ladder, and condition on the event of having a bi-infinite path from −∞$-\infty$ to ∞$\infty$. The random walk is shown to be transient, and to have an asymptotic speed to the right which is strictly positive or zero depending on whether the bias is below or above a certain critical value which we compute explicitly.     

Shift-coupling and a zero-one law for random walk in random environment

This paper discusses several aspects of shift-coupling for random walk in random environment.     

The mixing advantage for bounded random variables

Corresponding to n independent non-negative random variables X₁,…,X_n concentrated on a bounded interval set are values M₁,…,M_n, where each M_i is the expected value of the maximum of n independent copies of X_i. We obtain a sharp upper bound for the expected value of the maximum of X₁,…,X_n in terms of M₁,…,M_n. This inequality is sharp. A similar result is demonstrated for minima.     

Annealed deviations of random walk in random scenery

Let (Zn)_n∈N be a d-dimensional random walk in random scenery, i.e., with (Sk)_k∈N0 a random walk in Zd and (Y(z))_z∈Zd an i.i.d. scenery, independent of the walk. The walker's steps have mean zero and some finite exponential moments. We identify the speed and the rate of the logarithmic decay of for various choices of sequences n(bn) in [1,∞). Depending on n(bn) and the upper tails of the scenery, we identify different regimes for the speed of decay and different variational formulas for the rate functions. In contrast to recent work [A. Asselah, F. Castell, Large deviations for Brownian motion in a random scenery, Probab. Theory Related Fields 126 (2003) 497-527] by A. Asselah and F. Castell, we consider sceneries unbounded to infinity. It turns out that there are interesting connections to large deviation properties of self-intersections of the walk, which have been studied recently by X. Chen [X. Chen, Exponential asymptotics and law of the iterated logarithm for intersection local times of random walks, Ann. Probab. 32 (4) 2004].     

A note on random walk in random scenery

We consider a random walk in random scenery {Xn=η(S₀)+?+η(Sn),n∈N}, where a centered walk {Sn,n∈N} is independent of the scenery {η(x),x∈Zd}, consisting of symmetric i.i.d. with tail distribution P(η(x)>t)∼exp(−cαtα), with 1?α<d/2. We study the probability, when averaged over both randomness, that {Xn>ny} for y>0, and n large. In this note, we show that the large deviation estimate is of order exp(−ca(ny)), with a=α/(α+1).     

Zeno's walk: A random walk with refinements

Summary. A self-modifying random walk on is derived from an ordinary random walk on the integers by interpolating a new vertex into each edge as it is crossed. This process converges almost surely to a random variable which is totally singular with respect to Lebesgue measure, and which is supported on a subset of having Hausdorff dimension less than , which we calculate by a theorem of Billingsley. By generating function techniques we then calculate the exponential rate of convergence of the process to its limit point, which may be taken as a bound for the convergence of the measure in the Wasserstein metric. We describe how the process may viewed as a random walk on the space of monotone piecewise linear functions, where moves are taken by successive compositions with a randomly chosen such function. Received: 20 November 1995 / In revised form: 14 May 1996     

Logarithmic speeds for one-dimensional perturbed random walks in random environments

We study the random walk in a random environment on Z⁺={0,1,2,…}${\mathbb{Z}}^{+}=\{0,1,2,\dots \}$, where the environment is subject to a vanishing (random) perturbation. The two particular cases that we consider are: (i) a random walk in a random environment perturbed from Sinai’s regime; (ii) a simple random walk with a random perturbation. We give almost sure results on how far the random walker is from the origin, for almost every environment. We give both upper and lower almost sure bounds. These bounds are of order (logt)^β${(logt)}^{\beta }$, for β∈(1,∞)$\beta \in (1,\infty )$, depending on the perturbation. In addition, in the ergodic cases, we give results on the rate of decay of the stationary distribution.     

Precise large deviation estimates for a one-dimensional random walk in a random environment

ω_x } (taking values in the interval [1/2, 1)), which serve as an environment. This environment defines a random walk {X _k } (called a RWRE) which, when at x, moves one step to the right with probability ω _x , and one step to the left with probability 1 −ωx. Solomon (1975) determined the almost-sure asymptotic speed (= rate of escape) of a RWRE, in a more general set-up. Dembo, Peres and Zeitouni (1996), following earlier work by Greven and den Hollander (1994) on the quenched case, have computed rough tail asymptotics for the empirical mean of the annealed RWRE. They conjectured the form of the rate function in a full LDP. We prove in this paper their conjecture. The proof is based on a “coarse graining scheme” together with comparison techniques. Received: 22 July 1997/Revised version: 15 June 1998     

Moderate deviations for a random walk in random scenery

We investigate the cumulative scenery process associated with random walks in independent, identically distributed random sceneries under the assumption that the scenery variables satisfy Cramér’s condition. We prove moderate deviation principles in dimensions d≥2$d\ge 2$, covering all those regimes where rate and speed do not depend on the actual distribution of the scenery. For the case d≥4$d\ge 4$ we even obtain precise asymptotics for the probability of a moderate deviation, extending a classical central limit theorem of Kesten and Spitzer. For d≥3$d\ge 3$, an important ingredient in the proofs are new concentration inequalities for self-intersection local times of random walks, which are of independent interest, whilst for d=2$d=2$ we use a recent moderate deviation result for self-intersection local times, which is due to Bass, Chen and Rosen.     

Heat-kernel estimates for random walk among random conductances with heavy tail

We study models of discrete-time, symmetric, Z^d${\mathbb{Z}}^d$-valued random walks in random environments, driven by a field of i.i.d. random nearest-neighbor conductances _ωxy∈[0,1]${\omega }_{xy}\in [0,1]$, with polynomial tail near 0 with exponent γ>0$\gamma >0$. We first prove for all d≥5$d\ge 5$ that the return probability shows an anomalous decay (non-Gaussian) that approaches (up to sub-polynomial terms) a random constant times n⁻²$n^{-2}$ when we push the power γ$\gamma$ to zero. In contrast, we prove that the heat-kernel decay is as close as we want, in a logarithmic sense, to the standard decay n^−d/2$n^{-d/2}$ for large values of the parameter γ$\gamma$.     

Effort associated with a class of random optimization methods

When differentiability is not assumed random procedures can be successfully used to estimate the extreme values of a given function. For a class of such algorithms we treat the problem of estimating the mean effort.Research partially supported by CNPq-Brazil.     

Non-homogeneous random walks on a semi-infinite strip

We study the asymptotic behaviour of Markov chains (_Xn,_ηn)$(X_n,{\eta }_n)$ on _Z+×S${\mathbb{Z}}_{+}\times S$, where _Z+${\mathbb{Z}}_{+}$ is the non-negative integers and S$S$ is a finite set. Neither coordinate is assumed to be Markov. We assume a moments bound on the jumps of _Xn$X_n$, and that, roughly speaking, _ηn${\eta }_n$ is close to being Markov when _Xn$X_n$ is large. This departure from much of the literature, which assumes that _ηn${\eta }_n$ is itself a Markov chain, enables us to probe precisely the recurrence phase transitions by assuming asymptotically zero drift for _Xn$X_n$ given _ηn${\eta }_n$. We give a recurrence classification in terms of increment moment parameters for _Xn$X_n$ and the stationary distribution for the large- X$X$ limit of _ηn${\eta }_n$. In the null case we also provide a weak convergence result, which demonstrates a form of asymptotic independence between _Xn$X_n$ (rescaled) and _ηn${\eta }_n$. Our results can be seen as generalizations of Lamperti’s results for non-homogeneous random walks on _Z+${\mathbb{Z}}_{+}$ (the case where S$S$ is a singleton). Motivation arises from modulated queues or processes with hidden variables where _ηn${\eta }_n$ tracks an internal state of the system.     

On the local time of random walk on the 2-dimensional comb

We study the path behaviour of general random walks, and that of their local times, on the 2-dimensional comb lattice C² that is obtained from Z² by removing all horizontal edges off the x-axis. We prove strong approximation results for such random walks and also for their local times. Concentrating mainly on the latter, we establish strong and weak limit theorems, including Strassen-type laws of the iterated logarithm, Hirsch-type laws, and weak convergence results in terms of functional convergence in distribution.     

Tail expansions for the distribution of the maximum of a random walk with negative drift and regularly varying increments

Let F$F$ be a distribution function with negative mean and regularly varying right tail. Under a mild smoothness condition we derive higher order asymptotic expansions for the tail distribution of the maxima of the random walk generated by F$F$. The expansion is based on an expansion for the right Wiener–Hopf factor which we derive first. An application to ruin probabilities is developed.     

Random walk on the infinite cluster of the percolation model

Summary We consider random walk on the infinite cluster of bond percolation on ^d . We show that, in the supercritical regime whend3, this random walk is a.s. transient. This conclusion is achieved by considering the infinite percolation cluster as a random electrical network in which each open edge has unit resistance. It is proved that the effective resistance of this network between a nominated point and the points at infinity is almost surely finite.G.R.G. acknowledges support from Cornell University, and also partial support by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell UniversityH.K. was supported in part by the N.S.F. through a grant to Cornell University