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.     

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.     

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).     

The drift of a one-dimensional self-repellent random walk with bounded increments

Summary Consider a one-dimensional walk (S _k ) _k having steps of bounded size, and weight the probability of the path with some factor 1–(0,1) for every single self-intersection up to timen. We prove thatS _n /S S converges towards some deterministic number called the effective drift of the self-repellent walk. Furthermore, this drift is shown to tend to the basic drift as tends to 0 and, as tends to 1, to the self-avoiding walk's drift which is introduced in [10]. The main tool of the present paper is a representation of the sequence of the local times as a functional of a certain Markov process.Partially supported by Swiss National Sciences Foundation Grant 20-36305.92     

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$.     

Maximum likelihood estimator consistency for a ballistic random walk in a parametric random environment

We consider a one dimensional ballistic random walk evolving in an i.i.d. parametric random environment. We provide a maximum likelihood estimation procedure of the parameters based on a single observation of the path till the time it reaches a distant site, and prove that the estimator is consistent as the distant site tends to infinity. Our main tool consists in using the link between random walks and branching processes in random environments and explicitly characterising the limiting distribution of the process that arises. We also explore the numerical performance of our estimation procedure.     

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.     

Moments, moderate and large deviations for a branching process in a random environment

Let (Z_n) be a supercritical branching process in a random environment ξ, and W be the limit of the normalized population size Z_n/E[Z_n|ξ]. We show large and moderate deviation principles for the sequence logZ_n (with appropriate normalization). For the proof, we calculate the critical value for the existence of harmonic moments of W, and show an equivalence for all the moments of Z_n. Central limit theorems on W−W_n and logZ_n are also established.     

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.     

Rates of convergence of random walk on distance regular graphs

When run on any non-bipartite q-distance regular graph from a family containing graphs of arbitrarily large diameter d, we show that d steps are necessary and sufficient to drive simple random walk to the uniform distribution in total variation distance, and that a sharp cutoff phenomenon occurs. For most examples, we determine the set on which the variation distance is achieved, and the precise rate at which it decays. The upper bound argument uses spectral methods – combining the usual Cauchy-Schwarz bound on variation distance with a bound on the tail probability of a first-hitting time, derived from its generating function. Received: 2 April 1997 / Revised version: 10 May 1998     

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     

Brownian motion and random walk perturbed at extrema

Let b _t be Brownian motion. We show there is a unique adapted process x _t which satisfies dx _t = db _t except when x _t is at a maximum or a minimum, when it receives a push, the magnitudes and directions of the pushes being the parameters of the process. For some ranges of the parameters this is already known. We show that if a random walk close to b _t is perturbed properly, its paths are close to those of x _t . Received: 15 October 1997 / Revised version: 18 May 1998     

Central limit theorems for a supercritical branching process in a random environment

For a supercritical branching process (Z_n) in a stationary and ergodic environment ξ, we study the rate of convergence of the normalized population W_n=Z_n/E[Z_n|ξ] to its limit W_∞: we show a central limit theorem for W_∞−W_n with suitable normalization and derive a Berry-Esseen bound for the rate of convergence in the central limit theorem when the environment is independent and identically distributed. Similar results are also shown for W_n+k−W_n for each fixed k∈N^∗.     

Sharp critical behavior for pinning models in a random correlated environment

This article investigates the effect for random pinning models of long range power-law decaying correlations in the environment. For a particular type of environment based on a renewal construction, we are able to sharply describe the phase transition from the delocalized phase to the localized one, giving the critical exponent for the (quenched) free-energy, and proving that at the critical point the trajectories are fully delocalized. These results contrast with what happens both for the pure model (i.e., without disorder) and for the widely studied case of i.i.d. disorder, where the relevance or irrelevance of disorder on the critical properties is decided via the so-called Harris Criterion (Harris, 1974) [21].     

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     

Further results for semiregenerative phenomena

A theory of semiregenerative phenomena was developed by the author. The set of points at which such a phenomenon occurs is called a semi regenerative set. There is a correspondence between a semiregenerative set and the range of a Markov subordinator with a unit drift (or a Markov renewal process in the discrete time case). Prabhu, Tang, and Zhu showed that the properties of semiregenerative sets associated with Markov random walks completely characterize the fluctuation behaviour of these processes in the nondegenerate case and also established a Wiener-Hopf factorization based on these sets. These results are surveyed in this paper.     

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.