Quenched point-to-point free energy for random walks in random potentials

We consider a random walk in a random potential on a square lattice of arbitrary dimension. The potential is a function of an ergodic environment and steps of the walk. The potential is subject to a moment assumption whose strictness is tied to the mixing of the environment, the best case being the i.i.d. environment. We prove that the infinite volume quenched point-to-point free energy exists and has a variational formula in terms of entropy. We establish regularity properties of the point-to-point free energy, and link it to the infinite volume point-to-line free energy and quenched large deviations of the walk. One corollary is a quenched large deviation principle for random walk in an ergodic random environment, with a continuous rate function.     

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.     

Random Walks on Trees with Finitely Many Cone Types

This paper is devoted to the study of random walks on infinite trees with finitely many cone types (also called periodic trees). We consider nearest neighbour random walks with probabilities adapted to the cone structure of the tree, which include in particular the well studied classes of simple and homesick random walks. We give a simple criterion for transience or recurrence of the random walk and prove that the spectral radius is equal to 1 if and only if the random walk is recurrent. Furthermore, we study the asymptotic behaviour of return probabilitites and prove a local limit theorem. In the transient case, we also prove a law of large numbers and compute the rate of escape of the random walk to infinity, as well as prove a central limit theorem. Finally, we describe the structure of the boundary process and explain its connection with the random walk.     

An almost sure invariance principle for random walks in a space-time random environment

We consider a discrete time random walk in a space-time i.i.d. random environment. We use a martingale approach to show that the walk is diffusive in almost every fixed environment. We improve on existing results by proving an invariance principle and considering environments with an L² averaged drift. We also state an a.s. invariance principle for random walks in general random environments whose hypothesis requires a subdiffusive bound on the variance of the quenched mean, under an ergodic invariant measure for the environment chain. T. Sepp?l?inen was partially supported by National Science Foundation grant DMS-0402231.     

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.     

直线上独立时间随机环境中随机游动的渐近行为

主要讨论直线上独立时间随机环境中随机游动的常返性和非常返性,以及该过程的中心极限定理.     

The limit theorems for random walk with state space ℝ in a space-time random environment

We consider a discrete time random environment. We state that when the random walk on real number space in a environment is i.i.d., under the law, the law of large numbers, iterated law and CLT of the process are correct space-time random marginal annealed Using a martingale approach, we also state an a.s. invariance principle for random walks in general random environment whose hypothesis requires a subdiffusive bound on the variance of the quenched mean, under an ergodic invariant measure for the environment chain.     

Random walks on finitely structured transfinite networks

A general theory for random walks on transfinite networks whose ranks are arbitrary natural numbers is established herein. In such networks, nodes of higher ranks connect together transfinite networks of lower ranks. The probabilities for transitions through such nodes are obtained as extensions of the Nash-Williams rule for random walks on ordinary infinite networks. The analysis is based on the theory of transfinite electrical networks, but it requires that the transfinite network have a structure that generalizes local-finiteness for ordinary infinite networks. The shorting together of nodes of different ranks are allowed; this complicates transitions through such nodes but provides a considerably more general theory. It is shown that, with respect to any finite set of nodes of any ranks, a transfinite random walk can be represented by an irreducible reversible Makov chain, whose state space is that set of nodes.This work was supported by the National Science Foundation under the grants DMS-9200738 and MIP-9200748.     

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 .     

Linear and sub-linear growth and the CLT for hitting times of a random walk in random environment on a strip

The main goal of this work is to study the asymptotic behaviour of hitting times of a random walk (RW) in a quenched random environment (RE) on a strip. We introduce enlarged random environments in which the traditional hitting time can be presented as a sum of independent random variables whose distribution functions form a stationary random sequence. This allows us to obtain conditions (stated in terms of properties of random environments) for a linear growth of hitting times of relevant random walks. In some important cases (e.g. independent random environments) these conditions are also necessary for this type of behaviour. We also prove the quenched Central Limit Theorem (CLT) for hitting times in the general ergodic setting. A particular feature of these (ballistic) laws in random environment is that, whenever they hold under standard normalization, the convergence is a convergence with a speed. The latter is due to certain properties of moments of hitting times which are also studied in this paper. The asymptotic properties of the position of the walk are stated but are not proved in this work since this has been done in Goldhseid (Probab. Theory Relat. Fields 139(1):41–64, 2007).      

On the Local Times of Transient Random Walks

We study the properties of the local and occupation times of certain transient random walks. First, our recent results concerning simple symmetric random walk in higher dimension are surveyed, then we start to establish similar results for simple asymmetric random walk on the line.     

Displacement exponent for loop-erased random walk on the Sierpiński gasket

We prove that loop-erased random walks on the finite pre-Sierpiński gaskets can be extended to a loop-erased random walk on the infinite pre-Sierpiński gasket by using the ‘erasing-larger-loops-first’ method, and obtain the asymptotic behavior of the walk as the number of steps increases, in particular, the displacement exponent and a law of the iterated logarithm.     

Tubular recurrence

We introduce the directed-edge-reinforced random walk and prove that the process is equivalent to a random walk in random environment. Using Oseledec"s multiplicative ergodic theorem, we obtain recurrence and transience criteria for random walks in random environment on graphs with a certain linear structure and apply them to directed-edge-reinforced random walks. This revised version was published online in August 2006 with corrections to the Cover Date.     

The heavy range of randomly biased walks on trees

We focus on recurrent random walks in random environment (RWRE) on Galton–Watson trees. The range of these walks, that is the number of sites visited at some fixed time, has been studied in three different papers Andreoletti and Chen (2018), Aïdékon and de Raphélis (2017) and de Raphélis (2016). Here we study the heavy range: the number of edges frequently visited by the walk. The asymptotic behavior of this process when the number of visits is a power of the number of steps of the walk is given for all recurrent cases. It turns out that this heavy range plays a crucial role in the rate of convergence of an estimator of the environment from a single trajectory of the RWRE.     

Random random walks on ℤ2 d

Summary. We consider random walks on classes of graphs defined on the d-dimensional binary cube ℤ₂ ^d by placing edges on n randomly chosen parallel classes of vectors. The mixing time of a graph is the number of steps of a random walk before the walk forgets where it started, and reaches a random location. In this paper we resolve a question of Diaconis by finding exact expressions for this mixing time that hold for all n>d and almost all choices of vector classes. This result improves a number of previous bounds. Our method, which has application to similar problems on other Abelian groups, uses the concept of a universal hash function, from computer science.     

Random Walks in Weyl Chambers and the Decomposition of Tensor Powers

We consider a class of random walks on a lattice, introduced by Gessel and Zeilberger, for which the reflection principle can be used to count the number of k-step walks between two points which stay within a chamber of a Weyl group. We prove three independent results about such reflectable walks: first, a classification of all such walks; second, many determinant formulas for walk numbers and their generating functions; third, an equality between the walk numbers and the multiplicities of irreducibles in the kth tensor power of certain Lie group representations associated to the walk types. Our results apply to the defining representations of the classical groups, as well as some spin representations of the orthogonal groups.     

Transient Nearest Neighbor Random Walk and Bessel Process

We prove a strong invariance principle between a transient Bessel process and a certain nearest neighbor (NN) random walk that is constructed from the former by using stopping times. We show that their local times are close enough to share the same strong limit theorems. It is also shown that if the difference between the distributions of two NN random walks are small, then the walks themselves can be constructed in such a way that they are close enough. Finally, some consequences concerning strong limit theorems are discussed.     

Random Walks on Trees and an Inequality of Means

We define trees generated by bi-infinite sequences, calculate their walk-invariant distribution and the speed of a biased random walk. We compare a simple random walk on a tree generated by a bi-infinite sequence with a simple random walk on an augmented Galton-Watson tree. We find that comparable simple random walks require the augmented Galton-Watson tree to be larger than the corresponding tree generated by a bi-infinite sequence. This is due to an inequality for random variables with values in [1, [ involving harmonic, geometric and arithmetic mean.     

Asymptotics of the Moment Generating Function for the Range of Random Walks

The range of random walks means the number of distinct sites visited at least once by the random walk before time n. We are interested in the free energy function of the range of simple symmetric random walks and determine the asymptotic behavior near the origin.     

Scaling limit theorem for transient random walk in random environment

We construct a sequence of transient random walks in random environments and prove that by proper scaling, it converges to a diffusion process with drifted Brownian potential. To this end, we prove a counterpart of convergence for transient random walk in non-random environment, which is interesting itself.