Large deviations in the reinforced random walk model on trees

In this paper, we consider the linearly reinforced and the once-reinforced random walk models in the transient phase on trees. We show the large deviations for the upper tails for both models. We also show the exponential decay for the lower tail in the once-reinforced random walk model. However, the lower tail is in polynomial decay for the linearly reinforced random walk model.     

The monotonicity of the probability of return into the source in models of branching random walks

The paper discusses two models of a branching random walk on a many-dimensional lattice with birth and death of particles at a single node being the source of branching. The random walk in the first model is assumed to be symmetric. In the second model an additional parameter is introduced which enables “artificial” intensification of the prevalence of branching or walk at the source and, as the result, violating the symmetry of the random walk. The monotonicity of the return probability into the source is proved for the second model, which is a key property in the analysis of branching random walks.     

Random Walks on Directed Covers of Graphs

Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates no longer coincide in general. Furthermore, the behavior of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.     

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.     

Slow movement of a random walk on the range of a random walk in the presence of an external field

In this article, a localisation result is proved for the biased random walk on the range of a simple random walk in high dimensions ( $d\ge 5$ ). This demonstrates that, unlike in the supercritical percolation setting, a slowdown effect occurs as soon as a non-trivial bias is introduced. The proof applies a decomposition of the underlying simple random walk path at its cut-times to relate the associated biased random walk to a one-dimensional random walk in a random environment in Sinai’s regime. Via this approach, a corresponding aging result is also proved.     

Asymptotic direction for random walks in random environments

In this paper we study the existence of an asymptotic direction for random walks in random i.i.d. environments (RWRE). We prove that if the set of directions where the walk is transient contains a non-empty open set, the walk admits an asymptotic direction. The main tool to obtain this result is the construction of a renewal structure with cones. We also prove that RWRE admits at most two opposite asymptotic directions.     

Quenched Large Deviations for Multidimensional Random Walk in Random Environment with Holding Times

We consider a random walk in random environment with random holding times, that is, the random walk jumping to one of its nearest neighbors with some transition probability after a random holding time. Both the transition probabilities and the laws of the holding times are randomly distributed over the integer lattice. Our main result is a quenched large deviation principle for the position of the random walk. The rate function is given by the Legendre transform of the so-called Lyapunov exponents for the Laplace transform of the first passage time. By using this representation, we derive some asymptotics of the rate function in some special cases.     

Invariance principle for nonhomogeneous random walks on the grid ℤ1

A nonhomogeneous random walk on the grid ℤ¹ with transition probabilities that differ from those of a certain homogeneous random walk only at a finite number of points is considered. Trajectories of such a walk are proved to converge to trajectories of a certain generalized diffusion process on the line. This result is a generalization of the well-known invariance principle for the sums of independent random variables and Brownian motion. Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 459–472, September, 1999.     

����������������ζ������ٶ�����

Let be a correlated random walk in random environment. For the sub-linear regime, that is, almost surely but , we show that there is ??Let be a correlated random walk in random environment. For the sub-linear regime, that is, almost surely but , we show that there is $0s. This result characterizes the slowdown property of the walk.     

Intersections of random walks with random sets

Two general theorems about the intersections of a random walk with a random set are proved. The result is applied to the cases when the random set is a (deterministic) half-line and a two-sided random walk. Research supported by NSF Grant DMS-8702879 and an Alfred P. Sloan Research Fellowship.     

Limit theorems for one-dimensional diffusions and random walks in random environments

Summary The limiting behavior of one-dimensional diffusion process in an asymptotically self-similar random environment is investigated through the extension of Brox's method. Similar problems are then discussed for a random walk in a random environment with the aid of optional sampling from a diffusion model; an extension of the result of Sinai is given in the case of asymptotically self-similar random environments.     

Random walks on trees

The classical gambler's ruin problem, i.e., a random walk along a line may be viewed graph theoretically as a random walk along a path with the endpoints as absorbing states. This paper is an investigation of the natural generalization of this problem to that of a particle walking randomly on a tree with the endpoints as absorbing barriers. Expressions in terms of the graph structure are obtained from the probability of absorption at an endpoint e in a walk originating from a vertex v, as well as for the expected length of the walk.     

Brownian bridge asymptotics for random mappings

Uniform random mappings of an n-element set to itself have been much studied in the combinatorial literature. We introduce a new technique, which starts by specifying a coding of mappings as walks with ± 1 steps. The uniform random mapping is thereby coded as a nonuniform random walk, and our main result is that as n→∞ the random walk rescales to reflecting Brownian bridge. This result encompasses a large number of limit theorems for “global” characteristics of uniform random mappings. © 1994 John Wiley & Sons, Inc.     

Critical survival barrier for branching random walk

We consider a branching random walk with an absorbing barrier, where the associated one-dimensional random walk is in the domain of attraction of an α-stable law. We shall prove that there is a barrier and a critical value such that the process dies under the critical barrier, and survives above it. This generalizes previous result in the case that the associated random walk has finite variance.     

Chung-type law of the iterated logarithm for continuous time random walk

A continuous time random walk is a random walk subordinated to a renewal process used in physics to model anomalous diffusion. In this paper, we establish a Chung-type law of the iterated logarithm for continuous time random walk with jumps and waiting times in the domains of attraction of stable laws.     

Approximation for the Normal Inverse Gaussian Process Using Random Sums

Abstract

We approximate the normal inverse Gaussian (NIG) process with random summations. The random sum we introduce is a random walk subordinated to the first passage time of another independent random walk; the model is interpreted as an internal mechanism at small scale that generates the NIG process. The main result is a functional limit theorem of weak convergence in the Skorohod topology.     

Two-boundary problems for a random walk

We solve main two-boundary problems for a random walk. The generating function of the joint distribution of the first exit time of a random walk from an interval and the value of the overshoot of the random walk over the boundary at exit time is determined. We also determine the generating function of the joint distribution of the first entrance time of a random walk to an interval and the value of the random walk at this time. The distributions of the supremum, infimum, and value of a random walk and the number of upward and downward crossings of an interval by a random walk are determined on a geometrically distributed time interval. We give examples of application of obtained results to a random walk with one-sided exponentially distributed jumps. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 11, pp. 1485–1509, November, 2007.     

一维紧邻时间随机环境下可逗留随机游动的有关性质

给出了可数状态空间中时间随机环境下可逗留随机游动的一个统一模型,对于一维紧邻时间随机环境下的随机游动,在一定的条件下,讨论它的极限性质和中心极限定理,该结论类似于空间随机环境下的随机游动的有关结论.     

Random Walks on Dihedral Groups

In this paper, we look at the lower bounds of two specific random walks on the dihedral group. The first theorem discusses a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p ² steps are necessary for the walk to become close to uniformly distributed on all of D _2p where p≥3 is an integer. Next we take a random walk on the dihedral group generated by a random k-subset of the dihedral group. The latter theorem shows that it is necessary to take roughly p ^2/(k−1) steps in the typical random walk to become close to uniformly distributed on all of D _2p . We note that there is at least one rotation and one flip in the k-subset, or the random walk generated by this subset has periodicity problems or will not generate all of D _2p .     

Edge-reinforced random walk on one-dimensional periodic graphs

In the present paper, linearly edge-reinforced random walk is studied on a large class of one-dimensional periodic graphs satisfying a certain reflection symmetry. It is shown that the edge-reinforced random walk is recurrent. Estimates for the position of the random walker are given. The edge-reinforced random walk has a unique representation as a random walk in a random environment, where the random environment is given by random weights on the edges. It is shown that these weights decay exponentially in space. The distribution of the random weights equals the distribution of the asymptotic proportion of time spent by the edge-reinforced random walker on the edges of the graph. The results generalize work of the authors in Merkl and Rolles (Ann Probab 33(6):2051–2093, 2005; 35(1):115–140, 2007) and Rolles (Probab Theory Related Fields 135(2):216–264, 2006) to a large class of graphs and to periodic initial weights with a reflection symmetry.