Scaling exponents of random walks in random sceneries

We compute the exact asymptotic normalizations of random walks in random sceneries, for various null recurrent random walks to the nearest neighbours, and for i.i.d., centered and square integrable random sceneries. In each case, the standard deviation grows like n with . Here, the value of the exponent is determined by the sole geometry of the underlying graph, as opposed to previous examples, where this value reflected mainly the integrability properties of the steps of the walk, or of the scenery. For discrete Bessel processes of dimension d[0;2[, the exponent is . For the simple walk on some specific graphs, whose volume grows like n^d for d[1;2[, the exponent is =1−d/4. We build a null recurrent walk, for which without logarithmic correction. Last, for the simple walk on a critical Galton–Watson tree, conditioned by its nonextinction, the annealed exponent is . In that setting and when the scenery is i.i.d. by levels, the same result holds with .     

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.     

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.     

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.     

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).     

A finite compensation procedure for a class of two-dimensional random walks

Motivated by queueing applications, we consider a class of two-dimensional random walks, the invariant measure of which can be written as a linear combination of a finite number of product-form terms. In this work, we investigate under which conditions such an elegant solution can be derived by applying a finite compensation procedure. The conditions are formulated in terms of relations among the transition probabilities in the inner area, the boundaries as well as the origin. A discussion on the importance of these conditions is also given.     

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.     

Universality limits for random matrices and de Branges spaces of entire functions

We prove that de Branges spaces of entire functions describe universality limits in the bulk for random matrices, in the unitary case. In particular, under mild conditions on a measure with compact support, we show that each possible universality limit is the reproducing kernel of a de Branges space of entire functions that equals a classical Paley-Wiener space. We also show that any such reproducing kernel, suitably dilated, may arise as a universality limit for sequences of measures on [−1,1].     

On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes

In this paper we define and analyze convergence of the geometric random walks, which are certain random walks on vector spaces over finite fields. We show that the behavior of such walks is given by certain random matroid processes. In particular, the mixing time is given by the expected stopping time, and the cutoff is equivalent to sharp threshold. We also discuss some random geometric random walks as well as some examples and symmetric cases.     

A comparison theorem on convergence rates of random walks on groups

We give a comparison theorem which helps us to estimate the change in the convergence rate when we enlarge the support of a probability that generates a random walk, and/or change the original mass assignment. Some examples of applications of this theorem are discussed.Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

A subdiffusive behaviour of recurrent random walk in random environment on a regular tree

We are interested in the random walk in random environment on an infinite tree. Lyons and Pemantle (Ann. Probab. 20, 125–136, 1992) give a precise recurrence/transience criterion. Our paper focuses on the almost sure asymptotic behaviours of a recurrent random walk (X _n ) in random environment on a regular tree, which is closely related to Mandelbrot’s (C. R. Acad. Sci. Paris 278, 289–292, 1974) multiplicative cascade. We prove, under some general assumptions upon the distribution of the environment, the existence of a new exponent such that behaves asymptotically like . The value of ν is explicitly formulated in terms of the distribution of the environment.      

Level crossing probabilities I: One-dimensional random walks and symmetrization

We prove for an arbitrary random walk in R¹ with independent increments that the probability of crossing a level at a given time n is O(n−1/2). Moment or symmetry assumptions are not necessary. In removing symmetry the (sharp) inequality P(|X+Y|?1)<2P(|X−Y|?1) for independent identically distributed X,Y is used. In part II we shall discuss the connection of this result to ‘polygonal recurrence’ of higher-dimensional walks and some conjectures on directionally reinforced random walks in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252. [5]].     

一类分形结构上的非对称随机游动

本研究一类分形结构上的随机游动,得到了它的进位不变性,进位时间的生成函数表达式并得到一个极限定理。     

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 in two-dimensional complexes

A 2-dimensional complex is a union of a finite number of quarter planes ₊ ² having some boundaries in common. The most interesting example is the union of all 2-dimensional faces of ₊ ^N . We consider maximally homogeneous random walks on such complexes and obtain necessary and sufficient conditions for ergodicity, null recurrence and transience up to some non-zero assumptions which are of measure 1 in the parameter space.The problem we address in this paper is of theoretical range. However, the results can be applied to performance evaluation of some telecommunication systems (e.g. local area networks) viewed as interacting queues. To enforce this assertion, a detailed example of coupled queues in differentregimes is presented.     

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.