A random environment for linearly edge-reinforced random walks on infinite graphs

We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains, determined by time-independent strictly positive weights on the edges. Furthermore, we prove bounds for the random weights, uniform, among others, in the size of the graph.      

Large and moderate deviation principles for susceptible-infected-removed epidemic in a random environment

We are concerned with SIR epidemics in a random environment on complete graphs, where edges are assigned with i.i.d. weights. Our main results give large and moderate deviation principles of sample paths of this model. Our results generalize large and moderate deviation principles of the classic SIR models given by E. Pardoux and B. Samegni-Kepgnou [J. Appl. Probab., 2017, 54: 905-920] and X. F. Xue [Stochastic Process. Appl., 2019, 140: 49-80].     

The Number of Generations Entirely Visited for Recurrent Random Walks in a Random Environment

In this paper we deal with a random walk in a random environment on a super-critical Galton–Watson tree. We focus on the recurrent cases already studied by Hu and Shi (Ann. Probab. 35:1978–1997, 2007; Probab. Theory Relat. Fields 138:521–549, 2007), Faraud et al. (Probab. Theory Relat. Fields, 2011, in press), and Faraud (Electron. J. Probab. 16(6):174–215, 2011). We prove that the largest generation entirely visited by these walks behaves like logn, and that the constant of normalization, which differs from one case to another, is a function of the inverse of the constant of Biggins’ law of large numbers for branching random walks (Biggins in Adv. Appl. Probab. 8:446–459, 1976).     

Fastest mixing Markov chain problem for the union of two cliques

A symmetric, random walk on a graph G can be defined by prescribing weights to the edges in such a way that for each vertex the sum of the weights of the edges incident to the vertex is at most one. The fastest mixing, Markov chain (FMMC) problem for G is to determine the weighting that yields the fastest mixing random walk. We solve the FMMC problem in the case that G is the union of two complete graphs.     

On the recurrence of edge-reinforced random walk on ℤ×G

Let G be a finite tree. It is shown that edge-reinforced random walk on ℤ×G with large initial weights is recurrent. This includes recurrence on multi-level ladders of arbitrary width. For edge-reinforced random walk on {0,1, . . . ,n}×G, it is proved that asymptotically, with high probability, the normalized edge local times decay exponentially in the distance from the starting level. The estimates are uniform in n. They are used in the recurrence proof.     

Almost sure convergence for stochastically biased random walks on trees

We are interested in the biased random walk on a supercritical Galton?CWatson tree in the sense of Lyons (Ann. Probab. 18:931?C958, 1990) and Lyons, Pemantle and Peres (Probab. Theory Relat. Fields 106:249?C264, 1996), and study a phenomenon of slow movement. In order to observe such a slow movement, the bias needs to be random; the resulting random walk is then a tree-valued random walk in random environment. We investigate the recurrent case, and prove, under suitable general integrability assumptions, that upon the system??s non-extinction, the maximal displacement of the walk in the first n steps, divided by (log n)³, converges almost surely to a known positive constant.     

Random walks on stochastic hyperbolic half planar triangulations

We study the simple random walk on stochastic hyperbolic half planar triangulations constructed in (Angel and Ray, Ann Probab, in press). We show that almost surely the walker escapes the boundary of the map in positive speed and that the return probability to the starting point after n steps scales like © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 213–234, 2016     

拟顶点可迁图上简单随机游走的切割点

证明了体积增长不低于5次多项式的拟顶点可迁图上的简单随机游走几乎处处有无穷多个切割时,从而有无穷多个切割点.该结论在所论情形下肯定了Benjamini,Gurel-Gurevich和Schramm在文[2011,Cutpoints and resistance of random walk paths,Ann.Probab.,39(3):1122-1136]中提出的猜想:顶点可迁图上暂留简单随机游走几乎处处有无穷多个切割点.     

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.     

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.     

How edge-reinforced random walk arises naturally

 We give a characterization of a modified edge-reinforced random walk in terms of certain partially exchangeable sequences. In particular, we obtain a characterization of an edge-reinforced random walk (introduced by Coppersmith and Diaconis) on a 2-edge-connected graph. Modifying the notion of partial exchangeability introduced by Diaconis and Freedman in [3], we characterize unique mixtures of reversible Markov chains under a recurrence assumption. Received: 22 January 2002 / Revised version: 24 September 2002 Published online: 15 April 2003 Most of this paper was written while the author was working at EURANDOM in Eindhoven, The Netherlands. Mathematics Subject Classification (2000): 60K37, 60G09     

Transient random walks in random environment on a Galton–Watson tree

We consider a transient random walk (X _n ) in random environment on a Galton–Watson tree. Under fairly general assumptions, we give a sharp and explicit criterion for the asymptotic speed to be positive. As a consequence, situations with zero speed are revealed to occur. In such cases, we prove that X _n is of order of magnitude n ^Λ, with ${\Lambda \in (0,1)}$ . We also show that the linearly edge reinforced random walk on a regular tree always has a positive asymptotic speed, which improves a recent result of Collevecchio (Probab Theory Related 136(1):81–101, 2006).     

Multi-Particle Processes with Reinforcements

We consider a multi-particle generalization of linear edge-reinforced random walk (ERRW). We observe that in absence of exchangeability, new techniques are needed in order to study the multi-particle model. We describe an unusual coupling construction associated with the two-point edge-reinforced process on ℤ and prove a form of recurrence: the two particles meet infinitely often a.s. This research was supported in part by NSF VIGRE Grant DMS 9983726 at UCLA.     

Harnack inequalities on weighted graphs and some applications to the random conductance model

We establish elliptic and parabolic Harnack inequalities on graphs with unbounded weights. As an application we prove a local limit theorem for a continuous time random walk \(X\) in an environment of ergodic random conductances taking values in \((0, \infty )\) satisfying some moment conditions.     

Analysis of random walks in dynamic random environments via L2-perturbations

We consider random walks in dynamic random environments given by Markovian dynamics on ${\mathbb{Z}}^d$. We assume that the environment has a stationary distribution $\mu$ and satisfies the Poincaré inequality w.r.t. $\mu$. The random walk is a perturbation of another random walk (called “unperturbed”). We assume that also the environment viewed from the unperturbed random walk has stationary distribution $\mu$. Both perturbed and unperturbed random walks can depend heavily on the environment and are not assumed to be finite-range. We derive a law of large numbers, an averaged invariance principle for the position of the walker and a series expansion for the asymptotic speed. We also provide a condition for non-degeneracy of the diffusion, and describe in some details equilibrium and convergence properties of the environment seen by the walker. All these results are based on a more general perturbative analysis of operators that we derive in the context of $L^2$- bounded perturbations of Markov processes by means of the so-called Dyson–Phillips expansion.     

Limit behaviors of random connected graphs driven by a Poisson process

We consider a class of random connected graphs with random vertices and random edges with the random distribution of vertices given by a Poisson point process with the intensity n localized at the vertices and the random distribution of the edges given by a connection function. Using the Avram-Bertsimas method constructed in 1992 for the central limit theorem on Euclidean functionals, we find the convergence rate of the central limit theorem process, the moderate deviation, and an upper bound for large deviations depending on the total length of all edges of the random connected graph.     

Multi-excited random walks on integers

We introduce a class of nearest-neighbor integer random walks in random and non-random media, which includes excited random walks considered in the literature. At each site the random walker has a drift to the right, the strength of which depends on the environment at that site and on how often the walker has visited that site before. We give exact criteria for recurrence and transience and consider the speed of the walk.Most of this work was done while the author was Szegö Assistant Professor at Stanford University.     

Discrepancy properties for random regular digraphs

For the uniform random regular directed graph we prove concentration inequalities for (1) codegrees and (2) the number of edges passing from one set of vertices to another. As a consequence, we can deduce discrepancy properties for the distribution of edges essentially matching results for Erd?s–Rényi digraphs obtained from Chernoff‐type bounds. The proofs make use of the method of exchangeable pairs, developed for concentration of measure by Chatterjee in (Chatterjee, Probab Theory and Relat Fields 138 (2007), 305–321). Exchangeable pairs are constructed using two involutions on the set of regular digraphs: a well‐known “simple switching” operation, as well as a novel “reflection” operation. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 23–58, 2017     

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.     

Deterministic random walks on finite graphs

The rotor‐router model, also known as the Propp machine, is a deterministic process analogous to a random walk on a graph. Instead of distributing tokens to randomly chosen neighbors, the Propp machine deterministically serves the neighbors in a fixed order by associating to each vertex a “rotor‐router” pointing to one of its neighbors. This paper investigates the discrepancy at a single vertex between the number of tokens in the rotor‐router model and the expected number of tokens in a random walk, for finite graphs in general. We show that the discrepancy is bounded by O (mn) at any time for any initial configuration if the corresponding random walk is lazy and reversible, where n and m denote the numbers of nodes and edges, respectively. For a lower bound, we show examples of graphs and initial configurations for which the discrepancy at a single vertex is Ω(m) at any time (> 0). For some special graphs, namely hypercube skeletons and Johnson graphs, we give a polylogarithmic upper bound, in terms of the number of nodes, for the discrepancy. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,739–761, 2015