Almost sure estimates for the concentration neighborhood of Sinai’s walk

We consider Sinai’s random walk in random environment. We prove that infinitely often (i.o.) the size of the concentration neighborhood of this random walk is bounded almost surely. We also get that i.o. the maximal distance between two favorite sites is bounded almost surely.     

Tree-indexed random walks on groups and first passage percolation

Summary Suppose that i.i.d. random variables are attached to the edges of an infinite tree. When the tree is large enough, the partial sumsS along some of its infinite paths will exhibit behavior atypical for an ordinary random walk. This principle has appeared in works on branching random walks, first-passage percolation, and RWRE on trees. We establish further quantitative versions of this principle, which are applicable in these settings. In particular, different notions of speed for such a tree-indexed walk correspond to different dimension notions for trees. Finally, if the labeling variables take values in a group, then properties of the group (e.g., polynomial growth or a nontrivial Poisson boundary) are reflected in the sample-path behavior of the resulting tree-indexed walk.Partially supported by a grant from the Landau Center for Mathematical AnalysisPartially supported by NSF grant DMS-921 3595     

Quenched invariance principle for simple random walk on discrete point processes

We consider the simple random walk on random graphs generated by discrete point processes. This random walk moves on graphs whose vertex set is a random subset of a cubic lattice and whose edges are lines between any consecutive vertices on lines parallel to each coordinate axis. Under the assumption that the discrete point processes are finitely dependent and stationary, we prove that the quenched invariance principle holds, i.e., for almost every configuration of the point process, the path distribution of the walk converges weakly to that of a Brownian motion.     

Crossing velocities for an annealed random walk in a random potential

We consider a random walk in an i.i.d. non-negative potential on the d-dimensional integer lattice. The walk starts at the origin and is conditioned to hit a remote location y on the lattice. We prove that the expected time under the annealed path measure needed by the random walk to reach y grows only linearly in the distance from y to the origin. In dimension 1 we show the existence of the asymptotic positive speed.     

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 problem of the most visited site in random environment

We prove that the process of the most visited site of Sinai's simple random walk in random environment is transient. The rate of escape is characterized via an integral criterion. Our method also applies to a class of recurrent diffusion processes with random potentials. It is interesting to note that the corresponding problem for the usual symmetric Bernoulli walk or for Brownian motion remains open. Received: 17 April 1998     

Quenched tail estimate for the random walk in random scenery and in random layered conductance

We discuss the quenched tail estimates for the random walk in random scenery. The random walk is the symmetric nearest neighbor walk and the random scenery is assumed to be independent and identically distributed, non-negative, and has a power law tail. We identify the long time asymptotics of the upper deviation probability of the random walk in quenched random scenery, depending on the tail of scenery distribution and the amount of the deviation. The result is in turn applied to the tail estimates for a random walk in random conductance which has a layered structure.     

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     

Some recent advances in theory and simulation of fractional diffusion processes

To offer an insight into the rapidly developing theory of fractional diffusion processes, we describe in some detail three topics of current interest: (i) the well-scaled passage to the limit from continuous time random walk under power law assumptions to space-time fractional diffusion, (ii) the asymptotic universality of the Mittag–Leffler waiting time law in time-fractional processes, (iii) our method of parametric subordination for generating particle trajectories.     

Limiting behavior of a diffusion in an asymptotically stable environment

Let V be a two sided random walk and let X denote a real valued diffusion process with generator . This process is the continuous equivalent of the one-dimensional random walk in random environment with potential V. Hu and Shi (1997) described the Lévy classes of X in the case where V behaves approximately like a Brownian motion. In this paper, based on some fine results on the fluctuations of random walks and stable processes, we obtain an accurate image of the almost sure limiting behavior of X when V behaves asymptotically like a stable process. These results also apply for the corresponding random walk in random environment.     

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.     

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

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.     

Triangular array limits for continuous time random walks

A continuous time random walk (CTRW) is a random walk subordinated to a renewal process, used in physics to model anomalous diffusion. Transition densities of CTRW scaling limits solve fractional diffusion equations. This paper develops more general limit theorems, based on triangular arrays, for sequences of CTRW processes. The array elements consist of random vectors that incorporate both the random walk jump variable and the waiting time preceding that jump. The CTRW limit process consists of a vector-valued Lévy process whose time parameter is replaced by the hitting time process of a real-valued nondecreasing Lévy process (subordinator). We provide a formula for the distribution of the CTRW limit process and show that their densities solve abstract space–time diffusion equations. Applications to finance are discussed, and a density formula for the hitting time of any strictly increasing subordinator is developed.     

Scaling limits of coupled continuous time random walks and residual order statistics through marked point processes

A continuous time random walk (CTRW) is a random walk in which both spatial changes represented by jumps and waiting times between the jumps are random. The CTRW is coupled if a jump and its preceding or following waiting time are dependent random variables (r.v.), respectively. The aim of this paper is to explain the occurrence of different limit processes for CTRWs with forward- or backward-coupling in Straka and Henry (2011) [37] using marked point processes. We also establish a series representation for the different limits. The methods used also allow us to solve an open problem concerning residual order statistics by LePage (1981) [20].     

Local asymptotics for the time of first return to the origin of transient random walk

We consider a transient random walk on Z^d which is asymptotically stable, without centering, in a sense which allows different norming for each component. The paper is devoted to the asymptotics of the probability of the first return to the origin of such a random walk at time n.     

Random walks on quasisymmetric functions

Conditions are provided under which an endomorphism on quasisymmetric functions gives rise to a left random walk on the descent algebra which is also a lumping of a left random walk on permutations. Spectral results are also obtained. Several important random walks are now realized this way: Stanley's QS-distribution results from endomorphisms given by evaluation maps, a-shuffles result from the ath convolution power of the universal character, and the Tchebyshev operator of the second kind introduced recently by Ehrenborg and Readdy yields traditional riffle shuffles. A conjecture of Ehrenborg regarding the spectra for a family of random walks on ab-words is proven. A theorem of Stembridge from the theory of enriched P-partitions is also recovered as a special case.     

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.     

Tandem antagonistic games

We study an antagonistic sequential game of two players that undergoes two phases. Each phase is modeled by multi-dimensional random walk processes. During phase 1 (or game 1), the players exchange a series of random strikes of random magnitudes. Game 1 ends whenever one of the players sustains damages in excess of some lower threshold. However, the total damage does not exceed another upper threshold which allows the game to continue. Phase 2 (game 2) is run by another combination of random walk processes. At some point of phase 2, one of the players, after sustaining damages in excess of its third threshold, is ruined and he loses the entire game. We predict that moment, along with the total casualties to both players, and other critical information; all in terms of tractable functionals. The entire game is analyzed by tools of fluctuation theory.     

Maxima of branching random walks vs. independent random walks

In recent years several authors have obtained limit theorems for the location of the right most particle in a supercritical branching random walk. In this paper we will consider analogous problems for an exponentially growing number of independent random walks. A comparison of our results with the known results of branching random walk then identifies the limit behaviors which are due to the number of particles and those which are determined by the branching structure.