Velocity and Lyapounov exponents of some random walks in random environment

We express the asymptotic velocity of random walks in random environment satisfying Kalikow's condition in terms of the Lyapounov exponents which have previously been used in the context of large deviations.     

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.     

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.     

Random walks in a strongly sparse random environment

The integer points (sites) of the real line are marked by the positions of a standard random walk with positive integer jumps. We say that the set of marked sites is weakly, moderately or strongly sparse depending on whether the jumps of the random walk are supported by a bounded set, have finite or infinite mean, respectively. Focussing on the case of strong sparsity and assuming additionally that the distribution tail of the jumps is regularly varying at infinity we consider a nearest neighbor random walk on the set of integers having jumps $\pm 1$ with probability $1∕2$ at every nonmarked site, whereas a random drift is imposed at every marked site. We prove new distributional limit theorems for the so defined random walk in a strongly sparse random environment, thereby complementing results obtained recently in Buraczewski et al. (2019) for the case of moderate sparsity and in Matzavinos et al. (2016) for the case of weak sparsity. While the random walk in a strongly sparse random environment exhibits either the diffusive scaling inherent to a simple symmetric random walk or a wide range of subdiffusive scalings, the corresponding limit distributions are non-stable.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

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.     

Branching random walks II

A general method is developed with which various theorems on the mean square convergence of functionals of branching random walks are proven. The results cover extensions and generalizations of classical central limit analogues as well as a result of a different type.     

Invariance principle for biased bootstrap random walks

Our main goal is to study a class of processes whose increments are generated via a cellular automata rule. Given the increments of a simple biased random walk, a new sequence of (dependent) Bernoulli random variables is produced. It is built, from the original sequence, according to a cellular automata rule. Equipped with these two sequences, we construct two more according to the same cellular automata rule. The construction is repeated a fixed number of times yielding an infinite array ($\{?K,\dots ,K\}\times \mathbb{N}$) of (dependent) Bernoulli random variables. Taking partial sums of these sequences, we obtain a $(2K+1)$-dimensional process whose increments belong to the state space ${\{?1,1\}}^{2K+1}$.The aim of the paper is to study the long term behaviour of this process. In particular, we establish transience/recurrence properties and prove an invariance principle. The limiting behaviour of these processes depends strongly on the direction of the iteration, and exhibits few surprising features. This work is motivated by an earlier investigation (see Collevecchio et al. (2015)), in which the starting sequence is symmetric, and by the related work Ferrari et al. (2000).     

Branching random walks I

A general method is developed with which various theorems on the mean square convergence of functionals of branching random walks are proven. The results cover extensions and generalizations of classical central limit analogues as well as a result of a different type.     

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.      

Upper limits of Sinai’s walk in random scenery

We consider Sinai’s walk in i.i.d. random scenery and focus our attention on a conjecture of Révész concerning the upper limits of Sinai’s walk in random scenery when the scenery is bounded from above. A close study of the competition between the concentration property for Sinai’s walk and negative values for the scenery enables us to prove that the conjecture is true if the scenery has “thin” negative tails and is false otherwise.     

On the structure of stable random walks

We show that the Cauchy random walk on the line, and the Gaussian random walk on the plane are similar as infinite measure preserving transformations.     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

Tail estimates for one-dimensional non-nearest-neighbor random walk in random environment

Suppose that the integers are assigned i.i.d. random variables {(β gx , . . . , β 1x , α x )} (each taking values in the unit interval and the sum of them being 1), which serve as an environment. This environment defines a random walk {X n } (called RWRE) which, when at x, moves one step of length 1 to the right with probability α x and one step of length k to the left with probability β kx for 1≤ k≤ g. For certain environment distributions, we determine the almost-sure asymptotic speed of the RWRE and show that the chance of the RWRE deviating below this speed has a polynomial rate of decay. This is the generalization of the results by Dembo, Peres and Zeitouni in 1996. In the proof we use a large deviation result for the product of random matrices and some tail estimates and moment estimates for the total population size in a multi-type branching process with random environment.     

On random walks for Pollard's rho method

We consider Pollard's rho method for discrete logarithm computation. Usually, in the analysis of its running time the assumption is made that a random walk in the underlying group is simulated. We show that this assumption does not hold for the walk originally suggested by Pollard: its performance is worse than in the random case. We study alternative walks that can be efficiently applied to compute discrete logarithms. We introduce a class of walks that lead to the same performance as expected in the random case. We show that this holds for arbitrarily large prime group orders, thus making Pollard's rho method for prime group orders about faster than before.

     

Diameter of random spanning trees in a given graph

Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph G is between and with high probability., where c and c′ depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of logn. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 69: 223–240, 2012