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.     

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.     

Limit distributions for the number of particles in branching random walks

We study branching random walks with continuous time. Particles performing a random walk on ?², are allowed to be born and die only at the origin. It is assumed that the offspring reproduction law at the branching source is critical and the random walk outside the source is homogeneous and symmetric. Given particles at the origin, we prove a conditional limit theorem for the joint distribution of suitably normalized numbers of particles at the source and outside it as time unboundedly increases. As a consequence, we establish the asymptotic independence of such random variables.     

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.     

Limit theorems for reinforced random walks on certain trees

Consider a linearly edge-reinforced random walk defined on the b-ary tree, b≥70. We prove the strong law of large numbers for the distance of this process from the root. We give a sufficient condition for this strong law to hold for general edge-reinforced random walks and random walks in a random environment. We also provide a central limit theorem. Supported in part by a Purdue Research Foundation fellowship this work is part of the author's PhD thesis.     

Local Limit Theorems for Sequences of Simple Random Walks on Graphs

In this article, local limit theorems for sequences of simple random walks on graphs are established. The results formulated are motivated by a variety of random graph models, and explanations are provided as to how they apply to supercritical percolation clusters, graph trees converging to the continuum random tree and the homogenisation problem for nested fractals. A subsequential local limit theorem for the simple random walks on generalised Sierpinski carpet graphs is also presented.      

Symmetric random walk in random environment in one dimension

We give a new proof of the central limit theorem for one dimensional symmetric random walk in random environment. The proof is quite elementary and natural. We show the convergence of the generators and from this we conclude the convergence of the process. We also investigate the hydrodynamic limit (HDL) of one dimensional symmetric simple exclusion in random environment and prove stochastic convergence of the scaled density field. The macroscopic behaviour of this field is given by a linear heat equation. The diffusion coefficient is the same as that of the corresponding random walk. This revised version was published online in June 2006 with corrections to the Cover Date.     

Snakes and perturbed random walks

We study some properties of random walks perturbed at extrema, which are generalizations of the walks considered, e.g., by Davis (1999) and Tóth (1996). This process can also be viewed as a version of an excited random walk, recently studied by many authors. We obtain several properties related to the range of the process with infinite memory and prove the strong law, the central limit theorem, and the criterion for the recurrence of the perturbed walk with finite memory. We also state some open problems. Our methods are predominantly combinatorial and do not involve complicated analytic techniques.     

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.     

Central limit theorems for biased randomly trapped random walks on Z

We prove CLTs for biased randomly trapped random walks in one dimension. By considering a sequence of regeneration times, we will establish an annealed invariance principle under a second moment condition on the trapping times. In the quenched setting, an environment dependent centring is necessary to achieve a central limit theorem. We determine a suitable expression for this centring. As our main motivation, we apply these results to biased walks on subcritical Galton–Watson trees conditioned to survive for a range of bias values.     

Counting trees with random walks

We give a simple proof of Tutte’s matrix-tree theorem, a well-known result providing a closed-form expression for the number of rooted spanning trees in a directed graph. Our proof stems from placing a random walk on a directed graph and then applying the Markov chain tree theorem to count trees. The connection between the two theorems is not new, but it appears that only one direction of the formal equivalence between them is readily available in the literature. The proof we now provide establishes the other direction. More generally, our approach is another example showing that random walks can serve as a powerful glue between graph theory and Markov chain theory, allowing formal statements from one side to be carried over to the other.     

The Branching-Ruin Number and the Critical Parameter of Once-Reinforced Random Walk on Trees

The motivation for this paper is the study of the phase transition for recurrence/ transience of a class of self-interacting random walks on trees, which includes the once-reinforced random walk. For this purpose, we define a quantity, which we call the branching-ruin number of a tree, which provides (in the spirit of Furstenberg [11] and Lyons [13]) a natural way to measure trees with polynomial growth. We prove that the branching-ruin number of a tree is equal to the critical parameter for the recurrence/transience of the once-reinforced random walk. We define a sharp and effective (i.e., computable) criterion characterizing the recurrence/transience of a larger class of self-interacting walks on trees, providing the complete picture for their phase transition. © 2019 Wiley Periodicals, Inc.     

A one-dimensional version of the random interlacements

We base ourselves on the construction of the two-dimensional random interlacements (Comets et al., 2016) to define the one-dimensional version of the process. For this, we consider simple random walks conditioned on never hitting the origin. We compare this process to the conditional random walk on the ring graph. Our results are the convergence of the vacant set on the ring graph to the vacant set of one-dimensional random interlacements, a central limit theorem for the interlacements’ local time and the convergence in law of the local times of the conditional walk on the ring graph to the interlacements’ local times.     

Asymptotic variance of the self-intersections of stable random walks using Darboux-Wiener theory

We present a Darboux-Wiener type lemma as a powerful alternative to the classical Tauberian theorem when monotonicity is not known a priori. We apply it to obtain the exact asymptotics of the variance of the self-intersections of a one-dimensional stable random walk. Finally we prove a functional central limit theorem for stable random walk in random scenery conjectured in [1].     

Random walks on diestel-leader graphs

We investigate various features of a quite new family of graphs, introduced as a possible example of vertex-transitive graph not roughly isometric with a Cayley graph of some finitely generated group. We exhibit a natural compactification and study a large class of random walks, proving theorems concerning almost sure convergence to the boundary, a strong law of large numbers and a central limit theorem. The asymptotic type of then-step transition probabilities of the simple random walk is determined.     

Ellipticity criteria for ballistic behavior of random walks in random environment

We introduce ellipticity criteria for random walks in i.i.d. random environments under which we can extend the ballisticity conditions of Sznitman and the polynomial effective criteria of Berger, Drewitz and Ramírez originally defined for uniformly elliptic random walks. We prove under them the equivalence of Sznitman’s \((T')\) condition with the polynomial effective criterion \((P)_M\) , for \(M\) large enough. We furthermore give ellipticity criteria under which a random walk satisfying the polynomial effective criterion, is ballistic, satisfies the annealed central limit theorem or the quenched central limit theorem.     

Central Limit Theorems for Gromov Hyperbolic Groups

In this paper we study asymptotic properties of symmetric and nondegenerate random walks on transient hyperbolic groups. We prove a central limit theorem and a law of iterated logarithm for the drift of a random walk, extending previous results by S. Sawyer and T. Steger and of F. Ledrappier for certain CAT(−1)-groups. The proofs use a result by A. Ancona on the identification of the Martin boundary of a hyperbolic group with its Gromov boundary. We also give a new interpretation, in terms of Hilbert metrics, of the Green metric, first introduced by S. Brofferio and S. Blachère.     

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

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

Multiscale analysis of exit distributions for random walks in random environments

We present a multiscale analysis for the exit measures from large balls in , of random walks in certain i.i.d. random environments which are small perturbations of the fixed environment corresponding to simple random walk. Our main assumption is an isotropy assumption on the law of the environment, introduced by Bricmont and Kupiainen. Under this assumption, we prove that the exit measure of the random walk in a random environment from a large ball, approaches the exit measure of a simple random walk from the same ball, in the sense that the variational distance between smoothed versions of these measures converges to zero. We also prove the transience of the random walk in random environment. The analysis is based on propagating estimates on the variational distance between the exit measure of the random walk in random environment and that of simple random walk, in addition to estimates on the variational distance between smoothed versions of these quantities. Partially supported by NSF grant DMS-0503775.     

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.